题目描述

这是一道交互题。

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$。