Do you know Dumae? It is a nickname of the most famous restaurant nearby KAIST, Dumae Charcoal-grilled Barbecue. Because Dumae is a very famous restaurant, lots of KAIST students stand in line even though it has not opened yet. Students wonder how long they have to wait, so they started to guess their order.

There are N students in waiting line and each of them has a distinct student ID from 1 to N. Student i (student with student ID i) guessed that he/she is either L_i-th, (L_i + 1)-th, ..., (R_i - 1)-th, or R_i-th person in the line. (i.e. the number of people standing relatively in front of him/her is in the interval ) Also, M claims are made, of which the i-th says that student v_i can see student u_i in the waiting line. It means student u_i is relatively in front of student v_i.

You wonder if all of students' guesses and claims were right. Find an order of waiting line that satisfies all the guesses and claims, or report that such an order does not exist.

Joon is taking General Physics II and he is now studying electronic circuits. An electronic circuit consists of several nodes and undirected wires each connecting two distinct nodes. Moreover, a circuit has two distinctive end nodes; a source node and a sink node, where a voltage is applied (usually it is applied by additional wire with a battery connecting the two nodes, but we will neglect it). Each wire has a resistance, and Joon should know how to calculate the composite resistance of a circuit.

By the way, Joon hates complicated things. So he only cares about circuits that can be made by series and parallel compositions, since they are easy to calculate the composite resistance. He calls them 'nice' circuits; formally, a nice circuit can be defined as follows.

• A circuit with a single wire connecting two end nodes is nice.
• A circuit obtained by merging the sink node of a nice circuit $$$C_1$$$ and the source node of a nice circuit $$$C_2$$$ into a single node is nice. The source node and the sink node of the obtained circuit are the source node of $$$C_1$$$ and the sink node of $$$C_2$$$, respectively.
• A circuit obtained by merging the two source nodes of nice circuits $$$C_1$$$ and $$$C_2$$$ into a single node, and merging the two sink nodes of $$$C_1$$$ and $$$C_2$$$ into a single node, is nice. The two end nodes of the obtained circuit are the respective merged end nodes.

He made a circuit with his wires to calculate the composite resistance, but his friend Pringles screwed up his circuit, so now Joon does not know what the end nodes are. To make things worse, he is not even sure whether the circuit is nice or not.

Joon will give you the circuit. He kindly asks you whether the circuit can be nice by appropriately choosing two end nodes. Be careful that there may be multiple wires connecting two nodes.

Tree is a recursive structure, which is either:

• Empty. Empty tree is denoted as $$$-1$$$ and has a size of 0.
• Non-empty. Non-empty tree $$$T$$$ is denoted as a pair of two trees $$$(T_1, T_2)$$$, where $$$T_1$$$ is called left subtree of $$$T$$$, and $$$T_2$$$ is called right subtree of $$$T$$$. If $$$T = (-1, -1)$$$, then we call such $$$T$$$ a leaf. Leaf has a size of 1, and non-leaf has a size of $$$|T_1| + |T_2|$$$, where $$$|T_1|$$$ is the size of $$$T_1$$$, and $$$|T_2|$$$ is the size of $$$T_2$$$.

A non-empty tree $$$T$$$ is a Fake Plastic Tree, if the tree is balanced. Formally, Let $$$T = (T_1, T_2)$$$. If $$$|T_1| = |T_2|$$$ or $$$|T_1| = |T_2| + 1$$$ holds, then $$$T$$$ is a Fake Plastic Tree.

In computer science, trees are commonly used as a data structure, and they are stored in a memory. At first, there are no trees in the memory, and only an imaginary null pointer exists (which corresponds to empty tree, $$$-1$$$). You can allocate a tree in the memory, by setting $$$T_1$$$ and $$$T_2$$$ as either a null pointer or a pointer of an existing tree. Then, the memory is extended by adding $$$T = (T_1, T_2)$$$ into its structure. Note that pointer can be described as a small integer, reducing the need for explicitly storing the whole tree.

