There are two multisets $$$U$$$ and $$$V$$$ that contain two-dimensional points with integer coordinates.

We will define the following function $$$D(U, V)$$$ for a pair of multisets:

• $$$D(U, V) = -1$$$ if either set is empty.
• $$$D(U, V) = \min\limits_{\begin{smallmatrix}(u_x, u_y) \in U \\ (v_x, v_y) \in V\end{smallmatrix}}\max(u_x + v_x, u_y + v_y)$$$ otherwise.

In the beginning, both $$$U$$$ and $$$V$$$ are empty. Process $$$Q$$$ queries of the following form:

• "1 $$$s$$$ $$$x$$$ $$$y$$$": Add a point $$$(x, y)$$$ to one of the sets. If $$$s = 1$$$, add the point to $$$U$$$. Otherwise, add the point to $$$V$$$.
• "2 $$$s$$$ $$$x$$$ $$$y$$$": Delete a point $$$(x, y)$$$ from one of the sets. If $$$s = 1$$$, delete the point from $$$U$$$. Otherwise, delete the point from $$$V$$$.

When deleting a point, if there are multiple points at the given coordinates, you should delete only one of them. It is guaranteed that the given point exists in the given multiset at the time of each deletion.

Your task is to process the queries. After each query, print the value $$$D(U, V)$$$.

Bingo is a game on a square grid. Each player gets an $$$n \times n$$$ grid and writes a unique number in each cell. The game host then draws a random number, and each player looks for that number on their grid and, if the number is present on their grid, fills in the corresponding cell. This repeats until someone finds $$$n$$$ filled cells on a single line, which we will call a bingo line.

There are $$$2n + 2$$$ possible bingo lines: $$$n$$$ horizontal lines, $$$n$$$ vertical lines, and $$$2$$$ diagonal lines.

—  ...  ...  |..  .|.  ..|  ..  ../
...  —  ...  |..  .|.  ..|  ..  ./.
...  ...  —  |..  .|.  ..|  ..  /..

For example, the following grid has four bingo lines: two horizontal lines, one vertical line, and one diagonal line.

#..#.
#####
..###
#####
..###

Exactly when is a bingo line formed? That is completely random: you can get a line quite early if you are lucky, but on the other hand, you can fill most of the grid without getting any bingo lines. In this problem, we investigate the unfortunate case of filling $$$k$$$ cells without making any bingo lines.

Given two integers $$$n$$$ and $$$k$$$, determine whether it is possible to fill exactly $$$k$$$ cells in an $$$n \times n$$$ grid, without making any bingo lines. If it is possible, demonstrate how to do it.

For two nonnegative integers $$$a, b$$$, let $$$a \wedge b$$$ be their bitwise AND, and $$$a \vee b$$$ be their bitwise OR.

You are given an array $$$A_0, A_1, \ldots, A_{2^N - 1}$$$ of length $$$2^N$$$ consisting of nonnegative integers. Please find a pair of indices $$$0 \le i, j \le 2^N - 1$$$ such that $$$A_{i} + A_{j} \lt A_{i \wedge j} + A_{i \vee j}$$$, or state that no such pair exists. If there is more than one such pair, find any one of them.

There is a two-person video game about destroying buildings in a ruined city. In the game, there are $$$N$$$ buildings over flat ground. Buildings are indexed from $$$1$$$ to $$$N$$$ from left to right. The height of building $$$i$$$ is $$$A_i$$$ ($$$1 \le i \le N$$$), which is a positive integer between $$$1$$$ and $$$N$$$. No two buildings have the same height.

Initially, both players are to the left of all buildings. At every integer moment $$$i$$$($$$\ge 1$$$), both players fire one shot each at the same time, and the bullets fly horizontally to the right from where they were fired. Both bullets have the same speed. The player selects the bullet's firing height as the distance $$$H$$$ from the ground. The height $$$H$$$ is an integer between $$$1$$$ and $$$N + 1$$$. Both players can choose the same height.

If a player's bullet firing height is $$$H$$$, the leftmost building that satisfies $$$A_i \ge H$$$ and has not yet been destroyed will be destroyed by this bullet. If no building satisfies this condition, nothing happens. If both players hit the same building, only that one building is destroyed. For example, if $$$A_1 = 2$$$, $$$A_2 = 1$$$, and both players initially set $$$H = 1$$$ as the firing height, building 1 will be destroyed, but building 2 will stay in place.

Given the heights of $$$N$$$ buildings, find the minimum time to destroy all the buildings, and provide any sequence of firing heights that achieves this.

