You have recently learned about interactive libraries.

Given a chain of length $n-1$, the nodes are labeled with a permutation of $[1, n]$.

In each step, you can query a chain of length $n-1$ consisting of these $n$ nodes, and the interactive library will return the number of undirected edges common to both chains.

Try to determine the chain within at most $3 \times 10^5$ queries. Furthermore, your score depends on the number of queries you use.

Note: The interactive library is not adaptive; in other words, the chain is fixed before the interaction begins.

Implementation Details

You must include the interactive.h header file.

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

You only need to implement the following function:

std::vector<int> solve(int n);

This function will be called exactly once, where $n$ is the given number of nodes. The return value should be a permutation $p$ of order $n$, where $p[i]$ represents the $(i+1)$-th node on the chain (either in forward or reverse order is acceptable).

You can call the following function:

int query(std::vector<int> p);

where $p$ should be a permutation of order $n$, representing the chain for this query.

Examples

The sample interactive library will read input data in the following format:

The first line contains a positive integer $n$.

The next line contains $n$ numbers in the range $[1, n]$, where the $i$-th number is the $i$-th node on the chain.

The sample interactive library will output data in the following format:

If you perform an invalid query (or the number of queries $> 2 \times 10^5$), the sample interactive library will output WA: 0; otherwise, if you return the correct chain information, it will output AC: [number of queries used], otherwise it will output WA: 1.

It is guaranteed that the interactive library will use no more than $1\text{s}$ of time and $256\text{MB}$ of memory during evaluation.

Note that the final interactive library used for grading may not be the same as the sample interactive library.

Example Interaction

solve(3) // return: {3, 2, 1}

query({1, 2, 3}) // return: 2
query({3, 1, 2}) // return: 1
query({2, 3, 1}) // return: 1

Constraints

• Subtask 1 (10 points): $n \leq 30$.
• Subtask 2 (90 points): $n \leq 500$.

For 100% of the data, $3 \leq n \leq 500$.

Subtask 1 Scoring

Subtask 1 consists of 15 test cases.

If your program does not return the correct result for any test case, you will receive 0 points; otherwise, you will receive 10 points.

Subtask 2 Scoring

Subtask 2 consists of 40 test cases.

If your program does not return the correct result for any test case, you will receive 0 points; otherwise, your score will be calculated as follows (where $T$ is the number of queries you used):