MOLOCO is a company that matches advertisers with potential users using their high-performance ad platform.

MOLOCO is in contact with $$$N$$$ advertisers, where the $$$i$$$-th advertiser has paid for $$$a_i$$$ advertisements to deliver. Our advanced prediction algorithm has picked $$$M$$$ potential recipients, which we will deliver the advertisements to. For the $$$j$$$-th recipient, we can deliver up to $$$b_j$$$ advertisements.

Jaehyun is testing several hypotheses to increase engagement in the advertisements. One day, Jaehyun thought that all advertisements received by a single recipient should come from different advertisers: it is boring to watch the same advertisement multiple times.

Jaehyun wants to estimate the profitability of his hypotheses. He will perform the following kinds of updates.

• 1 i: Increase $$$a_i$$$ by one.
• 2 i: Decrease $$$a_i$$$ by one.
• 3 j: Increase $$$b_j$$$ by one.
• 4 j: Decrease $$$b_j$$$ by one.

All updates are cumulative. Jaehyun wants to check if the system can deliver all advertisements of our advertisers given the changing landscape of the advertisers and recipients.

Donghyun is playing a digital card game. In this game, two players start with a deck (stack of cards) of $$$30$$$ cards and $$$30$$$ HP (health points). They alternate turns drawing and playing their cards. The winner is the first person who makes their opponent's HP less than or equal to $$$0$$$.

This time, Donghyun met a tough opponent; the opponent mixed some bombs into Donghyun's deck! Now, there are $$$A$$$ cards in Donghyun's deck, and $$$B$$$ of them are bombs. Each card in the deck is equally likely to be a bomb.

Donghyun starts his next turn with $$$C$$$ HP. On his next turn, he will remove cards from the top of his deck one at a time until he removes a card that is not a bomb or until his HP becomes less than or equal to 0. For each bomb that he removes, he loses 5 HP. Donghyun's deck is guaranteed to contain at least one card which is not a bomb, so this process is guaranteed to terminate.

Donghyun is worried he may lose the game because of the bombs. Specifically, he will lose the game if and only if his HP becomes less than or equal to $$$0$$$. Donghyun asks you to calculate the probability that he does not lose the game in his next turn.

The country of RUN has $$$N$$$ cities, some of which are connected by two-way roads. Each road connects two different cities, and no two roads connect the same pair of cities. It is not guaranteed that every city is reachable from every other city by traveling along some roads.

Due to traffic issues, the mayor of RUN decided to make all roads one-way. After doing so, it must be possible to move from any city to any other city using one or more roads. To save as much money as possible, over all possible road orientations that satisfy this condition, the mayor will pick the cheapest one. Note that the cost of orienting a road depends on both the specific road and the direction it is oriented in.

You are in the spaceship The Skeld with your fellow crewmates. However, while checking the central power system, you found out that one crucial wiring installation of the central power system has been sabotaged. To prevent an engine failure, you should quickly fix the installation.

The installation consists of $$$N$$$ nodes and $$$M=\frac{N(N-1)}{2}$$$ wires. All possible pairs of distinct nodes in the installation are connected with a wire. Originally, each of the $$$M$$$ wires had exactly one tag attached to it. Each tag has a positive integer value, and different tags may have the same value. However, due to the sabotage, all the tags were removed from the wires and left on the floor. Fortunately, you gathered all $$$M$$$ tags from the ground. Now, in order to fix the installation, you have to trigger the reboot sequence by re-attaching all the tags back to the wires twice.

For an installation where all wires have a tag on them, let's define the cost of an installation as the cost of its minimum spanning tree, that is, the minimum cost of a subset of wires such that all nodes are connected using only the given subset of wires. Here, the cost of the set of wires is defined as the sum of the tag values of all wires in the set.

The reboot sequence is triggered in two steps:

• First, you should attach the tags to minimize the cost of the installation.
• Then, after detaching all tags, you should attach the tags to maximize the cost of the installation.

Please compute the cost of each installation.

Consider an undirected simple graph $$$G = (V, E)$$$. The problem of finding a node with similar connectivity is a well-researched topic, because it acts as a good metric to determine which nodes are relevant to other nodes. Services such as "friend recommendation" in Facebook is a good example of its applications. To formalize the notion of similarity, the concept of Jaccard similarity can be used, which is defined as $$$|N(v_1) \cap N(v_2)| / |N(v_1) \cup N(v_2)|$$$, where $$$N(v) = \{u | (u, v) \in E\}$$$.

