这是一个交互式问题。

“管道游戏”（Plumber Mariusz）包含 $n+1$ 个层级（编号为 $0$ 到 $n$），每一层都有 $k$ 个版本（编号为 $0$ 到 $k-1$）。除最后一层外，每一层的每个版本末端都有两条管道——左管道和右管道——Mariusz 必须跳入其中一条。每条管道包含一定数量的硬币，并通向下一层级的某个版本。除第 $0$ 层外，每一层的每个版本都有且仅有两条管道通向它；这两条管道可以是上一层所有 $k$ 个版本引出的 $2 \cdot k$ 条管道中的任意两条。

单次游玩过程包括：选择第 $0$ 层的一个版本，然后进行 $n$ 次选择（左管道或右管道），游玩的结果是 $n$ 次经过的管道中收集到的硬币总数。我们无法得知每条管道中有多少硬币，也无法得知具体经过了哪些层级版本。管道中的硬币总是会重置为初始值，因此所有游玩过程都是独立的。因此，一次游玩过程可以用以下函数表示：

int rozgrywka(int ver, string s)，其中 $ver \in [0, k-1]$，$s$ 是一个由 $n$ 个字母 L 和 P 组成的字符串。

注意，L 和 P 分别对应波兰语中的左（left）和右（right）。

你可以执行最多 $300\,000$ 次测试游玩并获知其结果。之后，你将收到最多 $10\,000$ 个关于游玩过程的查询。你的任务是确定这些查询的结果。

每个测试用例在交互开始前就已经固定（即交互器不是自适应的）。一个测试用例包含一个有向加权图，该图有 $(n+1) \cdot k$ 个顶点，排列在 $n+1$ 个层级中，以及 $q$ 个查询 $(ver, s)$。每个顶点（最后一层除外）都有两条出边（左和右），每条边由硬币数量 $c \in [1, 10^8]$ 和它通向的版本 $v \in [0, k-1]$ 描述。回想一下，除第 $0$ 层外，每个顶点的入度恰好为 $2$。

缓冲区刷新

在输出每一行后，你必须刷新输出缓冲区，以便交互器能够接收到该行输出。例如，在 C++ 中，你可以使用 cout << "!" << endl; 或者 printf("!\n"); fflush(stdout); 输出一个感叹号。在 Python 中，你可以使用 print("!", flush=True)。如果你在没有刷新缓冲区的情况下输出多行，或者在没有读取交互器响应的情况下输出过多行，我们不保证交互器的行为稳定。你的程序不得打开任何文件。

交互格式

完整的通信流程描述如下：

• 读取第一行，包含两个整数 $n$ 和 $k$ ($1 \le n, k \le 20$) —— 表示共有 $n+1$ 个层级，每个层级有 $k$ 个版本。
• 执行最多 $300\,000$ 次测试游玩：
  • 输出一行格式为 ? ver s 的内容（不含引号），其中 $ver \in [0, k-1]$，$s$ 是一个由 $n$ 个字母 L 和 P 组成的字符串。刷新缓冲区。
  • 读取下一行，包含游玩结果 —— 一个整数 $x$ ($n \le x \le n \cdot 10^8 \le 2 \cdot 10^9$)。
• 输出一行包含单个字符 !（感叹号）。刷新缓冲区。
• 读取下一行，包含一个整数 $q$ ($1 \le q \le 10\,000$) —— 查询的数量。
• 对于每个查询：
  • 读取下一行，包含一个整数 $ver$ 和一个字符串 $s$（限制同上）。
  • 输出一行，包含游玩结果（一个整数）。刷新缓冲区。

插图展示了第一个样例测试（$n=2; k=4$）。两个最终查询用虚线标记：rozgrywka(0, "LL") = 20 + 3 = 23 和 rozgrywka(1, "PL") = 9 + 10 = 19。

样例

以下是一个通信流程示例：

说明

在附件中（你可以在 QOJ 的“附件”标签页下载），你会找到示例（不正确的）解决方案 G.cpp 和 G.py，它们能正确执行通信，但计算结果不正确。该目录还包括：一个示例检查器 Gsoc.cpp 和样例测试（G0a.in、G0b.in、G0c.in 以及一个 $n=k=20$ 的大型随机测试 G0d.in）。测试文件的格式在 Gsoc.cpp 开头的注释中有描述。

示例检查器 Gsoc.cpp 与 QOJ 上使用的检查器不同。它可能不会验证输入或游玩函数的参数。

你可以使用脚本 run.sh 运行你的解决方案。该命令接收编译后的程序和测试文件名。例如，要在样例测试 G0a.in 上运行示例程序：

• C++: g++ G.cpp -o G.e && ./run.sh "./G.e" G0a.in
• Python: ./run.sh "python3 G.py" G0a.in