Education experts are going to rate $$$n$$$ contests due to whatever reasons. The experts have already decided on the rating of each contest, where the $$$i$$$-th contest is rated as a $$$s_i$$$-star contest.

It is said that each contest is rated according to $$$m$$$ properties, where the $$$j$$$-th property of the $$$i$$$-th contest is indicated as $$$p_{i, j}$$$, whose value ranges from $$$0$$$ to $$$k$$$ (both inclusive). The score of a contest is calculated as the sum of all its $$$m$$$ properties. That is, let $$$v_i$$$ be the score of the $$$i$$$-th contest, we have $$$v_i = \sum\limits_{j=1}^m p_{i, j}$$$.

It would be natural for a contest with more stars to have a higher score. The experts require that, for any two contests $$$1 \le i, j \le n$$$, if $$$s_i \gt s_j$$$, then there must be $$$v_i \gt v_j$$$. Unfortunately, the experts forgot to collect values for some (or even all) properties of some contests. As the assistant of the experts, you're required to fill in the missing values so that the constraint stated above holds for any two contests.

What a busy week! This weekend, $$$n$$$ programming contests will be held at the same time.

Each contest will award one gold medal for every $$$k$$$ participating teams. That is to say, if there are $$$t$$$ teams participating in the contest, $$$\lfloor \frac{t}{k} \rfloor$$$ gold medals will be awarded, where $$$\lfloor x \rfloor$$$ is the largest integer not exceeding $$$x$$$. Currently, there will be $$$a_i$$$ teams participating in the $$$i$$$-th contest.

BaoBao is the coach of a university with $$$m$$$ teams, and he hasn't decided which contests these teams should participate in. Please help him assign each team to a contest, so that the total number of gold medals handed out by all contests is maximized.

There are $$$n$$$ castles and $$$m$$$ obstacles on a chessboard with $$$10^9$$$ rows and $$$10^9$$$ columns. Each castle or obstacle occupies exactly one cell and all occupied cells are distinct. Two castles can attack each other, if they're on the same row or the same column, and there are no obstacles or other castles between them. More formally, let $$$(i, j)$$$ be the cell on the $$$i$$$-th row and the $$$j$$$-th column. Two castles positioned at $$$(i_1, j_1)$$$ and $$$(i_2, j_2)$$$ can attack each other, if one of the following conditions is true:

• $$$i_1 = i_2$$$ and for all $$$\min(j_1, j_2) \lt j \lt \max(j_1, j_2)$$$, there is no obstacle or castle positioned at $$$(i_1, j)$$$.
• $$$j_1 = j_2$$$ and for all $$$\min(i_1, i_2) \lt i \lt \max(i_1, i_2)$$$, there is no obstacle or castle positioned at $$$(i, j_1)$$$.

You have to remove $$$k$$$ obstacles from the chessboard, but you don't want too many castles to attack each other. Minimize the number of pairs of castles which can attack each other after removing exactly $$$k$$$ obstacles from the chessboard.

You are given a template string $$$S = s_1s_2\cdots s_n$$$ of length $$$n$$$. A generated string is a string formed by concatenating several substrings of $$$S$$$. Formally, each generated string $$$T = f(k, \{l_i\}_{i=1}^k, \{r_i\}_{i=1}^k)$$$ is described by a positive integer $$$k$$$ and $$$k$$$ pairs of integers $$$(l_i, r_i)$$$, where $$$T = s[l_1:r_1]+s[l_2:r_2]+\cdots+s[l_k: r_k]$$$. Here $$$s[l: r]$$$ denotes the substring $$$s_ls_{l+1}\cdots s_r$$$, and $$$+$$$ denotes string concatenation.

Your task is to maintain a multiset $$$\mathbb{A}$$$ of strings, supporting the following three types of operations:

• + $$$k\ l_1\ r_1\ l_2\ r_2\ \cdots\ l_k\ r_k$$$: Insert $$$f(k, \{l_i\}_{i=1}^k, \{r_i\}_{i=1}^k)$$$ into the multiset $$$\mathbb{A}$$$.

• - $$$t$$$: Erase the string inserted in the $$$t$$$-th operation from the multiset $$$\mathbb{A}$$$. It is guaranteed that the $$$t$$$-th operation is an inserting operation and the inserted string is not erased at this time.

