Let's call a sequence $$$b_1, b_2, b_3 \dots, b_{k - 1}, b_k$$$ almost increasing if $$$$$$\min(b_1, b_2) \le \min(b_2, b_3) \le \dots \le \min(b_{k - 1}, b_k).$$$$$$ In particular, any sequence with no more than two elements is almost increasing.

You are given a sequence of integers $$$a_1, a_2, \dots, a_n$$$. Calculate the length of its longest almost increasing subsequence.

You'll be given $$$t$$$ test cases. Solve each test case independently.

Reminder: a subsequence is a sequence that can be derived from another sequence by deleting some elements without changing the order of the remaining elements.

Monocarp would like to open a bakery in his local area. But, at first, he should figure out whether he can compete with other shops.

Monocarp plans that the bakery will work for $$$n$$$ days. On the $$$i$$$-th day, $$$a_i$$$ loaves of bread will be baked in the morning before the opening. At the end of the $$$n$$$-th day, Monocarp will sell all the remaining bread that wasn't sold earlier with a huge discount.

Because of how bread is stored, the bakery seller sells the bread in the following order: firstly, he sells the loaves that were baked that morning; secondly, he sells the loaves that were baked the day before and weren't sold yet; then the loaves that were baked two days before and weren't sold yet, and so on. That's why some customers may buy a rather stale bread and will definitely spread negative rumors.

Let's define loaf spoilage as the difference between the day it was baked and the day it was sold. Then the unattractiveness of the bakery will be equal to the maximum spoilage among all loaves of bread baked at the bakery.

Suppose Monocarp's local area has consumer demand equal to $$$k$$$, it means that each day $$$k$$$ customers will come to the bakery and each of them will ask for one loaf of bread (the loaves are sold according to the aforementioned order). If there is no bread left, then the person just doesn't buy anything. During the last day sale, all the remaining loaves will be sold (and they will still count in the calculation of the unattractiveness).

Monocarp analyzed his competitors' data and came up with $$$m$$$ possible consumer demand values $$$k_1, k_2, \dots, k_m$$$, and now he'd like to calculate the unattractiveness of the bakery for each value of demand. Can you help him?

Monocarp and Polycarp are working as waiters in Berpizza, a pizzeria located near the center of Bertown. Since they are waiters, their job is to serve the customers, but they choose whom they serve first differently.

At the start of the working day, there are no customers at the Berpizza. They come there one by one. When a customer comes into the pizzeria, she sits and waits for Monocarp or Polycarp to serve her. Monocarp has been working in Berpizza for just two weeks, so whenever he serves a customer, he simply chooses the one who came to Berpizza first, and serves that customer.

