hhz has a permutation of $1$ to $n$, and you need to guess it.

You can only ask hhz the following two types of questions:

1. Given two distinct numbers $i, j$, hhz will tell you the relative order of $a_i$ and $a_j$.
2. Given three pairwise distinct numbers $i, j, k$, hhz will tell you the median of $a_i, a_j, a_k$.

You are allowed to perform at most $2$ queries of type $1$ and $m$ queries of type $2$. You need to guess the permutation.

Implementation Details

This is an interactive problem.

You must include the header file guess.h.

You need to implement the following function:

vector<int> solve(int n, int m);

This function will be called exactly once. You need to return an array of length $n$ representing the permutation.

You can call the following procedures:

bool query1(int i, int j);

This function returns $1$ if $a_i < a_j$, and $0$ otherwise.

You must ensure $0 \leq i, j < n$ and $i \neq j$.

int query2(int i, int j, int k);

This function returns the median of $a_i, a_j, a_k$.

You must ensure $0 \leq i, j, k < n$, $i \neq j$, $j \neq k$, and $k \neq i$.

Examples

The sample interactor reads data in the following format:

The first line contains two integers $n, m$.

The second line contains $n$ integers representing the permutation.

If your interaction process is valid and the returned permutation is correct, the sample interactor will output Accepted cnt=... indicating the number of times you used operation $2$. Otherwise, it will output Wrong Answer [id]. You can refer to the interactor source code for specific error information.

Constraints

This problem uses bundled testing.

For all test cases, $50 \leq n \leq 5 \cdot 10^5$ and $2n \leq m \leq 10^6$.

The interactor is adaptive.

Note

You can submit a Hack using the following format:

• $seed$
• $n$ $m$ $mode$ $arg_1$ $arg_2$ $\cdots$ $arg_k$

The meanings of the parameters are as follows:

• $seed$: The seed used for randomization, satisfying $0 \leq seed < 2^{31} = 2\,147\,483\,648$.
• $n$: The $n$ from the problem statement, satisfying $50 \leq n \leq 5 \cdot 10^5$.
• $m$: The $m$ from the problem statement, satisfying $2n \leq m \leq 10^6$.
• $mode$: The strategy used by the interactor, satisfying $0 \leq mode \leq 3$:
  • When $mode = 0$:
    • The interactor will randomly choose a permutation as $a$.
    • The number of parameters $k=0$.
  • When $mode = 1$:
    • The interactor is adaptive and will construct $a$ dynamically based on the player's queries.
    • The number of parameters $k=1$, containing exactly one parameter $init\_num$, satisfying $0 \leq init\_num < n$.
  • When $mode = 2$:
    • The interactor is adaptive and will construct $a$ dynamically based on the player's queries.
    • The number of parameters $k=1$, containing exactly one parameter $rev$, satisfying $0 \leq rev \leq 1$.
  • When $mode = 3$:
    • The interactor will use the permutation $a$ provided by you.
    • The number of parameters $k=n$, containing $n$ parameters $a_1, a_2, \cdots, a_n$ representing the permutation $a$.

It is recommended to always use $mode = 3$ when using Hacks. Below are four valid input examples for your reference:

123456
50 1000000 0

234567
50 1000000 1 1

123123
50 1000000 2 0

67812345
50 1000000 3 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50