题目描述

请注意本题不寻常的时间限制。

给定一个由 $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 \le a_i \le 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 \le t, q \le 256$）——分别是测试用例的数量和每个测试用例允许的最大查询次数。

交互说明

对于每个测试用例，首先读取一个整数 $n$（$1 \le n \le 1024$），表示排列 $p$ 的长度。

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

要发起查询，请输出 $1\ a_1\ a_2 \dots \ a_n$（$1 \le a_i \le n$）。

作为响应，评测系统会返回数组 $c$，其生成规则如题目描述所示，格式为 $c_1\ c_2\ \dots \ c_n$。

发起查询后，请确保输出换行符并刷新输出缓冲区，否则可能触发“超出时间限制”错误。刷新缓冲区的方法如下：

• C++：fflush(stdout) 或 cout.flush()；
• Java：System.out.flush()；
• Pascal：flush(output)；
• Python：stdout.flush()；

其他语言请参考相关文档。

注意：如果你的查询无效（超过查询次数限制或数组 $a$ 不满足条件），评测系统会返回 $-1$ 并终止程序。如果读取到 $-1$，请立即终止程序以避免意外结果。

当你确定排列 $p$ 后，请输出 $2\ p_1\ p_2 \dots \ 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$ 表示程序允许的最大查询次数。

• （3 分）$n \le 16$，$q=256$，$t=128$；
• （7 分）$n \le 32$，$q=256$，$t=128$；
• （8 分）$n \le 256$，$q=256$，$t=128$；
• （14 分）$n \le 512$，$q=256$，$t=128$；
• （20 分）$n \le 512$，$q=128$，$t=256$；
• （最高 48 分）$n \le 1024$，$q=127$，$t=256$；设 $k$ 为单个测试用例中实际使用的最大查询次数，则得分规则为：
  • 若 $k > 127$，得 0 分；
  • 若 $55 < k \le 127$，得 $48 - \lceil \frac{24(k-55)}{37} \rceil$ 分；
  • 若 $k \le 55$，得 48 分；

翻译由 DeepSeek V3 完成