CFCF2183G.Snake Instructions

这是一个交互题。

数轴上有 $n$ 条蛇。第 $i$ 条蛇在位置 $a_i$，速度为 $s_i$。你已知每条蛇的位置，并且每条蛇的速度是 $0$ 到 $2$ 的整数，但你不知道具体每条蛇的速度。保证没有两条蛇处于相同的位置。

为了确定所有蛇的速度，你最多可以进行 $3$ 次指令。每条指令应以长度为 $m$ 的二进制字符串给出，字符串只包含 L 和 R （$1 \leq m \leq 4n$）。收到这条指令后，所有蛇会运动 $m$ 秒。在第 $i$ 秒，如果 $s_i=$ L，则所有蛇向左运动一秒，否则全部蛇向右运动一秒。如果在某一时刻（包括非整数秒时），有两条蛇处于相同的位置，则速度快的那条蛇被移除。$m$ 秒后，你会获得剩下的蛇的数量 $k$，以及所有剩余蛇的位置。注意，每次指令都是独立的——也就是说，所有蛇都会复活回到起始位置再开始新的操作。

你的任务是确定所有蛇的速度。然而，可能存在无法确定某一条蛇的速度的情况，如果碰到这种情况，你需要输出 $-1$。只有当无论给出哪一组最多 $3$ 条指令都无法确定某条蛇的速度时，才能输出 $-1$。如果存在至多 $3$ 条指令能唯一确定所有蛇的速度而你输出了 $-1$，你会得到 Wrong Answer 判决。同理，如果本应该输出 $-1$ 却没有输出也会判错，即使你“猜”对了速度。

每个测试包含多个测试用例。第一行为用例数量 $t$（$1 \le t \le 10^3$），随后是所有用例的描述。

每个用例的第一行为整数 $n$，即蛇的数量（$2 \leq n \leq 10^5$）。

第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$（$1 \leq a_1<a_2<\ldots<a_n \leq 4n$），表示所有蛇的初始位置。

保证所有用例的 $n$ 之和不超过 $10^5$。

交互说明

读入所有蛇的位置后，开始交互。每次发出指令需按以下格式输出一行：

• ? s

你需保证 $s$ 只由字母 L 和 R 组成，且长度在 $1$ 到 $4n$ 之间。

评测器会返回如下格式的一行：

• $k\ b_1\ b_2\ \ldots\ b_k$（$1 \leq k \leq n, -10^9 \leq b_1<b_2<\ldots<b_k \leq 10^9$）

其中 $k$ 表示指令后剩余蛇的数量，$b_1,b_2,\ldots,b_k$ 为它们的最终位置。

当你准备好输出答案时，输出一行：

• 如果无法确定所有蛇的速度，输出 ! -1
• 否则，输出 ! s_1 s_2 \ldots s_n（$0 \leq s_i \leq 2$），其中 $s_i$ 表示第 $i$ 条蛇的速度。

输出答案不计入指令次数。

之后继续下一个用例或程序最后终止。

交互器不自适应，即所有蛇的速度在整个过程都保持不变，并保证输入合法——即所有信息与各自速度兼容。

每次输出查询后请务必换行并刷新输出缓冲，否则会收到 Idleness limit exceeded 的判决。

若某一步收到 $-1$，表示你有非法查询或其他错误，应立即退出，否则程序继续读取已关闭流会导致不可预期的判决。

Hack 格式

自定义 hack 时，输入如下格式：

第一行为整数 $t$，即用例数（$1 \leq t \leq 10^3$）。

每个用例的第一行为 $n$（$2 \leq n \leq 10^5$）。

第二行为 $n$ 个整数 $a_1,a_2,\ldots,a_n$（$1 \leq a_1<a_2<\ldots<a_n \leq 4n$）。

第三行为 $n$ 个整数 $s_1,s_2,\ldots,s_n$（$0 \leq s_i \leq 2$），表示每条蛇的速度。

所有用例的 $n$ 之和不超过 $10^5$。

要刷新输出缓冲：

• C++：fflush(stdout) 或 cout.flush()；
• Python：sys.stdout.flush()；
• 其它语言请查阅相关文档。

在第一个用例中，两条蛇速度分别为 $0$ 和 $1$。程序首先给出指令 L。右边那条蛇从 $2$ 移动到 $1$，而左边的蛇不动。此时两条蛇都在 $1$，速度较大的蛇（右边那只）被移除。因此只剩下一条蛇在位置 $1$。此时程序猜测两条蛇的速度分别为 $0$ 和 $1$，这是正确的。注意，尽管速度 $[0,2]$ 也会导致最后只剩一只蛇在 $1$，但不能直接输出 $-1$，因为还可以通过另一组指令区分 $[0,2]$ 和 $[0,1]$。

在第三个用例中，可以确定第一条蛇和第三条蛇的速度均为 $0$，且可以证明无论如何无法区分中间那条蛇的速度是 $1$ 还是 $2$，因此输出 $-1$ 是正确的。