题目描述

题目译自 Ukrainian Olympiads in Informatics 2021 Stage 4 Day2 T3. Вгадайте перестановкуД

给定一个由 $n$ 个数字组成的排列（$n$ 是 $2$ 的幂次方）。你不知道这个排列的具体顺序。

排列是指长度为 $n$ 的整数序列，包含从 $1$ 到 $n$ 的所有数字，并且每个数字恰好出现一次。例如，$[1]$、$[4, 3, 5, 1, 2]$、$[3, 2, 1]$ 是排列，而 $[1, 1]$、$[4, 3, 1]$、$[2, 3, 4]$ 不是。

你可以进行一种查询操作：提交一个长度为 $n$ 的数组 $a$，其中 $1 \leq a_i \leq n$（注意，$a$ 不一定是排列）。作为响应，你将收到一个长度为 $n$ 的数组 $c$，其生成规则如下：

c = 长度为 n 的全零数组
for i = 1 to n:
    if p[a[i]] > p[i]:
        c[a[i]] += 1
返回 c

你的目标是找出隐藏的排列 $p$。允许的最大查询次数见「数据范围与提示」部分。

输入格式

第一行包含两个整数 $t$ 和 $q$ $(1 \leq t, q \leq 256)$，分别表示输入数据的组数和每组数据中允许的最大查询次数。

交互方式

对于每组输入数据，首先读取一个整数 $n$ $(1 \leq n \leq 1024)$，表示排列 $p$ 的元素数量。

保证 $n$ 是 $2$ 的幂次方（即存在非负整数 $k$，使得 $2^k = n$）。

要进行一次查询，输出格式为 $1\ a_1\ a_2 \ldots a_n$ $(1 \leq a_i \leq n)$。

作为响应，评测程序将返回一个数组 $c$，格式为 $c_1\ c_2\ \ldots\ c_n$，按照题目描述的规则生成。

在输出查询后，务必输出换行符并清空输出缓冲区，否则可能会导致「超时」判定。清空缓冲区的方法如下：

• 在 C++ 中使用 $\texttt{fflush(stdout)}$ 或 $\texttt{cout.flush()}$；
• 在 Java 中使用 $\texttt{System.out.flush()}$；
• 在 Pascal 中使用 $\texttt{flush(output)}$；
• 在 Python 中使用 $\texttt{stdout.flush()}$；
• 其他语言请参考相关文档。

请注意，如果你的查询无效（例如超过查询次数限制或输入数组不符合约束条件），交互器将输出 -1 并终止运行。如果读取到 -1，请立即终止程序，以获得「答案错误」判定，而不是其他未定义的判定结果。

当你找到排列 $p$ 时，输出 $2\ p_1\ p_2\ \ldots \ p_n$。

如果这是最后一组输入数据，则应终止程序；否则，继续处理下一组输入数据。

1 256
4

0 1 1 1

1 3 2 4 2

2 1 4 2 3

在第一次查询中，得知 $p_1 < p_3 < p_4 < p_2$。

因此，目标排列为 $[1, 4, 2, 3]$。

数据范围与提示

$q$ 表示程序允许的最大查询次数。

详细子任务附加限制及分值如下表所示：

对于最后一个子任务，设 $k$ 为单组数据中使用的最大查询次数，则得分如下：

• 若 $k > 127$，得 $0$ 分；
• 若 $55 < k \leq 127$，得 $48 - \lceil \frac{24(k-55)}{37} \rceil$ 分；
• 若 $k \leq 55$，得 $48$ 分。