CF1543D2 RPD and Rap Sheet (Hard Version)

这是该问题的困难版本。唯一的区别在于这里 $2\leq k\leq 100$。只有当你同时解决了该问题的两个版本时，才能进行 Hack。 这是一个交互题！ 每个十进制数都有一个 $k$ 进制的等价形式。$k$ 进制数的每一位称为 $k$-it。我们定义两个 $k$-it $a$ 和 $b$ 的 $k$-it 异或为 $(a + b)\bmod k$。 两个 $k$ 进制数的 $k$-it 异或等于将它们对应 $k$-it 逐位 $k$-it 异或后得到的新数。两个十进制数 $a$ 和 $b$ 的 $k$-it 异或记作 $a\oplus_{k} b$，其值等于将 $a$ 和 $b$ 转换为 $k$ 进制后逐位 $k$-it 异或，再转回十进制所得的结果。下文中所有数字均为十进制，除非特别说明。 你已经黑进了 Rockport 警察局（RPD）的犯罪数据库（Rap Sheet）。但要访问它，你需要一个密码。你并不知道密码，但你确信它在 $0$ 到 $n-1$ 之间（包含 $0$ 和 $n-1$）。于是你决定去猜。幸运的是，你最多可以尝试 $n$ 次而不会被系统封锁。但系统是自适应的。每当你猜错一次，系统就会更改密码。具体来说，如果猜测前的密码是 $x$，你猜了一个不同的数 $y$，那么系统会将密码更改为 $z$，使得 $x\oplus_{k} z = y$。请你猜出密码，闯入系统。

输入的第一行包含一个整数 $t$（$1\leq t\leq 10\,000$），表示测试用例的数量。接下来有 $t$ 组测试用例。 每个测试用例的第一行包含两个整数 $n$（$1\leq n\leq 2\cdot 10^5$）和 $k$（$2\leq k\leq 100$）。 保证所有测试用例中 $n$ 的总和不超过 $2\cdot 10^5$。

对于每个测试用例，首先读取两个整数 $n$ 和 $k$。然后你可以最多询问 $n$ 次。 每次询问时，输出一个整数 $y$（$0\leq y\leq 2\cdot 10^7$）。设当前密码为 $x$。之后读取一个整数 $r$。 如果 $x=y$，你将读到 $r=1$，该测试用例结束。你需要继续解决剩余的测试用例。 否则，你将读到 $r=0$。此时密码会被更改为 $z$，满足 $x\oplus_{k} z = y$。 每次输出询问后，别忘了输出换行并刷新输出缓冲区，否则会收到“Idleness limit exceeded”判定。 为此，你可以使用： - C++：fflush(stdout) 或 cout.flush() - Java：System.out.flush() - Pascal：flush(output) - Python：stdout.flush() - 其它语言请查阅相关文档 如果你询问了非法的数或超过 $n$ 次询问，将会读到 $r=-1$ 并收到“Wrong Answer”判定。此时请立即退出以避免不必要的判定。 注意，交互器是自适应的。也就是说，初始密码并不是一开始就固定的，可能会根据你的询问动态变化。但保证在任何时刻，至少存在一个初始密码，使得所有询问的答案都是一致的。 Hack 说明： 若要进行 Hack，请使用如下格式： 第一行包含一个整数 $t$（$1\leq t\leq 10\,000$），表示测试用例数量。 每个测试用例的第一行包含两个整数 $n$（$1\leq n\leq 2\cdot 10^5$）和 $k$（$2\leq k\leq 100$），分别表示可询问次数和进制。自适应交互器会自动决定最优初始密码。 你必须保证所有测试用例中 $n$ 的总和不超过 $2\cdot 10^5$。

样例 1： 此时隐藏密码为 $2$。 第一次询问 $3$，不等于当前密码，返回 $0$，密码变为 $1$，因为 $2\oplus_2 1=3$。 第二次询问 $4$，不等于当前密码，返回 $0$，密码变为 $5$，因为 $1\oplus_2 5=4$。 第三次询问 $5$，等于当前密码，返回 $1$，任务完成。 样例 2： 此时隐藏密码为 $3$。 第一次询问 $1$，不等于当前密码，返回 $0$，密码变为 $7$，因为 $3\oplus_3 7=1$。$[3=(10)_3, 7=(21)_3, 1=(01)_3, (10)_3\oplus_3 (21)_3 = (01)_3]$。 第二次询问 $4$，不等于当前密码，返回 $0$，密码变为 $6$，因为 $7\oplus_3 6=4$。$[7=(21)_3, 6=(20)_3, 4=(11)_3, (21)_3\oplus_3 (20)_3 = (11)_3]$。 第三次询问 $6$，等于当前密码，返回 $1$，任务完成。 注意，这些初始密码仅用于说明。实际上，评测器可能会有不同的行为，因为它是自适应的。 由 ChatGPT 4.1 翻译