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$ and $j$, hhz will tell you the relative order of $a_i$ and $a_j$.
2. Given three pairwise distinct numbers $i, j,$ and $k$, hhz will tell you the median of $a_i, a_j,$ and $a_k$.

You are allowed to perform at most $2$ queries of type $1$ and $m$ queries of type $2$. You need to determine the entire 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 must 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,$ and $a_k$.

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

Examples

The sample grader reads data in the following format:

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

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

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

Constraints

This problem uses subtask testing.

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

The grader is adaptive.