Here, we will instead discuss the min-hashing method. Assume each node $$$v$$$ has the label $$$l_v$$$. The shingle value $$$s_v$$$ of node $$$v$$$ is defined as $$$s_v = \min \{l_u | u \in N(v) \}$$$. This method is efficient enough to keep up with industrial needs, and it is also a great metric for similarity: the Jaccard similarity between the set of neighbors $$$N(v_1)$$$ and $$$N(v_2)$$$ is an unbiased estimator of the probability that nodes $$$v_1$$$ and $$$v_2$$$ have the same shingle values, for random unique labels.

Let's think about a variant of min-hashing: we repeatedly perform min-hashing by taking the label as the previous iteration's shingle value. In this variant, for each node $$$v$$$ and the number of iterations $$$k$$$, the value $$$h^{(k)}_v$$$ is defined as

$$$$$$ h^{(k)}_v = \begin{cases} s_v, & \text{if $k = 1$}\\ \min \{h^{(k-1)}_u | u \in N(v) \}, & \text{if $k \geq 2$} \\ \end{cases} $$$$$$

For each $$$k$$$, let $$$c_k$$$ be the number of unordered pairs of distinct vertices $$$\{u, v\}$$$ such that $$$h^{(k)}_u = h^{(k)}_v$$$. Then, how does the value $$$c_k$$$ change as $$$k$$$ increases? In this problem, your task is to compute $$$\max_{k \in \mathbb{N}} c_k$$$.

A histogram is a polygon made by aligning $$$N$$$ adjacent rectangles that share a common base line. Each rectangle is called a bar. The $$$i$$$-th bar from the left has width 1 and height $$$H_i$$$.

Your goal is to find the area of the largest rectangle contained in the given histogram, such that one of the sides is parallel to the base line.

Figure 1. The histogram given in the example, with the largest rectangle shown on the right.

Actually, no, you have to find the largest square. Since the area of a square is determined by its side length, you are required to output the side length instead of the area.

Figure 2. The histogram given in the example, with the largest square shown on the right.

You are given a string $$$S$$$ of length $$$N$$$, consisting of uppercase letters, and a small nonnegative integer $$$K$$$.

Please compute the number of strings $$$T$$$ of length $$$N$$$, consisting of only uppercase letters, such that the longest common subsequence of $$$S$$$ and $$$T$$$ has length at least $$$N - K$$$. As the number could be large, print the number of such strings modulo $$$10^9 + 7$$$.

A string $$$S = s_1s_2\ldots s_n$$$ is a subsequence of a string $$$T = t_1t_2\ldots t_m$$$ if there exists an increasing sequence of indices $$$1 \le i_1 \lt i_2 \lt \ldots \lt i_n \le m$$$ such that $$$s_x = t_{i_x}$$$ for all $$$1 \le x \le n$$$.

MOLOCO is a company that matches advertisers with potential users using their high-performance ad platform.

Whenever the application has available space for ads, the app requests the AdExchange platform to determine which ad to show. Then, the AdExchange holds an auction, in which bidders like MOLOCO bid for the opportunity to show their advertisement.

RUN wants to advertise its 2020 ICPC Mock Competition. They have asked MOLOCO for the advertisement. RUN has a total of $$$K$$$ dollars and wants to display the ad for internal apps used by KAISTians. The ads in those apps are in one of six types, and the bidding price depends only on the type of ad. The first bidder to bid on the ad gets to show their ad.

AdExchange has already determined the costs of the six ad types and the $$$N$$$ auctions it will run today. In the $$$i$$$-th auction, AdExchange will run an auction for an ad of type $$$c_i$$$. AdExchange never runs two auctions at the same time, more specifically auction $$$i+1$$$ cannot start until after auction $$$i$$$ ends.

MOLOCO will bid during auctions using the following strategy - before the auctions begin, RUN selects a set of ad types. During the $$$i$$$-th auction, if the ad type for that auction is in RUN's set, and RUN has enough money to bid on an ad of that type, MOLOCO will submit a bid. Otherwise, they will ignore it.

MOLOCO is very fast at bidding, so it will always be the first bidder if it bids on the ad. Determine the maximum number of ads they can bid on if RUN selects the set of ad types optimally.

On Baekjoon Online Judge, there are a series of problems related to processing queries on a tree. We KAISTians are proud to offer the seventeenth edition in this series.

You are given a tree with $$$N$$$ vertices. Each vertex is numbered from 1 to $$$N$$$. The tree is rooted at vertex 1.

People can live in each vertex. Let $$$A[i]$$$ be the number of people living in vertex $$$i$$$. Initially, $$$A[i] = 0$$$ for all $$$1 \le i \le N$$$.

Write a program that processes the $$$Q$$$ following queries:

• 1 u: Add $$$1$$$ to $$$A[i]$$$ for all vertices $$$i$$$ in the subtree rooted at vertex $$$u$$$.
• 2 u v: Add $$$1$$$ to $$$A[i]$$$ for all vertices $$$i$$$ on the unique shortest path between the two vertices $$$u$$$ and $$$v$$$. Note that $$$u$$$ and $$$v$$$ might be equal.