On the other hand, Polycarp is an experienced waiter at Berpizza, and he knows which customers are going to spend a lot of money at the pizzeria (and which aren't) as soon as he sees them. For each customer, Polycarp estimates the amount of money this customer can spend, and when he serves a customer, he chooses the one that is expected to leave the most money at Berpizza (in case there are several such customers, he chooses the one who came first among them).

Obviously, no customer can be served twice, so Monocarp and Polycarp choose which customer to serve only among those who haven't been served yet.

When the number of customers gets really high, it becomes difficult for both Monocarp and Polycarp to choose the customer they are going to serve. Your task is to write a program that makes these choices for them. Formally, your program should be able to process three types of queries:

• $$$1$$$ $$$m$$$ — a customer comes to Berpizza, and Polycarp estimates the amount of money that they will spend as $$$m$$$;
• $$$2$$$ — Monocarp serves a customer which came to the pizzeria first;
• $$$3$$$ — Polycarp serves a customer which is expected to spend the largest amount of money at the pizzeria (if there are several such customers, the one that came to the pizzeria first is chosen).

For each query of types $$$2$$$ and $$$3$$$, report the number of the customer who was served (the customers are numbered in the order they come to the pizzeria, starting from $$$1$$$).

Consider a long corridor which can be divided into $$$n$$$ square cells of size $$$1 \times 1$$$. These cells are numbered from $$$1$$$ to $$$n$$$ from left to right.

There are two people in this corridor, a hooligan and a security guard. Initially, the hooligan is in the $$$a$$$-th cell, the guard is in the $$$b$$$-th cell ($$$a \ne b$$$).

One of the possible situations. The corridor consists of $$$7$$$ cells, the hooligan is in the $$$3$$$-rd cell, the guard is in the $$$6$$$-th ($$$n = 7$$$, $$$a = 3$$$, $$$b = 6$$$).

There are $$$m$$$ firecrackers in the hooligan's pocket, the $$$i$$$-th firecracker explodes in $$$s_i$$$ seconds after being lit.

The following events happen each second (sequentially, exactly in the following order):

1. firstly, the hooligan either moves into an adjacent cell (from the cell $$$i$$$, he can move to the cell $$$(i + 1)$$$ or to the cell $$$(i - 1)$$$, and he cannot leave the corridor) or stays in the cell he is currently. If the hooligan doesn't move, he can light one of his firecrackers and drop it. The hooligan can't move into the cell where the guard is;
2. secondly, some firecrackers that were already dropped may explode. Formally, if the firecracker $$$j$$$ is dropped on the $$$T$$$-th second, then it will explode on the $$$(T + s_j)$$$-th second (for example, if a firecracker with $$$s_j = 2$$$ is dropped on the $$$4$$$-th second, it explodes on the $$$6$$$-th second);
3. finally, the guard moves one cell closer to the hooligan. If the guard moves to the cell where the hooligan is, the hooligan is caught.

Obviously, the hooligan will be caught sooner or later, since the corridor is finite. His goal is to see the maximum number of firecrackers explode before he is caught; that is, he will act in order to maximize the number of firecrackers that explodes before he is caught.

Your task is to calculate the number of such firecrackers, if the hooligan acts optimally.

Monocarp wants to draw four line segments on a sheet of paper. He wants the $$$i$$$-th segment to have its length equal to $$$a_i$$$ ($$$1 \le i \le 4$$$). These segments can intersect with each other, and each segment should be either horizontal or vertical.

Monocarp wants to draw the segments in such a way that they enclose a rectangular space, and the area of that rectangular space should be maximum possible.

For example, if Monocarp wants to draw four segments with lengths $$$1$$$, $$$2$$$, $$$3$$$ and $$$4$$$, he can do it the following way:

Here, Monocarp has drawn segments $$$AB$$$ (with length $$$1$$$), $$$CD$$$ (with length $$$2$$$), $$$BC$$$ (with length $$$3$$$) and $$$EF$$$ (with length $$$4$$$). He got a rectangle $$$ABCF$$$ with area equal to $$$3$$$ that is enclosed by the segments.

Calculate the maximum area of a rectangle Monocarp can enclose with four segments.

There are $$$n$$$ persons located on a plane. The $$$i$$$-th person is located at the point $$$(x_i, y_i)$$$ and initially looks at the point $$$(u_i, v_i)$$$.

At the same moment of time, all persons will start to rotate clockwise synchronously with the same angular speed. They will rotate until they do one full $$$360$$$-degree turn.

It is said that persons $$$A$$$ and $$$B$$$ made eye contact if person $$$A$$$ looks in person $$$B$$$'s direction at the same moment when person $$$B$$$ looks in person $$$A$$$'s direction. If there is a person $$$C$$$ located between persons $$$A$$$ and $$$B$$$, that will not obstruct $$$A$$$ and $$$B$$$ from making eye contact. A person can make eye contact with more than one person at the same time.

Calculate the number of pairs of persons that will make eye contact at least once during the rotation (including the initial moment).

The hobbits Frodo and Sam are carrying the One Ring to Mordor. In order not to be spotted by orcs, they decided to go through the mountains.

The mountain relief can be represented as a polyline with $$$n$$$ points $$$(x_i, y_i)$$$, numbered from $$$1$$$ to $$$n$$$ ($$$x_i \lt x_{i + 1}$$$ for $$$1 \le i \le n - 1$$$). Hobbits start their journey at the point $$$(x_1, y_1)$$$ and should reach the point $$$(x_n, y_n)$$$ to complete their mission.

The problem is that there is a tower with the Eye of Sauron, which watches them. The tower is located at the point $$$(x_n, y_n)$$$ and has the height $$$H$$$, so the Eye is located at the point $$$(x_n, y_n + H)$$$. In order to complete the mission successfully, the hobbits have to wear cloaks all the time when the Sauron Eye can see them, i. e. when there is a direct line from the Eye to the hobbits which is not intersected by the relief.

The hobbits are low, so their height can be considered negligibly small, but still positive, so when a direct line from the Sauron Eye to the hobbits only touches the relief, the Eye can see them.

The Sauron Eye can't see hobbits when they are in the left position, but can see them when they are in the right position.

The hobbits do not like to wear cloaks, so they wear them only when they can be spotted by the Eye. Your task is to calculate the total distance the hobbits have to walk while wearing cloaks.

Let's denote the median of a sequence $$$s$$$ with odd length as the value in the middle of $$$s$$$ if we sort $$$s$$$ in non-decreasing order. For example, let $$$s = [1, 2, 5, 7, 2, 3, 12]$$$. After sorting, we get sequence $$$[1, 2, 2, \underline{3}, 5, 7, 12]$$$, and the median is equal to $$$3$$$.

You have a sequence of $$$n$$$ integers $$$[1, 2, \dots, n]$$$ and an odd integer $$$k$$$.

In one step, you choose any $$$k$$$ elements from the sequence and erase all chosen elements except their median. These elements do not have to go continuously (gaps are allowed between them).

For example, if you have a sequence $$$[1, 2, 3, 4, 5, 6, 7]$$$ (i.e. $$$n=7$$$) and $$$k = 3$$$, then the following options for the first step are possible:

• choose $$$[1, \underline{2}, 3]$$$; $$$2$$$ is their median, so it is not erased, and the resulting sequence is $$$[2, 4, 5, 6, 7]$$$;
• choose $$$[2, \underline{4}, 6]$$$; $$$4$$$ is their median, so it is not erased, and the resulting sequence is $$$[1, 3, 4, 5, 7]$$$;
• choose $$$[1, \underline{6}, 7]$$$; $$$6$$$ is their median, so it is not erased, and the resulting sequence is $$$[2, 3, 4, 5, 6]$$$;
• and several others.

You can do zero or more steps. Can you get a sequence $$$b_1$$$, $$$b_2$$$, ..., $$$b_m$$$ after several steps?

You'll be given $$$t$$$ test cases. Solve each test case independently.

You are given five integers $$$n$$$, $$$dx_1$$$, $$$dy_1$$$, $$$dx_2$$$ and $$$dy_2$$$. You have to select $$$n$$$ distinct pairs of integers $$$(x_i, y_i)$$$ in such a way that, for every possible pair of integers $$$(x, y)$$$, there exists exactly one triple of integers $$$(a, b, i)$$$ meeting the following constraints:

There are $$$n$$$ cities and $$$m$$$ bidirectional roads in Berland. The $$$i$$$-th road connects the cities $$$x_i$$$ and $$$y_i$$$, and has the speed limit $$$s_i$$$. The road network allows everyone to get from any city to any other city.

The Berland Transport Ministry is planning a road reform.

First of all, maintaining all $$$m$$$ roads is too costly, so $$$m - (n - 1)$$$ roads will be demolished in such a way that the remaining $$$(n - 1)$$$ roads still allow to get to any city from any other city. Formally, the remaining roads should represent an undirected tree.

Secondly, the speed limits on the remaining roads might be changed. The changes will be done sequentially, each change is either increasing the speed limit on some road by $$$1$$$, or decreasing it by $$$1$$$. Since changing the speed limit requires a lot of work, the Ministry wants to minimize the number of changes.

The goal of the Ministry is to have a road network of $$$(n - 1)$$$ roads with the maximum speed limit over all roads equal to exactly $$$k$$$. They assigned you the task of calculating the minimum number of speed limit changes they have to perform so the road network meets their requirements.

For example, suppose the initial map of Berland looks like that, and $$$k = 7$$$:

Then one of the optimal courses of action is to demolish the roads $$$1$$$–$$$4$$$ and $$$3$$$–$$$4$$$, and then decrease the speed limit on the road $$$2$$$–$$$3$$$ by $$$1$$$, so the resulting road network looks like that:

There is a robot on a checkered field that is endless in all directions. Initially, the robot is located in the cell with coordinates $$$(0, 0)$$$. He will execute commands which are described by a string of capital Latin letters 'L', 'R', 'D', 'U'. When a command is executed, the robot simply moves in the corresponding direction:

• 'L': one cell to the left (the $$$x$$$-coordinate of the current cell decreases by $$$1$$$);
• 'R': one cell to the right (the $$$x$$$-coordinate of the current cell is increased by $$$1$$$);
• 'D': one cell down (the $$$y$$$-coordinate of the current cell decreases by $$$1$$$);
• 'U': one cell up (the $$$y$$$-coordinate of the current cell is increased by $$$1$$$).

Your task is to put an obstacle in one cell of the field so that after executing the commands, the robot will return to the original cell of its path $$$(0, 0)$$$. Of course, an obstacle cannot be placed in the starting cell $$$(0, 0)$$$. It is guaranteed that if the obstacle is not placed, then the robot will not return to the starting cell.

An obstacle affects the movement of the robot in the following way: if it tries to go in a certain direction, and there is an obstacle, then it simply remains in place (the obstacle also remains, that is, it does not disappear).

Find any such cell of the field (other than $$$(0, 0)$$$) that if you put an obstacle there, the robot will return to the cell $$$(0, 0)$$$ after the execution of all commands. If there is no solution, then report it.

Suppose you have a sequence of $$$k$$$ integers $$$A = [a_1, a_2, \dots , a_k]$$$ where each $$$a_i \geq 2$$$. A sequence of prime integers $$$P = [p_1, p_2, \dots, p_k]$$$ is called suitable for the sequence $$$A$$$ if $$$a_1$$$ is divisible by $$$p_1$$$, $$$a_2$$$ is divisible by $$$p_2$$$ and so on.

A sequence of prime integers $$$P$$$ is called friendly if there are no unique integers in this sequence.

A sequence $$$A$$$ is called ideal, if each sequence $$$P$$$ that is suitable for $$$A$$$ is friendly as well (i. e. there is no sequence $$$P$$$ that is suitable for $$$A$$$, but not friendly). For example, the sequence $$$[2, 4, 16]$$$ is ideal, while the sequence $$$[2, 4, 6]$$$ is not ideal (there exists a sequence $$$P = [2, 2, 3]$$$ which is suitable for $$$A$$$, but not friendly).

You are given $$$n$$$ different integers $$$x_1$$$, $$$x_2$$$, ..., $$$x_n$$$. You have to choose exactly $$$k$$$ of them in such a way that they form an ideal sequence, or report that it is impossible. Note that no integer can be chosen more than once.

You are given $$$n$$$ sets of integers. The $$$i$$$-th set contains $$$k_i$$$ integers.

Two sets are called similar if they share at least two common elements, i. e. there exist two integers $$$x$$$ and $$$y$$$ such that $$$x \ne y$$$, and they both belong to each of the two sets.

Your task is to find two similar sets among the given ones, or report that there is no such pair of sets.

The progress is not standing still in Berland. Recently all garbage containers in Bertown, the capital of Berland, were replaced by differentiated recycling bins, each accepting some category of waste. While this will definitely improve the ecological situation, for some citizens it's difficult to get used to the habit of sorting waste.

Monocarp is one of those citizens who tries to get used to waste sorting. Today he has to take out the trash from his house. There are three containers near the Monocarp's house, the first one accepts paper waste, the second one accepts plastic waste, and the third one — all other types of waste. It is possible to fit $$$c_1$$$ items into the first container, $$$c_2$$$ items into the second container and $$$c_3$$$ items into the third container.

Monocarp has a lot of items to throw into containers. Some are made of paper, so Monocarp has to put them into the first container (he has $$$a_1$$$ such items), some are made of plastic, so he has to put them into the second container (he has $$$a_2$$$ such items), and some are neither paper nor plastic — so Monocarp has to put them into the third container (he has $$$a_3$$$ such items).

Unfortunately, there are also two categories of items that Monocarp is unsure of: he has $$$a_4$$$ items which are partially made of paper, so he will put each of these items either into the first container or into the third container. Similarly, he has $$$a_5$$$ items partially made of plastic, so he has to put each of them either into the second container or into the third container. Obviously, this choice is made separately for each item — for example, Monocarp can throw several partially-plastic items into the second container, and all other partially-plastic items — into the third one.

Now Monocarp wonders: is it possible to put each item into some container so that the first container will hold no more than $$$c_1$$$ items, the second one — no more than $$$c_2$$$ items, and the third one — no more than $$$c_3$$$ items?