CF2129F2.Top-K Tracker (Hard Version)

这是一个交互题。

这是该问题的困难版本。唯一的区别在于本版本中 $ n \leq 890 $。只有在所有版本的问题都被解决后，你才能进行 Hack。

有一个隐藏的排列 $ p $，它是 $ {1,2,\ldots,n} $ 的一个排列。令 $ pos_i $ 表示值 $ i $ 在 $ p $ 中的位置，即 $ pos_{p_i} = i $。

为了找出这个排列，你可以进行以下四种类型的询问：

• “$ 1\ m\ i_1\ i_2\ \ldots\ i_m $”（$ 1 \leq m \leq n $，$ i_1,\ i_2,\ \ldots,\ i_m $ 必须互不相同）。令 $ k = \min(60, m) $。裁判会返回 $ [p_{i_1}, p_{i_2}, \ldots, p_{i_m}] $ 中最大的 $ k $ 个数，按升序排列。
• “$ 2\ m\ i_1\ i_2\ \ldots\ i_m $”（$ 1 \leq m \leq n $，$ i_1,\ i_2,\ \ldots,\ i_m $ 必须互不相同）。令 $ k = \min(60, m) $。裁判会返回 $ [pos_{i_1}, pos_{i_2}, \ldots, pos_{i_m}] $ 中最大的 $ k $ 个数，按升序排列。
• “$ 3\ m\ i_1\ i_2\ ...\ i_m $”（$ 1 \leq m \leq n $，$ i_1,\ i_2,\ ...,\ i_m $ 必须互不相同）。令 $ k = \min(300, m) $。裁判会返回 $ [p_{i_1}, p_{i_2}, ..., p_{i_m}] $ 中最大的 $ k $ 个数，按升序排列。
• “$ 4\ m\ i_1\ i_2\ \ldots\ i_m $”（$ 1 \leq m \leq n $，$ i_1,\ i_2,\ \ldots,\ i_m $ 必须互不相同）。令 $ k = \min(300, m) $。裁判会返回 $ [pos_{i_1}, pos_{i_2}, \ldots, pos_{i_m}] $ 中最大的 $ k $ 个数，按升序排列。

令 $ c_i $ 表示第 $ i $ 类询问的使用次数（$ 1 \leq i \leq 4 $）。你的询问次数必须满足以下约束：

• $ c_1+c_2+c_3+c_4 \leq 30 $。
• $ c_3+c_4 \leq 1 $。

每组测试包含多组测试用例。第一行包含测试用例数 $ t $（$ 1 \leq t \leq 40 $）。接下来是每组测试用例的描述。

每组测试用例的第一行包含一个整数 $ n $（$ 2 \leq n \leq 890 $）。此时，排列 $ p $ 已经被选定。本题的交互器是非自适应的。换句话说，每组测试用例中的排列 $ p $ 是固定的，在交互过程中不会改变。

要发起第 1 类询问，你需要输出如下格式的一行（不含引号）：

• “$ 1\ m\ i_1\ i_2\ \ldots\ i_m $”（$ 1 \leq m \leq n $，$ i_1, i_2, \ldots, i_m $ 必须互不相同）

之后，你会收到 $ k=\min(60,m) $ 个整数——即 $ [p_{i_1}, p_{i_2}, \ldots, p_{i_m}] $ 中最大的 $ k $ 个数，按升序排列。

要发起第 2 类询问，你需要输出如下格式的一行（不含引号）：

• “$ 2\ m\ i_1\ i_2\ \ldots\ i_m $”（$ 1 \leq m \leq n $，$ i_1, i_2, \ldots, i_m $ 必须互不相同）

之后，你会收到 $ k=\min(60,m) $ 个整数——即 $ [pos_{i_1}, pos_{i_2}, \ldots, pos_{i_m}] $ 中最大的 $ k $ 个数，按升序排列。

要发起第 3 类询问，你需要输出如下格式的一行（不含引号）：

• “$ 3\ m\ i_1\ i_2\ \ldots\ i_m $”（$ 1 \leq m \leq n $，$ i_1, i_2, \ldots, i_m $ 必须互不相同）

之后，你会收到 $ k=\min(300,m) $ 个整数——即 $ [p_{i_1}, p_{i_2}, \ldots, p_{i_m}] $ 中最大的 $ k $ 个数，按升序排列。

要发起第 4 类询问，你需要输出如下格式的一行（不含引号）：

• “$ 4\ m\ i_1\ i_2\ \ldots\ i_m $”（$ 1 \leq m \leq n $，$ i_1, i_2, \ldots, i_m $ 必须互不相同）

之后，你会收到 $ k=\min(300,m) $ 个整数——即 $ [pos_{i_1}, pos_{i_2}, \ldots, pos_{i_m}] $ 中最大的 $ k $ 个数，按升序排列。

接下来，如果你的程序已经找到了排列 $ p $，请输出如下格式的一行（不含引号）：

• “$ !\ p_1\ p_2\ \ldots\ p_n $”

注意，这一行不计入询问次数。

输出每次询问或每组测试用例的答案后，别忘了输出换行并刷新输出缓冲区，否则你会收到 Idleness Limit Exceeded 的判定。为此，你可以使用：

• C++：fflush(stdout) 或 cout.flush()
• Java：System.out.flush()
• Pascal：flush(output)
• Python：stdout.flush()
• 其它语言请参考相关文档。

Hack 格式

Hack 时请按照如下测试格式：

第一行包含测试用例数 $ t $（$ 1 \leq t \leq 40 $）。接下来是每组测试用例的描述。

每组测试用例的第一行包含一个整数 $ n $（$ 2 \leq n \leq 890 $）。

每组测试用例的第二行包含 $ n $ 个整数 $ p_1, p_2, \ldots, p_n $，它是 $ {1,2,\ldots,n} $ 的一个排列。

在第一个测试用例中，隐藏的排列为 $ p = [3, 1, 2] $。因此，$ pos = [2, 3, 1] $。

对于询问 “3 2 3 1”，裁判返回 $ 2 $ 和 $ 3 $，因为 $ 2 $ 和 $ 3 $ 是 $ [p_3, p_1] $ 中最大的 $ k $ 个数，其中 $ k = \min(300, m) = \min(300, 2) = 2 $。

对于询问 “2 1 2”，裁判返回 $ 3 $，因为 $ 3 $ 是 $ [pos_2] $ 中最大的 $ k $ 个数，其中 $ k = \min(60, m) = \min(60, 1) = 1 $。

注意，样例仅用于帮助理解题意，并不保证能唯一确定排列 $ p $。

由 ChatGPT 4.1 翻译