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.

In Byteland, there is a school with an enormously large playground. The playground is an $$$N \times M$$$ grid. Since the playground is so large, the weather may differ in different squares of the grid. For $$$1 \le i \le N, 1 \le j \le M$$$, cell $$$(i, j)$$$ has a temperature of $$$A_i + B_j$$$. The sequences $$$A$$$ and $$$B$$$ are known in advance.

Sunghyeon wants to organize a relay race competition in the playground. The race will start in cell $$$(S, 1)$$$ and end in cell $$$(T, M)$$$, where $$$S$$$ and $$$T$$$ are integers that are to be determined. In the race, students will only run to the right and down. In other words, a student in cell $$$(i, j)$$$ can move directly to cells $$$(i, j + 1)$$$ or $$$(i + 1, j)$$$. From this, it is clear that $$$1 \le S \le T \le N$$$ must hold for the race to be valid.

The people of Byteland love cacti. Therefore, all students will hold a cactus while in the race. Since cacti can't endure cold weather, all cells in the racetrack should satisfy $$$A_i + B_j \geq 0$$$.

There are $$$\frac{N(N+1)}{2}$$$ candidate races over all candidate pairs of $$$S$$$ and $$$T$$$. Please find the number of valid pairs - a pair is valid if the corresponding race can be completed given the constraints due to the cacti.

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.

SNUPS is the programming contest club of Seoul National University. There are $$$N$$$ members in the club, and for every two distinct members $$$1 \le i, j \le N, i \neq j$$$, we define the friend distance $$$C(i, j)$$$. The friend distance is symmetric ($$$C(i, j) = C(j, i)$$$ for all $$$i \neq j$$$), and is an integer in range $$$[1, 10^7]$$$. The smaller the friend distance is, the more friendly two members are toe each other.

When there is an agenda to discuss in SNUPS, they select three distinct members uniformly at random and the three members hold a discussion. However, if $$$C(i, j) \lt C(j, k)$$$ and $$$C(i, j) \lt C(i, k)$$$ for the three members $$$i, j, k$$$ in discussion, then members $$$i$$$ and $$$j$$$ may collude and ignore member $$$k$$$. We call this an unjust meeting.

Currently, there are $$$M$$$ pairs of friends, and their friend distance can not be changed. All other pairs of members can have their friend distances changed. Sunghyeon will hold a party for the SNUPS members and change the friend distances for all of these pairs. After the party, the friend distance should satisfy the symmetry condition and should be an integer in range $$$[1, 10^7]$$$.

Sunghyeon wants to know if he can set the friend distance in such a way that it is impossible to have an unjust meeting. If this is possible, he also wants to minimize $$$\sum_{i=1}^{N}{\sum_{j=i+1}^{N}{C(i,j)}}$$$ in order to make the club as friendly as possible.

Changki Yun is a professor in the Department of Chemistry, Seoul National University. To fight the ongoing COVID-19 pandemic, Changki conducts research on a certain molecule.

The molecule consists of $$$N$$$ atoms with $$$M$$$ chemical bonds, which we will simply consider as an undirected graph without self-loops or parallel edges. Note that, unlike real-life chemistry, it is not guaranteed that the molecule is connected, or that atoms in the molecule have degree at most 4.

Changki can use a machine to change the molecule. When Changki enters two integers $$$1 \le L \le R \le N$$$, the machine will keep only atoms in the range $$$L, L+1, \cdots, R$$$, as well as any bonds that were only between kept atoms.

Changki thinks that molecules which form chains are crucial to his research. A molecule forms a chain if you can place the atoms in a line such that a chemical bond between two atoms exists if and only if they are adjacent on the line. Please count the number of pairs $$$(L, R)$$$ which can be put in the machine to form a chain.

You are given $$$N$$$ closed intervals. The $$$i$$$-th interval has the range $$$[s_i, e_i]$$$, and has a positive integer weight $$$w_i$$$. Consider the undirected graph of $$$N$$$ vertices, where each vertex corresponds to an interval, and there exists an edge between two vertices if and only if the corresponding pair of intervals has a nonempty intersection. For a given list of intervals, we call this graph the interval graph.

Jaehyun is addicted to problems about trees and queries, so he wants the graph to be acyclic. To accomplish this, he can delete zero or more intervals. Jaehyun is lazy, so over all possible ways to delete intervals, he will select the way which minimizes the weight of the intervals he has to delete. Print the weight of the remaining intervals after he has made the interval graph acyclic.

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$$$.

Jeyeon the alchemist has obtained the philosopher's stone which can transform one or more materials into a single material of a different type. Now he is trying to obtain the most valuable material in the universe. Every material in the world has a value corresponding to some nonnegative integer, and two materials are different in type if and only if they differ in value.

The philosopher's stone can consume $$$k$$$ ($$$k \geq 1$$$) materials, the $$$i$$$th having value $$$x_i$$$, and generates a material that was not among the consumed values. Over all such materials, the philosopher's stone will generate the material with minimum value, also known as the mex of the original values. It is allowed to consume multiple materials of the same value.

Jeyeon starts out with some elements with values varying from $$$0$$$ to $$$N-1$$$. Specifically, he has $$$c_i$$$ materials with value $$$i$$$. He will use the philosopher's stone zero or more times. In the end, Jeyeon wants to own exactly one material. Jeyeon wants to maximize the value of this single material. Can you calculate this value for him? Note that the value of this material may be greater than or equal to $$$N$$$.

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.