Guess the permutation

Given a permutation of $n$ numbers, where $n$ is a power of two, you need to determine the order of the elements in this permutation. The permutation is a sequence of integers from $1$ to $n$, each appearing exactly once. For example, $[1]$, $[4,3,5,1,2]$, and $[3,2,1]$ are valid permutations, while $[1,1]$, $[4,3,1]$, and $[2,3,4]$ are not.

You can make queries using an array $a$ of length $n$, where each element $a_i$ satisfies $1\le a_i\le n$. Note that $a$ does not have to be a permutation. For each query, you receive an array $c$ of length $n$, constructed as follows:

c = array of length n filled with zeros
for i = 1 to n:
    if p[a[i]] > p[i]:
         c[a[i]] += 1
return c

Your task is to find the hidden permutation $p$. The maximum number of queries allowed is specified in the "Scoring" section.

Input

The first line contains two integers $t$ and $q$ ($1\le t,q\le 256$) — the number of test cases and the maximum number of queries allowed per test case.

Interaction

For each test case, read an integer $n$ ($1\le n\le 1024$) — the number of elements in permutation $p$. It is guaranteed that $n$ is a power of two.

To make a query, output "1 $a_1$ $a_2$ ...$a_n$" ($1\le a_i\le n$). In response, the system will return the array $c$, formatted as "$c_1$ $c_2$ ...$c_n$".

After outputting a query, ensure you print a newline character and flush the output buffer to avoid a "Time Limit Exceeded" verdict. Use:

• fflush(stdout) or cout.flush() in C++;

• System.out.flush() in Java;

• flush(output) in Pascal;

• stdout.flush() in Python;

Refer to the documentation for other languages.

If your query is invalid (exceeding the query limit or violating input constraints), the system will output "-1" and terminate. If you receive "-1", terminate your program immediately to avoid an arbitrary verdict.

Once you determine the permutation $p$, output "2 $p_1$ $p_2$ ...$p_n$". If it is the last test case, terminate your program; otherwise, proceed to the next test case.

Examples

1 256
4

0 1 1 1

1 3 2 4 2

2 1 4 2 3

Note

From the first query, we deduced that $p_1<p_3<p_4<p_2$. Thus, the permutation is $[1,4,2,3]$.

Scoring

The maximum number of queries $q$ your program can use is specified as follows:

1. (3 points) $n\le 16,q=256,t=128$

2. (7 points) $n\le 32,q=256,t=128$

3. (8 points) $n\le 256,q=256,t=128$

4. (14 points) $n\le 512,q=256,t=128$

5. (20 points) $n\le 512,q=128,t=256$

6. (up to 48 points) $n\le 1024,q=127,t=256$; Let $k$ be the maximum number of queries used in one test case. The score for this test is:

• 0 points, if $k>127$;

• $48-\lceil \frac{24(k-55)}{37}\rceil$ points, if $55<k\le 127$;

• 48 points, if $k\le 55$;