Astronomers have recently found a cosmic signal from a distant planet. World's best scientists have all confirmed that this is a communication signal sent by aliens. Moreover, they have established that these aliens have only nine fingers, hence, they use a numeral system in base 9, in other words, digits from $$$0$$$ to $$$8$$$. To challenge humans, these aliens came up with a puzzle. Many scientists solved the puzzle, but since the stakes are very high, they want you to confirm that their solution is correct as you are the smartest computer scientist on the planet. The puzzle is explained below.

Let $$$n$$$ be some positive integer, and $$$f(n)$$$ be a function that returns another positive integer that can be represented as $$$123456781011...n$$$ in base 9. In other words, $$$f(n)$$$ is a number which can be obtained by concatenating all the positive integers from 1 to n in their base 9 representations. The obtained number is also in base 9.

For example, for $$$n = 10$$$ (in base 10), $$$f(n) = 123456781011$$$, since $$$n = 11$$$ (in base 9). You need to find the remainder of dividing $$$f(n)$$$ by $$$4$$$.

You are a rider of a two-headed snake! It has two heads, one on each end, respectively.

You are traveling in a country that can be represented as a tree with $$$n$$$ vertices. Each vertex of the tree represents a city in the country.

You have such a long snake that its body takes up a certain simple path in the tree. Its heads are located on the vertices $$$h_1$$$ and $$$h_2$$$, respectively.

In one move, you can choose one of the heads, and move it to a neighboring vertex that does not have a body part of the snake on it. All of the other parts of the body will move in the same direction. Note that you are not allowed to stretch or compress the snake (it hurts)!

Find the minimum number of moves required for the snake to reach the given vertex $$$tar$$$, i.e. to make one of the heads be located on $$$tar$$$.

Mura is a tree-lover. Unfortunately, recently, he has lost his favorite rooted tree $$$t$$$ of size $$$n$$$, each node $$$v$$$ of which was assigned a value ($$$v.val$$$).

$$$t$$$ satisfies the following:

1. The next pseudocode function returns a given array $$$a$$$ of size $$$n$$$ as a result, if $$$t$$$ is passed as an argument:

   
   Array to_array(Tree t):
       Array res = [t.root.val]
       
       for each child v of t.root:
           res = res + to_array(v.subtree)
   
       return res
   

2. Among all trees that satisfy the first condition, $$$t$$$ has the maximum sum of $$$f(v)$$$ over all nodes $$$v$$$ of the tree. Here, $$$f(v) = xor(v) \curlywedge size(v)$$$, where:
   • $$$xor(v)$$$ — the result of bitwise XOR operation over the values of all nodes in the subtree of $$$v$$$.
   • $$$size(v)$$$ — the number of nodes in the subtree of $$$v$$$.
   • $$$\curlywedge$$$ — bitwise AND operation.

Mura knows, that he will never see his favorite tree again. But, at least, he wants to find the value of the sum of $$$f(v)$$$ over all nodes $$$v$$$ of $$$t$$$. Can you help him?

You are given a sequence of delivery points $$$x$$$ of length $$$n$$$ and the integer number $$$k$$$.

Delivery point is an integer number $$$x_i$$$ in the range of $$$[-10^9; 10^9]$$$ (i.e. $$$-10^9 \le x_i \le 10^9$$$).

Find the minimum distance of delivering any $$$k$$$ orders. Initially you are at origin $$$0$$$.

The distance between $$$x_i$$$ and $$$x_j$$$ is the absolute difference between them |$$$x_i$$$ - $$$x_j$$$|.

You're given an undirected graph with $$$n$$$ nodes and $$$m + n$$$ edges ($$$m$$$ red and $$$n$$$ black edges). Nodes are numbered from $$$1$$$ to $$$n$$$ in the order around the circle. There are $$$n$$$ black edges between adjacent nodes. Nodes $$$i$$$ and $$$(i + 1)$$$ are adjacent for $$$(1 \le i \le n - 1)$$$, nodes $$$1$$$ and $$$n$$$ are also adjacent.

You are given $$$m$$$ red edges.

The path is considered valid if and only if the given path contains at most $$$1$$$ red edge.

Find the length of the shortest valid path between two vertices $$$a_i$$$ and $$$b_i$$$.

Solve this problem for $$$Q$$$ independent queries.

You are a pizza delivery courier at Yankeks. The region you are working in can be represented as an $$$n \times m$$$ grid. Each cell of the grid is either empty or occupied.

You can move only between neighboring empty cells. Two cells are considered as neighboring if they share a side.

You are given $$$q$$$ queries of the following types:

• $$$0$$$ $$$x_1$$$ $$$y_1$$$ $$$x_2$$$ $$$y_2$$$
  • Make all cells $$$(x, y)$$$ which satisfy $$$x_1 \leq x \leq x_2$$$ and $$$y_1 \leq y \leq y_2$$$ empty.
  • $$$1 \leq x_1, x_2 \leq n$$$.
  • $$$1 \leq y_1, y_2 \leq m$$$.