Formally, memory $$$M$$$ is an inductive structure, which at first contains only empty tree $$$-1$$$. ($$$M = \{-1\}$$$). You can expand the memory with following operation $$$M \leftarrow M \cup \{(T_1, T_2)\}$$$, where $$$T_1 \in M, T_2 \in M$$$. If a tree $$$T$$$ is inserted in $$$i$$$-th stage, then it has the index $$$i-1$$$. For a tree with index $$$i$$$, their subtrees can be represented as a pair of integer in range $$$[-1, i-1]$$$.

Your task is to construct a memory $$$M$$$, which satisfies the following :

• Every tree in $$$M$$$ is either empty or Fake Plastic Tree.
• $$$M$$$ has at most 125 non-empty trees.
• There exists a tree $$$T \in M$$$, where $$$|T| = N$$$ holds. $$$N$$$ is an integer, and is given as an input.

A street named Fascination Street is divided into $$$N$$$ equal length of blocks. For each block $$$i$$$ ($$$1 \leq i \leq N$$$), it has block $$$i-1$$$ in its left side if $$$i \gt 1$$$, and block $$$i+1$$$ in its right side if $$$i \lt N$$$.

Unlike its name, the street is infamous to be a dark and eerie place in the night. To solve this, Robert decided to install the streetlight for some of the blocks. The cost of installing a streetlight for $$$i$$$-th block is $$$W_i$$$, and the total cost is the sum of each installation cost. After installing, every block should either have a streetlight, or have a streetlight in it's left or right block.

Robert also has some tricks to reduce the cost. Before installing the streetlight, Robert selects two distinct blocks $$$i$$$ and $$$j$$$, and exchange their position. After the operation, the cost of installation is exchanged. In other words, the operation simply swaps the value of $$$W_i$$$ and $$$W_j$$$. This operation have no cost, but Robert can only perform it at most $$$K$$$ times.

Now, given the array $$$W$$$ and the maximum possible number of operations $$$K$$$, you should find the minimum cost of lighting the whole street.

About 44 days are left before College Scholastic Ability Test is held. This exam aims to measure students' achievement of National Curriculum standards and scholastic ability required for college education. (http://www.kice.re.kr/sub/info.do?m=0205&s=english)

One of the subjects covered by this test is Mathematics, which consists of 21 multiple choice questions and 9 short-answer questions. The answer of each short-answer question is guaranteed to be a unique positive integer below 1 000, as you can see from the answer sheet below.

However, the organizers might want to give students short-answer questions with non-integer answers, such as $$$2\sqrt{3}$$$ or $$$\frac{5}{3}$$$. Usually, the workaround is to write the answer in a canonical form, and then sum up all the integers inside that form and ask students to write that number instead.

In particular, when the answer is a positive rational number $$$\frac{a}{b}$$$, the organizers usually ask students to reduce it and sum up the numerator and the denominator of the reduced fraction. For example, when the answer is $$$\frac{18}{10}$$$, the student should reduce it to $$$\frac{9}{5}$$$ and write the final answer as $$$9 + 5 = 14$$$.

However, when the answer is $$$\frac{521}{500}$$$, the reduced fraction is also $$$\frac{521}{500}$$$, so the student should write the final answer as $$$521 + 500 = 1021$$$. But this shouldn't happen, since all the answers for the short-answer questions are below 1 000. To avoid this situation, the organizers should make sure that after reducing the fraction, the sum of the numerator and the denominator shouldn't exceed $$$999$$$. Let's call such fractions as Suneung Fractions. For example, $$$\frac{1996}{2}$$$ and $$$\frac{18}{10}$$$ are Suneung fractions, while $$$\frac{1998}{2}$$$ and $$$\frac{521}{500}$$$ are not.

Suppose that, this year, one of the organizers wrote a problem, and the answer to that problem is $$$\frac{x}{y}$$$. Since the problem is not finalized yet, the only thing we know is $$$A \le x \le B$$$ and $$$C \le y \le D$$$ holds, for given $$$A, B, C, D$$$. The organizers want to know, among all the pairs $$$(x, y)$$$, how many of $$$\frac{x}{y}$$$ is a Suneung fraction. Write a program that counts this number.

