这是一个交互式问题。你的程序将通过标准输入和输出与评测机进行交互。评测机的执行时间可能长达 1.3 秒。

给定一个整数 $N$。评测机秘密选择了一个函数 $$f(x) := \sum_{k=0}^{N-1} A_k \cos(kx)$$ 其中每个 $A_0, A_1, \dots, A_{N-1}$ 都是满足 $0 \le A_k < 998244353$ 的整数。

你必须通过如下所述的交互来确定 $A_0, A_1, \dots, A_{N-1}$ 的值： 你将输出 $N$ 对整数 $(X_1, Y_1), \dots, (X_N, Y_N)$。每一对必须满足 $$0 \le X_i \le Y_i < 998244353, \quad Y_i \neq 0$$ 评测机随后将返回 $N$ 个整数 $Z_1, \dots, Z_N$，其中 $$Z_i = f\left(\arccos(X_i/Y_i)\right) \pmod{998244353}$$

$Z_i$ 的详细定义：在 $X_i, Y_i$ 的约束下，$f(\arccos(X_i/Y_i))$ 的值是一个有理数。将其写成最简分数 $P_i/Q_i$；可以证明 $Q_i \not\equiv 0 \pmod{998244353}$。那么 $Z_i$ 定义为满足以下条件的唯一整数 $0 \le Z_i < 998244353$： $$Z_i Q_i \equiv P_i \pmod{998244353}$$ 这样的 $Z_i$ 总是存在且唯一的。

输入格式

• 所有输入均为整数。
• $1 \le N \le 5 \times 10^5$。

交互

这是一个交互式问题。你的程序将通过标准输入和输出与评测机进行交互。 首先，从标准输入读取整数 $N$： $N$

然后输出 $N$ 个查询对 $(X_i, Y_i)$，格式如下，且需满足上述约束： $X_1 \ Y_1$ $X_2 \ Y_2$ $\vdots$ $X_N \ Y_N$

如果你的输出有效，评测机将回复 $N$ 行： $Z_1$ $Z_2$ $\vdots$ $Z_N$

如果你的输出无效，你将收到： -1

如果你收到“-1”，你的程序必须立即终止。 最后，在接收到 $Z_i$ 后，按顺序输出隐藏的系数 $A_0, A_1, \dots, A_{N-1}$： $A_0$ $A_1$ $\vdots$ $A_{N-1}$

说明

• 在每次输出操作后，请打印换行符并刷新标准输出。如果未能刷新，你可能会收到 TLE（超时）判决。
• 如果你在任何时候产生了无效输出，或者程序意外终止，判决结果是不确定的。
• 在打印答案（或读取“-1”）后，请立即终止程序。否则，判决结果是不确定的。
• 多余的换行符或任何偏离指定格式的行为都将被判定为无效。
• 评测机是非自适应的：值 $A_0, \dots, A_{N-1}$ 在开始时即固定，且在交互过程中不会改变。

样例

输入格式 1

2
3
5

输出格式 1

0 1
1 1
3
2

说明

假设 $N = 2$ 且 $(A_0, A_1) = (3, 2)$。上述交互展示了读取 $N$、查询两个有效对 $(X_i, Y_i)$、接收评测机返回的 $Z_1=3, Z_2=5$ 以及输出恢复出的 $(A_0, A_1)$ 的过程。