• ? $$$k\ l_1\ r_1\ l_2\ r_2\ \cdots\ l_k\ r_k\ m\ u_1\ v_1\ u_2\ v_2\ \cdots u_m\ v_m$$$: Answer the number of strings in the multiset $$$\mathbb{A}$$$ that begin with string $$$f(k, \{l_i\}_{i=1}^k, \{r_i\}_{i=1}^k)$$$ and end with $$$f(m, \{u_i\}_{i=1}^m, \{v_i\}_{i=1}^m)$$$.

Given an integer sequence $$$a_1, a_2, \cdots, a_n$$$ of length $$$n$$$ and a non-negative integer $$$k$$$, you can perform the following operation at most once: Choose two integers $$$l$$$ and $$$r$$$ such that $$$1 \le l \le r \le n$$$, then for each $$$l \le i \le r$$$, change $$$a_i$$$ into $$$(a_i + k)$$$.

Maximize the greatest common divisor of the whole sequence.

An integer $$$g$$$ is said to be the common divisor of the whole sequence, if $$$a_i$$$ is divisible by $$$g$$$ for all $$$1 \le i \le n$$$.

There are $$$10^9$$$ cells arranged in a row, numbered from $$$1$$$ to $$$10^9$$$ from left to right. Two robots are patrolling in the cells. The maximum speed of each robot is $$$v$$$ cells per second ($$$v$$$ is an integer), indicating that if a robot is currently in cell $$$p$$$, it can move to any cell $$$p'$$$ in the next second, as long as $$$1 \le p' \le 10^9$$$ and $$$|p' - p| \le v$$$.

There will be $$$n$$$ coins appearing in the cells. The $$$i$$$-th coin will appear at the $$$t_i$$$-th second in cell $$$c_i$$$. If a robot is in the same cell at that time, it can pick up the coin. Otherwise the coin will instantly disappear.

More formally, during each second, the following steps will happen in order:

• Each robot can move to a position no more than $$$v$$$ cells away (it is OK to just stay in its current cell).
• Coins appear in the cells.
• If at least one robot is in the same cell with a coin, that coin is collected.
• All uncollected coins disappear.

Your task is to determine the initial positions of two robots before the $$$1$$$-st second, and move them wisely to collect all the coins with the smallest possible $$$v$$$. Output this optimal value of $$$v$$$.

Find the lexicographically smallest permutation $$$p_0, p_1, p_2 \cdots, p_{n-1}$$$ of $$$0, 1, 2, \cdots, (n - 1)$$$ satisfying the following constraint: For all $$$0 \le i \lt n$$$, $$$p_0 \oplus p_1 \oplus \cdots \oplus p_i \gt 0$$$. Here $$$\oplus$$$ is the bitwise exclusive or operation.

We say an integer sequence $$$p_0, p_1, \cdots, p_{n - 1}$$$ of length $$$n$$$ is lexicographically smaller than another integer sequence $$$q_0, q_1, \cdots, q_{n - 1}$$$ of length $$$n$$$, if there exists an integer $$$0 \le k \lt n$$$ such that $$$p_i = q_i$$$ for all $$$0 \le i \lt k$$$ and $$$p_k \lt q_k$$$.

Given an integer sequence $$$a_1, a_2, \cdots, a_n$$$ of length $$$n$$$, we say a continuous subarray $$$a_l, a_{l + 1}, \cdots, a_r$$$ is good, if the maximum element of the subarray appears exactly $$$k$$$ times in the subarray. For each $$$1 \le k \le n$$$, count the number of good subarrays.

Given a string consisting of lower-cased English letters, we say the string is beautiful if all neighboring characters are different. For example, icpc and kunming are beautiful but hello is not, because its $$$3$$$-rd and $$$4$$$-th characters are the same.

Given a string $$$S = s_0s_1\cdots s_{n-1}$$$ of length $$$n$$$ consisting of lower-cased English letters, let $$$f(S, d)$$$ be the string obtained by shifting $$$S$$$ to the left $$$d$$$ times. That is $$$f(S, d) = s_{(d+0)\bmod n}s_{(d+1)\bmod n}\cdots s_{(d+n-1)\bmod n}$$$.

Let $$$g(S, d)$$$ be the smallest number of operations needed to make string $$$f(S, d)$$$ beautiful. In each operation, you can change one character in $$$f(S, d)$$$ to any lower-cased English letter.

Find a non-negative integer $$$d$$$ which minimizes $$$g(S, d)$$$ and output the minimized value.