You are given $$$N$$$ closed intervals. The $$$i$$$-th interval covers $$$[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 wants the graph to not have a connected component of size greater than $$$K$$$. 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 that minimizes the weight of the intervals he has to delete. Print the weight of the deleted intervals after he has made sure all connected components of the interval graph have size at most $$$K$$$.

You are using Paint on an old Windows computer. The screen of Paint is a grid with cells called pixels. The coordinates of the bottom left pixel are $$$(1, 1)$$$, and the coordinates of the pixel that is in $$$a$$$-th column from the left and $$$b$$$-th row from the bottom are $$$(a, b)$$$. On the initial screen, $$$N$$$ rectangles with vertical and horizontal sides are drawn. A rectangle with bottom left pixel $$$(x_1, y_1)$$$ and top right pixel $$$(x_2, y_2)$$$ contains all pixels $$$(x, y)$$$ such that $$$x_1 \le x \le x_2$$$ and $$$y_1 \le y \le y_2$$$.

A total of $$$M$$$ move commands will be performed on $$$N$$$ rectangles. The movement of the rectangle is represented by direction and distance. Each direction is one of the following: east, west, south, north, northeast, northwest, southeast, and southwest (the latter four are 45 degrees to the horizontal axis). Each distance is a positive integer $$$d$$$.

Suppose that the original coordinates of the bottom left pixel of the rectangle are $$$(a, b)$$$. A movement by a distance of $$$d$$$ in the east, north, west, and south directions causes this pixel to move toward the coordinates $$$(a+d, b)$$$, $$$(a, b+d)$$$, $$$(a-d, b)$$$, and $$$(a, b-d)$$$, respectively. In addition, a movement by a distance of $$$d$$$ in the northeast, northwest, southwest, and southeast directions causes this pixel to move toward the coordinates $$$(a+d, b+d)$$$, $$$(a-d, b+d)$$$, $$$(a-d, b-d)$$$, and $$$(a+d, b-d)$$$, respectively.

Moving by distance $$$d$$$ of the rectangle $$$R$$$ on the screen is implemented by quickly displaying the shape of $$$R$$$ every time when $$$R$$$ moves by distance 1. However, our computer is very old, so moving $$$R$$$ is very laggy. As a result, all of the $$$R$$$ drawn in the movement of $$$R$$$ remains on the screen. Therefore, if $$$R$$$ moves by the distance $$$d$$$, $$$d$$$ rectangles are newly created on the screen. For example, if the rectangle moves in the northeast direction by a distance of 3, 3 rectangles are created, leaving a total of 4 rectangles on the screen. Of course, after moving, the rectangle at the northeast end becomes $$$R$$$.

After executing $$$M$$$ move commands, $$$Q$$$ queries will be given. Each query is given as a pixel $$$p$$$ on the plane. Print the number of rectangles containing the pixel $$$p$$$ as the answer to the query.

You are given a connected undirected graph $$$G$$$ with $$$N$$$ vertices and $$$M$$$ edges where vertices are numbered from $$$1$$$ to $$$N$$$ and edges are numbered from $$$1$$$ to $$$M$$$.

For each vertex $$$v$$$, if the graph is disconnected after the vertex $$$v$$$ is removed, we call $$$v$$$ a critical vertex. Note that the original connectedness of the graph does not matter.

For each $$$i$$$ ($$$1 \le i \le M$$$), please compute the number of critical vertices in $$$G$$$ when edge $$$i$$$ is removed. Note that the removal is only temporary, and does not affect other queries.

Whenever students of KAIST go outside of campus, they usually follow a straight road named the Endless Road. The name comes from the fact that most students feel like the road is endless. One factor for this is due to the boring scenery of the road. Here, we model the Endless Road as a straight line of length $$$10^9$$$. The position over the straight line can be denoted as a single real number $$$x \in [0, 10^9)$$$.

To cope with this, the members of RUN@KAIST decided to plant different kinds of colorful flowers along this road. The $$$N$$$ members of RUN@KAIST are numbered from $$$1$$$ to $$$N$$$. In the last regular meeting, each member was assigned a nonempty segment $$$[L_i, R_i)$$$ over the straight line, containing all positions $$$x$$$ such that $$$L_i \le x \lt R_i$$$.

The members with higher indices bear more responsibility for the tasks on the club. Thus, the length of the segments is nondecreasing as the indices of the members increase. In other words, $$$R_i - L_i \leq R_j - L_j$$$ for $$$1 \le i \lt j \le N$$$.

The planting is done in $$$N$$$ turns. In each turn, we select one previously unselected member to plant flowers. The selected member plants the flowers in their assigned segment $$$[L_i, R_i)$$$, except where other members have already planted flowers before.

To make the work distribution more equitable, the selection is done in the following way:

• Pick the member who will plant the minimum number of flowers. Here, the number of flowers is determined by the total length of the intervals where this member will plant new flowers, which could be zero.
• If there is more than one such member, pick the member with minimum index.

Jaeung should now announce the planting schedule. For this, he has to find an order in which the $$$N$$$ members will plant the flowers, according to the above selection rules. Please help him do it.

There are $$$N$$$ streetlights along the straight road. The initial height of the $$$i$$$-th streetlight is a positive integer $$$A_i$$$ $$$(1 \le i \le N)$$$.

You are trying to install an electric wire between two streetlights. To install an electric wire between the streetlights $$$i$$$ and $$$j( \gt i)$$$, the following conditions must be satisfied:

• $$$A_i = A_j$$$,
• For every $$$i \lt k \lt j$$$, $$$A_k \lt A_i$$$.

The city may adjust the height of a streetlight $$$Q$$$ times. Each adjustment is given as a pair of positive integers $$$(x, h)$$$, which indicates that the height of $$$x$$$-th streetlight was adjusted to $$$h$$$. In other words, $$$A_x = h$$$.

Before the updates, and also after each update, find the number of pairs $$$1 \le i \lt j \le N$$$ such that you can install an electric wire between streetlights $$$i$$$ and $$$j$$$.

For an unweighted tree $$$T$$$, a simple path $$$P$$$ is a diameter if there is no simple path longer than it. Two paths are different if some vertex is in one path but not the other.

Consider a set of paths $$$D_T$$$ where $$$P \in D_T$$$ if and only if $$$P$$$ is a diameter. Given two paths $$$D$$$ and $$$E$$$, let $$$f(D, E)$$$ be the number of vertices that belong to both $$$D$$$ and $$$E$$$.

You are given an undirected forest (a graph with no cycles) with $$$N$$$ vertices and $$$M$$$ edges. Process $$$Q$$$ queries of the following form:

• "1 $$$x$$$ $$$y$$$": Connect two vertices $$$x$$$ and $$$y$$$ with an edge ($$$1 \le x, y \le N$$$). It is guaranteed that there is no path between $$$x$$$ and $$$y$$$ at the time of the query.
• "2 $$$x$$$ $$$y$$$": Remove an edge between two vertices $$$x$$$ and $$$y$$$ ($$$1 \le x, y \le N$$$). It is guaranteed that such an edge exists at the time of the query.
• "3 $$$x$$$": Let $$$F$$$ be the connected component containing the vertex $$$x$$$. Output the value $$$\sum\limits_{D \in D_F} \sum\limits_{E \in D_F} f(D, E)$$$ modulo $$$10^9 + 7$$$ ($$$1 \le x \le N$$$).

You are given a tree with $$$N$$$ vertices numbered from $$$1$$$ to $$$N$$$. The tree is vertex-weighted. In other words, each vertex of the tree is assigned a nonnegative integer weight.

We will delete some edges from the tree. After the deletion, for each connected component, the sum of vertex weights should be in the range $$$[L, R]$$$.

For all integers $$$0 \le i \le K$$$, determine if we can achieve this goal by deleting exactly $$$i$$$ edges.

You are creating a new KartRider racetrack. The racetrack is a $$$H \times W$$$ rectangular board. Each cell of the board is either empty, or contains a tile which is described in the picture below.

Note that each of the tiles can be rotated, and all except one have roads going out of the tile. We denote the fourth type of tile (highlighted in blue color) as a curly tile.

In a valid KartRider racetrack, every cell should contain a tile, and there should be no dead-ends over the roads in the tile. In other words, each road going out of the tile should be connected to a road on the neighboring tile. Also, the road should not face outside the board.

Currently, there are some curly tiles already placed on the board. You can place zero or more curly tiles on the board and submit the racetrack. Then, the administrator will try to fill all empty cells with tiles (not necessarily curly) with their best effort, so that it becomes a valid KartRider racetrack. Note that you can only place the curly tiles, and you should not remove, replace, or rotate the curly tiles already placed in the board.

Additionally, for some cells, you can not place the tiles, and for some cells, you must place the curly tiles.

Please find the maximum possible number of curly tiles you can place in the racetrack so that the administrator can fill the remaining cells to create a valid KartRider racetrack. You should report the total number of curly tiles in the racetrack, not the number of curly tiles you have newly added. If there is no way to create a valid KartRider racetrack, print $$$-1$$$.