Guess the permutation#10449

Guess the permutation

30 seconds

256 megabytes

Medium

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]$ [4, 3, 5, 1, 2], and $[3, 2, 1]$ [3, 2, 1] are valid permutations, while $[1, 1]$ , $[4, 3, 1]$ [4, 3, 1], and $[2, 3, 4]$ [2, 3, 4] are not.

You can make queries using an array $a$ of length $n$ , where each element $a_{i}$ a_i satisfies $1 \leq a_{i} \leq n$ 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 \leq t, q \leq 256$ 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 \leq n \leq 1024$ 1 \le n \le 1024) — the number of elements in permutation $p$ . It is guaranteed that $n$ is a power of two (i.e., there exists a non-negative integer $k$ such that $2^{k} = n$ 2^k=n).

To make a query, output "1 $a_{1}$ a_1 $a_{2}$ a_2 ... $a_{n}$ a_n" ( $1 \leq a_{i} \leq n$ 1 \le a_i \le n). In response, the system will return the array $c$ , formatted as " $c_{1}$ c_1 $c_{2}$ c_2 ... $c_{n}$ 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 get a Wrong Answer verdict instead of an arbitrary verdict.

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

Examples

Example



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}$ p_1<p_3<p_4<p_2. Thus, the permutation is $[1, 4, 2, 3]$ [1, 4, 2, 3].

Scoring

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

(3 points) $n \leq 16, q = 256, t = 128$ n \le 16, q=256, t=128
(7 points) $n \leq 32, q = 256, t = 128$ n \le 32, q=256, t=128
(8 points) $n \leq 256, q = 256, t = 128$ n \le 256, q=256, t=128
(14 points) $n \leq 512, q = 256, t = 128$ n \le 512, q=256, t=128
(20 points) $n \leq 512, q = 128, t = 256$ n \le 512, q=128, t=256
(up to 48 points) $n \leq 1024, q = 127, t = 256$ 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$ k > 127;
$48 - ⌈ \frac{24 ( k - 55 )}{37} ⌉$ 48- \lceil \frac{24(k-55)}{37}\rceil points, if $55 < k \leq 127$ 55 < k \le 127;
48 points, if $k \leq 55$ k \le 55;