题目描述

这是一道交互题。

有 $N$ 个小球，从 $1$ 到 $N$ 编号。

你每次可以询问编号在 $[l,r]$ 之间的小球有几种不同的颜色，你需要求出每个小球的颜色。由于你并不知道具体颜色是什么，你只要将同种颜色用同一个数字表示即可。

交互格式

第一行输入一个正整数 $T$，代表 Subtask 编号（而不是测试数据组数）。

第二行输入两个整数 $N,Q$，代表小球数量和询问次数限制。

接下来你可以提出不超过 $Q$ 个询问并读取交互库返回的答案，每个询问的格式为 ? l r，代表你询问 $[l,r]$ 中小球颜色的数量。

当你确认所有小球的颜色后，你需要输出 ! a1 a2 ... an 代表所有小球的颜色。你需要保证：

• $1\leq a_i\leq N$ 且 $a_i$ 均为整数。
• 相同颜色的小球的 $a_i$ 相同。
• 不同颜色的小球的 $a_i$ 不同。

你的每次输出后都需要刷新缓冲区，你可以使用如下语句来清空缓冲区：

• 对于 C/C++：fflush(stdout)；
• 对于 C++：std::cout << std::flush；
• 对于 Java：System.out.flush()；
• 对于 Python：stdout.flush()；
• 对于 Pascal：flush(output)；
• 对于其他语言，请自行查阅对应语言的帮助文档。

输入格式

见“交互格式”。

输出格式

见“交互格式”。

1
5 10000

2

1

2
 

 

? 1 5

? 1 3

? 2 4

! 1 1 1 2 2

提示

【数据范围】

本题采用捆绑测试。

• Subtask 1（8 points）：$Q=10000$, 保证每种颜色的球的编号连续。
• Subtask 2（7 points）：$Q=2000$，保证每种颜色的球的编号连续。
• Subtask 3（19 points）：$Q=2000$，保证球只有至多 $3$ 种颜色。
• Subtask 4（14 points）：$Q=2000$，保证球只有至多 $4$ 种颜色。
• Subtask 5（12 points）：$Q=2000$，保证球有至少 $(N-1)$ 种颜色。
• Subtask 6（21 points）：$Q=10000$，保证 $N\le 100$。
• Subtask 7（19 points）：$Q=10000$。

对于所有数据，保证 $1\leq T\leq 7$，$2\leq N\leq 10^3$。