Description

去年，一个研究联盟在使用分布式数据库系统时遇到了问题，该系统有时会丢失部分数据。不过你不需要理解那个问题就能解决本题！

该联盟认为分布式系统过于复杂，于是决定将 $\mathbf{B}$ 位重要信息存储在一台超级计算机的单个数组中。为了增加安全性，他们设置了获取信息的障碍：用户必须查询 1 到 $\mathbf{B}$ 之间的位位置，才能获得该位存储的值。

不幸的是，这台超现代计算机会受到随机量子涨落的影响！具体来说，在发送第 1、11、21、31...次查询后（但在返回响应前），量子涨落会以均等概率（各 25%）引发以下四种效应之一：

• 数组取反：所有 0 变 1，所有 1 变 0；
• 数组反转：第 1 位与第 $\mathbf{B}$ 位交换，第 2 位与第 $\mathbf{B}-1$ 位交换，以此类推；
• 同时发生取反和反转（顺序无关）；
• 数组保持不变。

每次量子涨落的影响没有任何提示。联盟现在非常担忧，雇佣你来恢复这些珍贵数据（无论它们当前处于何种状态）！你能否找出整个数组，使得你的答案在提交时是准确的？注意：提交答案不算作查询，例如如果你在第 30 次查询后提交答案，数组状态将与第 21-30 次查询期间的状态一致。

交互协议

这是一个交互题。

初始时，你的程序应读取包含两个整数 $\mathbf{T}$ 和 $\mathbf{B}$ 的单行输入：分别表示测试用例数量和数组位数。注意所有测试用例的 $\mathbf{B}$ 相同。

接着处理 $\mathbf{T}$ 个测试用例。每个用例中，评测系统会预设一个 $\mathbf{B}$ 位数组（注意该数组可能因用例而异，且不一定是随机生成的）。你可以进行最多 150 次如下形式的查询：

• 你的程序输出 1 到 $\mathbf{B}$ 之间的整数 $\mathrm{P}$，表示要查询的位位置；
• 若当前查询次数是第 1、11、21...次（即模 10 余 1），评测系统会随机选择上述四种效应之一（独立于之前的选择）改变数组；
• 评测系统返回单字符 0 或 1 表示当前 $\mathrm{P}$ 位的值，若 $\mathrm{P}$ 非法则返回 $\mathrm{N}$。

完成查询后，你必须进行如下最终交互：

• 你的程序输出由 $\mathbf{B}$ 个 0/1 组成的字符串，表示当前数组状态（可能与初始状态不同）；
• 评测系统返回 $\mathrm{Y}$ 表示答案正确，$\mathrm{N}$ 表示错误（或格式非法）。收到 $\mathrm{Y}$ 后应处理下一个测试用例，若无更多用例则终止程序。

当评测系统返回 $\mathrm{N}$ 后，将不再发送任何输出。若你的程序继续等待会导致超时错误。注意：你需要确保程序及时退出以避免超时错误。若内存超限或运行时错误，将得到相应判果。

Input Format

参见交互协议。

Output Format

参见交互协议。

Hint

以下交互对应测试集 1：

t, b = readline_int_list() // 读取 t=100 和 b=10
// 评测系统初始数组：0001101111（实际测试集 1 不一定使用此数组）
printline 1 // 查询第 1 位
flush stdout
// 这是第 1 次查询（1 mod 10），系统随机选择取反+反转，数组变为 0000100111
r = readline_chr() // 返回 0
printline 6 // 查询第 6 位
flush stdout
// 第 2 次查询（2 mod 10），无量子涨落
r = readline_chr() // 返回 0
...
// 此处省略第 3-10 次查询
...
printline 1 // 再次查询第 1 位
flush stdout
// 第 11 次查询（11 mod 10），系统随机选择反转，数组变为 1110010000
r = readline_chr() // 返回 1
printline 1110110000 // 尝试提交错误答案
flush stdout
ok = readline_chr() // 返回 N
exit // 退出以避免超时错误

可使用交互测试工具进行本地测试。

数据范围

$1 \leq \mathbf{T} \leq 100$

测试集 1（1 分，可见判果）

• $\mathrm{B}=10$

测试集 2（9 分，可见判果）

• $\mathrm{B}=20$

测试集 3（16 分，隐藏判果）

• $\mathrm{B}=100$

翻译由 DeepSeek V3 完成