After each query, print the vertex $$$x$$$ that minimizes the quantity $$$\sum_{y = 1}^{N} A[y] \times dist(x, y)$$$, where $$$dist(x, y)$$$ is the number of edges on the path between $$$x$$$ and $$$y$$$. If there is more than one such vertex, print the vertex with minimum distance from the root (vertex 1). It can be proven that such vertex is unique. In other words, we should find a vertex that minimizes the total distance needed for everyone to gather.

Jaemin lives on an infinitely large rectangular grid. Recently, he moved to a new grid, so currently there is only one wall in the grid, which occupies one of the cells.

Each cell has a coordinate determined by the following: the wall is at the coordinate $$$(0,0)$$$. If a cell has coordinate $$$(x,y)$$$, then the cell immediately to the right is $$$(x+1,y)$$$, the cell immediately to the left is $$$(x-1,y)$$$, the cell immediately above is $$$(x,y+1)$$$, and the cell immediately below is $$$(x,y-1)$$$.

Today, he brought his favorite remote-controlled toy car to the grid. The car occupies exactly one cell in the grid. Unfortunately, as this grid is extremely large, he forgot where he put the car. In this case, the only way to move the car is to press a button on the remote control. Upon pressing it, the car will try to execute a predetermined path of $$$N$$$ moves, where each move involves the car trying to move to an adjacent cell in one of the four directions. Note that the car cannot go into the wall; if there is a wall at the cell the car is trying to move to, the car will ignore that command and not move, but will continue to try to execute the moves afterwards.

Since you decided to help him, he will ask you $$$Q$$$ questions of the form: "if my car starts at $$$(x,y)$$$, and I press the button once, where will it end up at?" Can you answer his questions?

Donghyun recently bought a square-shaped tablecloth. There are $$$N$$$ dots on the cloth, and the dots can be seen from both sides of the cloth. Donghyun thought that the tablecloth can be made more beautiful, so he decided to decorate the cloth with sewing.

For convenience, let's assume that each dot is a point on the $$$xy$$$-plane and the dots are numbered from $$$1$$$ to $$$N$$$. Dot $$$i$$$ ($$$1 \le i \le N$$$) is placed at coordinate $$$(x_i, y_i)$$$. No two dots have the same coordinates. A sewing sequence is an integer sequence $$$\{ s_i \}$$$ of length $$$k \geq 2$$$ satisfying $$$1 \le s_i \le N$$$ ($$$1 \le i \le k$$$) and $$$s_i \neq s_{i+1}$$$ ($$$1 \le i \le k-1$$$). The sequence draws edges on the cloth per the following rules:

• Draw an edge connecting dot $$$s_{2i-1}$$$ and dot $$$s_{2i}$$$ on the front side of the cloth for all $$$1 \le i \le \left \lfloor \frac{k}{2} \right \rfloor$$$.
• Draw an edge connecting dot $$$s_{2j}$$$ and dot $$$s_{2j+1}$$$ on the back side of the cloth for all $$$1 \le j \le \left \lfloor \frac{k-1}{2} \right\rfloor$$$.

Donghyun wants to make a beautiful pattern on the tablecloth, which is defined as the following:

• For both sides of the cloth, all $$$N$$$ dots are connected by the edges on that side.
• Two edges on the same side of the cloth can intersect only at a common endpoint.

Donghyun is very busy, so he wants to finish his sewing job as quickly as possible. In other words, over all sewing sequences that produces a beautiful pattern, Donghyun decides to choose the shortest such sequence. Your job is to find such a sequence.

Note that Donghyun wants to minimize the length of the sewing sequence itself, not the sum of the lengths of the edges he draws.

ISCO(ICPC Steel Company) is a company that buys steel sheets of a certain shape, cuts them into pieces, and sells them in the industry market. Every steel sheet that ISCO buys has a shape of two histograms of equal width, where one histogram is reflected vertically and soldered to the bottom of the other histogram. This process forms a polygon without holes such that each side is either horizontal or vertical. We call such a polygon a histogon. See the below figure for a histogon.

Since the market price of a piece becomes much higher if the steel piece is rectangular, it is desirable to cut a steel sheet into several rectangles. To achieve this, you will use a laser cutter.

In a single operation, the laser cutter can trace either a horizontal segment or a vertical segment through a polygon that touches the border of the polygon at exactly two points, the two endpoints of the segment. After the move, the polygon will be cut into two smaller polygons per the path the laser cutter traced. Note that the laser cutter can only operate on a single polygon in one operation.

The laser cutter is expensive to use, so your task is to find the minimum number of laser cutter operations needed such that after all the operations, all of the resulting polygons are rectangles.