• $$$1$$$
  • Cancel the last query of type 0.
  • It is guaranteed that there exists a non-cancelled query of type 0.

• $$$2$$$ $$$x_1$$$ $$$y_1$$$ $$$x_2$$$ $$$y_2$$$
  • Determine if you can deliver a pizza from cell $$$(x_1, y_1)$$$ to cell $$$(x_2, y_2)$$$.
  • $$$1 \leq x_1, x_2 \leq n$$$.
  • $$$1 \leq y_1, y_2 \leq m$$$.
  • It is guaranteed that cells $$$(x_1, y_1)$$$ and $$$(x_2, y_2)$$$ are empty.

Your task is to answer all queries of type 2.

This problem is interactive. That means you can make queries and get responses in the online mode. Please be sure to use the stream flushing operation after each query's output in order not to leave part of your output in some buffer. For example, in C++ you've got to use the fflush(stdout) function, in Java — call System.out.flush(), and in Pascal — flush(output).

Ulzhan is a young researcher at NU. She wants to find out what number is the most popular favorite number amongst Kazakh people. But since there are millions of Kazakh people, she asked for your help. Ulzhan already has a list of people who agreed to participate in this research. Your job is to simply go through the list and ask each person what his or her favorite number is. It is guaranteed that one of the numbers appears strictly more than 50% of the time. In other words, the most popular number accounts for the majority of participant responses. Your task is to find that number after having received all the responses.

It is guaranteed that each participant's response is an integer within the range $$$[-10^{18}, 10^{18}]$$$, and the total number of participants is within the range $$$[1, 10^6]$$$.

Pay attention to the unusual time and memory constraints!

Use standard input and output for the interaction.

1. To start the interaction, output a single line consisting of a string "next".

2. Read a line of input consisting of a single integer, a participant's response.

3. Keep repeating steps 1 and 2, until you read -1 in step 2.

4. If you read -1, it means you have received all the responses. This -1 is not a participant response and should not be counted towards the answer!

5. Output a single integer, the number that appeared more than half of the times in step 2, excluding the last -1.

After step 5, your program should terminate immediately.

It is the last week before NU Open takes place. The greatest problemsetter of all time $$$krauch$$$ does not have time and money for new challenging problems. So, $$$krauch$$$ asks their boss $$$CMaster$$$ for help. But there is a thing, $$$CMaster$$$ accepts only positive whole square amount of dollars $$$\geq X$$$. $$$Krauch$$$ is out of pocket. Luckily, $$$NUBANK$$$ provides loans with low percentages, but, of course, has its own terms, the loan amount may only be the product of some bank-supported prime numbers.

More specifically, $$$NUBANK$$$ has an array of supported prime numbers, $$$p[]$$$ (not necessarily distinct) and another array $$$cost[]$$$, both of them having lengths of $$$N$$$. If you choose indices $$$j_1$$$, $$$j_2$$$ ... $$$j_m$$$, the loan amount will be $$$p_{j_1}$$$ $$$\cdot$$$ $$$p_{j_1}$$$ $$$\cdot$$$ ... $$$\cdot$$$ $$$p_{j_m}$$$ and the return cost will be $$$cost_{j_1}$$$ $$$+$$$ $$$cost_{j_1}$$$ $$$+$$$ ... $$$+$$$ $$$cost_{j_m}$$$.

Can you help $$$krauch$$$ to take a loan from $$$NUBANK$$$ to pay $$$CMaster$$$ with the minimal return cost (as $$$krauch$$$ is out of money)? Keep in mind that both the $$$NUBANK$$$ and $$$CMaster$$$ has their own terms and conditions.

We have a track that is infinite in one direction.

At the begging of the track, we have a car with an initial speed of $$$v=0$$$ m/s. Also, the car has an acceleration of $$$a$$$ m$$$/s^2$$$, which we can change at any moment of time to a value in the range [1, -1] m$$$/s^2$$$. The speed of the car can reach any value in the range (-$$$\infty$$$, $$$\infty$$$) m/s

We are given $$$n$$$ requests. In each request, a new restriction $$$(t, r)$$$ is added: At the moment when $$$t$$$ seconds have passed from the start of the race, the speed of the car should satisfy $$$v \leq r$$$ (at that exact moment).

After each request, you need to print the maximum distance that the car can reach at the moment when all restrictions are passed.

You are given two arrays of integers $$$a$$$ and $$$b$$$.

You can perform the following operation on the array $$$a$$$:

1. Pick some subarray of length k.

2. Replace it with the sum of the elements in the subarray.

For example, if the initial array was $$$[3, 6, 9]$$$ and we have $$$k$$$ = 2, then in a single operation you can replace the last two elements by their sum, yielding an array $$$[3, 15]$$$, or replace the first two elements to get an array $$$[9, 9]$$$.

For some fixed $$$k$$$, let us denote it as valid, if it is possible to get the array $$$b$$$ from $$$a$$$ by performing the given operation some number of times (possibly zero).

Find the valid values of $$$k$$$ ($$$1 \le k \le n$$$) and print them in an increasing order.