There is a kingdom with $$$n$$$ cities and $$$m$$$ bi-directional railways connecting the cities. The $$$i$$$-th railway is operated by the $$$c_i$$$-th railway company, and the length of the railway is $$$l_i$$$.

You'd like to travel around the country starting from city $$$1$$$. For your travel, you have bought $$$k$$$ railway tickets. The $$$i$$$-th ticket can be represented by two integers $$$a_i$$$ and $$$b_i$$$, meaning that if you use this ticket, you can travel through some railways in one go, as long as they're all operated by company $$$a_i$$$ and their total length does not exceed $$$b_i$$$. It is also allowed to just stay in the current city when using a ticket. You can only use the tickets one at a time, and you can only use each ticket once.

As you find it a burden to determine the order to use the tickets, you decided to use the tickets just in their current order. More formally, you're going to perform $$$k$$$ operations. In the $$$i$$$-th operation, you can either choose to stay in the current city $$$u$$$; Or choose a different city $$$v$$$, such that there exists a path from city $$$u$$$ to city $$$v$$$ where all railways in the path are operated by company $$$a_i$$$ and the total length of railways does not exceed $$$b_i$$$, and finally move to city $$$v$$$.

For each city, determine if it is possible to arrive in that city after using all $$$k$$$ tickets.

This is an interactive problem.

There is a hidden permutation of $$$n$$$. Recall that a permutation of $$$n$$$ is a sequence where each integer from $$$1$$$ to $$$n$$$ (both inclusive) appears exactly once. Piggy wants to unravel the permutation with some queries.

Each query must consist of a sequence (not necessarily a permutation) with $$$n$$$ integers ranging from $$$1$$$ to $$$n$$$ (both inclusive). Each query is answered with an integer $$$x$$$, indicating the number of the positions where the corresponding element in Piggy's query sequence matches that of the hidden permutation. For example, if the hidden permutation is $$$\{1, 3, 4, 2, 5\}$$$ and the sequence Piggy asks is $$$\{2, 3, 5, 2, 5\}$$$, he'll receive $$$3$$$ as the answer.

As Piggy is busy recently, he gives this problem to you. Find the permutation with no more than $$$6666$$$ queries.

To ask a query, output one line. First output 0 followed by a space, then print a sequence of $$$n$$$ integers ranging from $$$1$$$ to $$$n$$$ separated by a space. After flushing your output, your program should read a single integer $$$x$$$ indicating the answer to your query.

If you want to guess the permutation, output one line. First output 1 followed by a space, then print a permutation of $$$n$$$ separated by a space. After flushing your output, your program should exit immediately.

Note that the answer for each test case is pre-determined. That is, the interactor is not adaptive. Also note that your guess does not count as a query.

To flush your output, you can use:

• fflush(stdout) (if you use printf) or cout.flush() (if you use cout) in C and C++.
• System.out.flush() in Java.
• stdout.flush() in Python.

BaoBao is taking a walk on an infinite two-dimensional plane. For each point $$$(x, y)$$$ on the plane where both $$$x$$$ and $$$y$$$ are integers, there is a bi-directional trail connecting points $$$(x, y)$$$ and $$$(x + 1, y)$$$, and another bi-directional trail connecting points $$$(x, y)$$$ and $$$(x, y + 1)$$$. What's more, there are $$$n$$$ additional bi-directional trails, where the $$$i$$$-th trail connects points $$$(x_i, y_i)$$$ and $$$(x_i + 1, y_i + 1)$$$.

BaoBao can only move along the trails. Let $$$f(x, y)$$$ be the smallest number of trails BaoBao has to pass if he wants to move from point $$$(0, 0)$$$ to point $$$(x, y)$$$. Given two integers $$$p$$$ and $$$q$$$, calculate

$$$$$$ \sum\limits_{x = 0}^p \sum\limits_{y = 0}^q f(x, y) $$$$$$

BaoBao has prepared a pizza for you! This pizza is a convex polygon with stuffed crust along all of its edges. However, the crust is delicate, allowing you to cut only through its vertices and not into the middle of the edges. Unfortunately, there's a sizable circular piece of pineapple on the pizza that you absolutely want to avoid.

Calculate the largest single piece of pineapple-free pizza that you can obtain with a single straight cut and output its size. A piece is considered pineapple-free when no part of the pineapple falls strictly within it. That is, the area of intersection of the pineapple and the pizza is $$$0$$$.