[SNCPC2024] 猜质数 I

**这是一道交互题。** MCPlayer542 手上有一个神秘的**奇质数** $p$，但他并不想让你知道这个数是多少。 他打算用一个函数 $f(x)$ 来加密他的数，其值为 $x$ 在十进制下的各位数字之和，例如 $f(5)=5$，$f(542)=5+4+2=11$，$f(1024)=1+0+2+4=7$。 **然而考虑到你太聪明，他想了想，决定把加密函数改成：** $$g(x)=f(f(f(f(f(f(f(f(f(f(x))))))))))$$ **即连续应用 $10$ 次 $f(x)$，并把手上的 $p$ 换成了 $q=p^k$。** 现在他准备给你 $n$ 个整数 $g(q^{a_1}),\ g(q^{a_2}),\ \ldots,\ g(q^{a_n})$，并希望你能告诉他 $$q^{a_1}\bmod (m\cdot a_1),\ q^{a_2}\bmod (m\cdot a_2),\ \ldots,\ q^{a_n}\bmod (m\cdot a_n)$$ 分别是多少。**他觉得你肯定猜不到，所以决定让你自己选择 $m$ 和 $a_1,\ a_2,\ \ldots,\ a_n$**。你能完成这个任务吗？ **注意：$m$ 的范围有特殊限制。**

输入包含多组测试数据。数据的第一行包含一个整数 $t$ ($1\le t\le 500$)，表示数据组数。每组数据的交互流程在下文中描述。 在每组数据中，输入的第一行包含两个整数 $n$ 和 $k$ ($1\le n\le 50, \ 1\le k\le 10^9$)，用单个空格分隔，含义见题目描述。 接下来每次交互，输出一行一个整数 $a_i$ ($1\le a_i\le 10^{18},a_i$ **互不相同**)，表示要询问的 $q$ 的幂次。 给出一个询问后，你应该读入一个整数，即 $g(q^{a_i})$。 你需要在进行完 $n$ 轮交互之后输出一行一个整数 $m$ ($m\ge 35,1\le m\cdot a_i\le 10^{18}$)，再输出一行 $n$ 个数，即 $q^{a_1}\bmod (m\cdot a_1), \ q^{a_2}\bmod (m\cdot a_2), \ \ldots, \ q^{a_n}\bmod (m\cdot a_n)$，用单个空格分隔，表示答案。 **你必须进行恰好 $n$ 轮交互，随后输出答案并结束程序，否则你可能得到无法预测的结果。** 注意在你的程序每轮输出结束时（即，每一次交互输出 $a_i$ 时和最后输出 $m$ 与答案时）需要输出回车并刷新输出缓冲区，否则你将会得到 $\text{Idleness Limit Exceeded}$。 - C 的 $\text{fflush(stdout)}$； - C++ 的 $\text{cout.flush()}$； - Java 的 $\text{System.out.flush()}$； - Python 的 $\text{stdout.flush()}$； 来刷新输出缓冲区。 **保证在每组数据中的奇质数** $p$ ($2<p\le 10^{18}$) **都是在交互前确定的，即不会随着你的输入而变化。** 如果你最后输出的答案正确，你会得到 $\text{Accepted}$； 如果你输出的 $m$ 或 $a_i$ 不符合题目范围要求，或最后输出的答案不正确，你会得到 $\text{Wrong Answer}$。 此外，其他的评测结果仍会在评测过程中根据通常情况返回。

2
3 1

3

9

9


3 2

4

4

4

1

2

3

100
3 9 27

1

7

49

49
0 0 0

在第一组数据中，MCPlayer542 手上的奇质数 $p=3$，因此有 $q=p^k=3$。 我们选择数组 $a=\{1,\ 2,\ 3\}$，依次得到 $g(3^1)=3, \ g(3^2)=9, \ g(3^3)=9$。 随后我们猜到 $p=3$，选择 $m=100$，因此输出 $3^1\bmod (100\times 1)=3, \ 3^2\bmod (100\times 2)=9, \ 3^3\bmod (100\times 3)=27$。 在第二组数据中，MCPlayer542 手上的奇质数 $p=7$，因此有 $q=p^k=49$。 我们选择数组 $a=\{1,\ 7,\ 49\}$，依次得到 $g(49^1)=4,\ g(49^7)=4,\ g(49^{49})=4$。 随后我们**敏锐地发现** $p=7$，选择 $m=49$，因此输出 $49^1\bmod (49\times 1)=0, \ 49^7\bmod (49\times 7)=0, \ 49^{49}\bmod (49\times 49)=0$。 注：第二组数据中的“**敏锐地发现**”仅作为交互流程的示意，并不保证上述交互可以确定 $p=7$。