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 indices $i, j$, hhz will tell you the relative order of $a_i$ and $a_j$.

2. Given three pairwise distinct indices $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 determine 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$ and $i, j, k$ are pairwise distinct.

Examples

Input 1

4 8
1 3 2 4

Output 1

1 3 2 4

Note

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 type $2$ operations you used. Otherwise, it will output Wrong Answer [id], and you can check the grader for specific error information.

Subtasks

For all test cases, $4 \leq n \leq 500000$ and $2n \leq m \leq 10^6$.

The grader is adaptive.