This is an interactive problem.

On the counter of 跳蚤甜品店 are two rows of colorful two-layer jellies (the upper layer is $a$, and the lower layer is $b$). Under the shop's “complementary setting” rule, the heights of the upper and lower layers at each position sum to exactly $n+1$. The staff had originally arranged each of the two rows by height into a perfect permutation of $1 \sim n$, but last night, a lively flea staff member accidentally swapped the upper and lower jelly layers at some positions!

Now the annual Dessert Festival is about to begin, and the staff must restore the original arrangement before the jellies were swapped (that is, the upper-layer height sequence $a$ before the swaps).

You cannot observe the jelly heights directly, but you can issue instructions to the dessert shop's automatic measuring device: specify several positions $i$, and the device will swap the upper and lower jelly layers at those positions, then return the difference between the maximum and minimum heights (the range) of the current upper layer, as well as the difference between the maximum and minimum heights (the range) of the lower layer. Note: the effect of each swap persists.

Can you successfully restore the original upper-layer jelly sequence within a limited number of swap-and-measure operations?

The interaction library first chooses a permutation $p$ of $1\sim n$ and constructs the permutation $b_i=n+1-p_i$. Then, independently for each index $i$, the interaction library decides whether to swap the two numbers at position $i$. Denote the arrays after these swaps by $a,b$. We always have $a_i+b_i=n+1$, but $a,b$ are not necessarily still permutations.

You know $n$, but you do not know these two arrays. You may choose several positions and swap $a_i,b_i$ at those positions; the interaction library will tell you the ranges of both arrays after the swaps. The effect of each swap persists.

Your task is to reconstruct the array $a$ before the first query. An answer is also considered correct if it matches the target only after every value $x$ in the returned array is simultaneously replaced by $n+1-x$.

Implementation Details

You do not need to, and should not, implement the main function.

You must include the header range.h in the source file recover.cpp and implement the following function:

std::vector<int> recover(int c, int n);

• $c$ is the current subtask number: it is $1,2,3,4$ in the official tests and $0$ in the example. $n$ is the length of the arrays. The interaction library calls recover exactly once per test case.
• The return value must be an integer array of length $n$, representing $a$ before the first query, or its whole-array complement.

You may call the following function:

std::pair<int, int> query(const std::vector<int>& positions);

• The indices in positions must be pairwise distinct and belong to $[0,n-1]$. You may pass an empty array.
• For each index in positions, the interaction library swaps the current $a_i,b_i$ exactly once, then returns the range of the current $a$ and the range of the current $b$. Swaps accumulate between queries, but the array you return must reconstruct the initial array before the swaps.
• The range is defined as the maximum value in an array minus its minimum value. Since $b_i=n+1-a_i$ always holds, the two ranges are necessarily equal.
• The number of calls to query must not exceed the limit $Q_{\max}$ for the test case.

The interaction library is not adaptive: the initial arrays are fixed before recover begins and do not change in response to your queries. The interaction library used in the final evaluation may differ from the provided sample interaction library. Your program must not read the interaction library's internal data or directly operate on the standard input or output streams.

Testing Your Program

Place recover.cpp, range.h, and the attached grader.cpp in the same directory, and compile using C++17:

g++ grader.cpp recover.cpp -o recover -O2 -std=c++17
./recover < ex_range1.in

The first line read by the local interaction library contains $c,n,Q_{\max}$; the second line contains the permutation $p_0,\ldots,p_{n-1}$; and the third line contains $n$ numbers that are $0/1$, where $1$ indicates that the corresponding position is swapped before the interaction begins. Only $c,n$ are provided to your program through function parameters; the permutation, swap flags, and query limit are not passed directly to your program.

If the answer is correct, the local interaction library outputs Correct! on the first line and Queries used: Q on the second line, where $Q$ is the number of queries used in this call. If the answer is incorrect, it outputs Wrong answer.; if an interface call is invalid, it also reports the reason on the standard error stream.

Examples

Input 1

0 6 67
3 1 6 4 2 5
0 1 1 0 1 0

Output 1

Correct!
Queries used: 16

Note

In the example, $a=(3,6,1,4,5,5)$ before the interaction begins, and its whole-array complement is $(4,1,6,3,2,2)$. Returning either of them is correct. The first call to query({}) returns $(5,5)$. The output above corresponds to the result of running the attached standard program; different correct programs may use different numbers of queries.

Constraints

For all test data, $1\le n\le 500$.

Each subtask is scored according to the test case in it with the lowest score multiplier, as described below.

Subtasks

If the answer returned by recover is incorrect, the arguments to query are invalid, or the number of queries exceeds $Q_{\max}$, the score for that test case is $0$.

Otherwise, test cases in subtasks $1,2$ receive full credit. For subtasks $3,4$, let $Q$ be the number of queries actually used for the test case. The score multiplier $f(Q)$ is calculated using the following table:

The score for subtask $3$ is $40f(Q)$, and the score for subtask $4$ is $40f(Q)$. The final score is rounded to $3$ decimal places.

Time limit: $2\ \mathrm{s}$.

Memory limit: $512\ \mathrm{MiB}$.