You are given $$$N$$$ points on a plane. These points are precisely the set of vertices of some regular $$$N$$$-gon. Koosaga, an extreme villain, is challenging you with a game using these points. You and Koosaga alternatively take turns, and in each turn, the player

1. chooses two of the given points, then
2. draws the line segment connecting the two chosen points.

Given the integer $$$N$$$, Koosaga is letting you decide who will move first. Your task is decide whether you need to move first or the second so that you can win regardless of Koosaga's moves.

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

Figure: This picture depicts a case when $$$N = 9$$$ and $$$H = [7,4,3,5,4,2,5,1,2]$$$.

One day, you wanted to find the area of the largest rectangle contained in the given histogram. What you did was to make a list of integers $$$A$$$ by the following procedure:

• For each $$$1 \le i \le j \le N$$$, calculate the largest area of the rectangle contained in the histogram, where the rectangle's base line coincides with the base line of the $$$i, i+1, \cdots, j-1, j$$$-th bar. Add the area to the list $$$A$$$.

Figure: This picture depicts a case when $$$i = 3$$$ and $$$j = 5$$$. The area is 9.

The length of the list $$$A$$$ is exactly $$$\frac{N(N+1)}{2}$$$ since you chose each pair $$$(i, j)$$$ exactly once. To make your life easier, you sorted the list $$$A$$$ in non-decreasing order. Now, to find the largest area of the rectangle contained in the histogram, you just need to read the last element of $$$A$$$, $$$A_{N(N+1)/2}$$$.

However, you are not satisfied with this at all, so I decided to let you compute some part of the list $$$A$$$. You have to write a program that, given two indices $$$L$$$ and $$$R$$$ ($$$L \le R$$$), calculate the values $$$A_{L..R}$$$, i.e. $$$A_{L}, A_{L+1}, \cdots, A_{R-1}, A_{R}$$$.

Python uses a sorting algorithm called Timsort. In short, the algorithm splits the list into mostly sorted subarrays, sorts each subarray using insertion sort, and merges the sorted subarrays. If the list is already mostly sorted, this algorithm runs very quickly.

In this problem, let's focus on the splitting part:

1. Take the longest non-decreasing (a₀ ≤ a₁ ≤ a₂ ≤ ...) or strictly decreasing (a₀ > a₁ > a₂ > ...) subarray that starts from the current index.

2. If the length of the subarray is less than MINRUN, take more elements until the length equals MINRUN or all elements are taken. Let's call these additional elements "bad elements".

If MINRUN is too small, there are too many subarrays to merge; if MINRUN is too large, it takes too much time to apply insertion sort. For this reason, it is important to set an appropriate value of MINRUN. Also, N / MINRUN should be close to a power of 2 to ensure a balanced merging, but we will not consider this in this problem. For each MINRUN value, find the number of subarrays and bad elements.

In RUN-land, there are $$$n$$$ cities numbered $$$1$$$ to $$$n$$$. Some pairs of cities are connected by a bidirectional road. It happens that there are $$$n-1$$$ roads in total and that for any two cities, there is a unique path from one to the other. Also, each road is assigned an integer called the value.

Today, to honor the $$$k$$$ co-founders of RUN-land, Alex, the king of RUN-land, has decided to choose $$$k$$$ different roads and give one road to each of the $$$k$$$ co-founders. To prevent unnecessary conflicts, there should be no city that is connected to more than one chosen roads.

In this process, Alex, the king of RUN-land, does not care about who gets what road. Instead, Alex, the king of RUN-land, is only interested in the sum of the values of the $$$k$$$ chosen roads. Your task is to choose the roads to maximize this sum.

Joon has a midterm exam tomorrow, but he hasn't studied anything. So he decided to stay up all night to study. He promised himself that he will not stop studying before the sun rises.

Joon's house is in some mountains. For convenience, let's say that Joon is living in a 2-dimensional coordinate system. The mountains are in the region $$$y\geq 0$$$, starting at $$$x=a_0$$$, and the boundary of them consists of $$$2n$$$ line segments parallel to either $$$y=x$$$ or $$$y=-x$$$.

More precisely, the boundary of the mountains can be described by $$$(2n-1)$$$ additional integers, where the $$$i$$$th number $$$a_i$$$ of them is the $$$x$$$-coordinate of the $$$i$$$th cusp of the mountains. The boundary line starts at $$$(a_0, 0)$$$, proceeds parallel to $$$y=x$$$ until its $$$x$$$-coordinate reaches $$$a_1$$$, then proceeds parallel to $$$y=-x$$$ until its $$$x$$$-coordinate reaches $$$a_2$$$, and so on. After the last step, the line proceeds parallel to $$$y=-x$$$ until it meets the $$$x$$$-axis.

The interior of the mountains is the region below the boundary and above the $$$x$$$-axis. Thus, the interior and the boundary are disjoint.

At some point between $$$x=a_0$$$ and $$$x=a_{2n-1}$$$, there is Joon's house on the boundary of the mountains. The size of his house is neglectable compared to the mountains.

Currently, the sun is at the origin and it rises vertically ($$$+y$$$ direction), 1 per minute. Joon can see the sun if the interior of the mountains does not intersect the straight line segment connecting Joon's house and the sun. Joon is completely exhausted and wants to know when can he stop studying. But as you may expect, he is out of his mind, so he cannot do such difficult math. Help him!

Figure: Voronoi Diagram of size 4.

In the 2-dimensional Cartesian coordinate system, we define the Voronoi Diagram of a non-empty set of points $$$S$$$, as a diagram that divides the plane by the criteria "which point in the set $$$S$$$ is closest in this location?". More precisely, the Voronoi diagram of a given non-empty point set $$$\{P_1, P_2, \cdots, P_n\}$$$ is a collection of regions: A point $$$K$$$ is included in region $$$i$$$ if and only if $$$d(P_i, K) \le d(P_j, K)$$$ holds for all $$$1 \le j \le n$$$, where $$$d(X, Y)$$$ denotes the Euclidean distance between point $$$X$$$ and $$$Y$$$.

For example, in the picture above, every location over the plane is colored by the closest point with such location. The points which belongs to a single region is colored by a light color indicating a region, and the points which belongs to more than one region forms lines and points colored black.

There is an algorithm which computes the Voronoi Diagram in $$$O(n \log(n))$$$, but it is infamous to be very complicated and hard. In fact, we are lenient problem setters, so we set $$$n \leq 2000$$$, which means you can solve this task with slower Voronoi Diagram algorithms!

In this task, you should solve the point query problem in Voronoi diagram: in the Voronoi diagram constructed with the set of points $$$\{P_1, P_2, \cdots, P_n\}$$$, you should determine which region(s) the point belongs in. More precisely, you will be given $$$q$$$ queries of points. For each query point, you should determine the following:

• If it's not included in any region, output NONE.
• If it's included in exactly one region, output REGION X, where X is the index of such region.
• If it's included in exactly two regions, output LINE X Y, where X and Y (X $$$ \lt $$$ Y) are the indices of such two regions.
• If it's included in three or more regions, output POINT.

You are given a string $$$s$$$ consisting of lowercase alphabets, and an integer $$$k$$$.

Make a new string $$$t$$$ by concatenating $$$k$$$ copies of $$$s$$$. Determine whether $$$t$$$ is a palindrome, e.g. is the same backward as forward.

Mr. Jeong really loves coke. He loves so much that he drinks coke everyday without exception. One day, he decided to open a coke contest in Daejeon. To the winner, a box of cokes will be given!

N people participate in the contest. Each participant is given K mL of coke, and the one who finishes his/her coke earliest wins the contest. But it is painful to drink the whole coke in one time, so each person repeats drinking and taking a rest. More specifically, as soon as the contest starts, the ith participant starts to drink for t_i seconds, then takes a rest for s_i seconds, and repeats this process until no more coke remains. Moreover, everyone drinks A mL per second. The contest is over if one of the participants finished his/her coke.

Given the infomation of N participants, determine after how many seconds the contest is finished, since the contest begins.