本题为交互题（你的程序与评测程序通过标准输入输出进行交互）。评测程序的运行最多需要 $1.3$ 秒。

给定一个整数 $N$。评测程序隐藏了一个函数 $f(x) \coloneqq \sum_{k=0}^{N-1} A_k \cos{kx}$，其中，$A_0, \dots, A_{N - 1}$ 是 $0$ 以上、$998244353$ 未满的整数。

通过下面的交互过程，确定整数 $A_0, \dots, A_{N-1}$：

• 你需要输出 $N$ 组整数对 $(X_1, Y_1), \dots, (X_N, Y_N)$。对于每组整数 $(X_i, Y_i)$，需要满足 $0 \le X_i \le Y_i < 998244353$ 且 $Y_i \neq 0$。
• 评测程序会回复 $N$ 个整数 $Z_1, \dots, Z_N$。每个 $Z_i$ 按如下定义：$Z_i \coloneqq f(\arccos(X_i / Y_i)) \bmod 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$ 是满足 $Z_i Q_i \equiv P_i \pmod{998244353}$ 的 $[0, 998244353)$ 内的唯一整数。可以证明，这样的 $Z_i$ 必然存在且唯一。

本题为交互题（你的程序与评测程序通过标准输入输出进行交互）。

首先，从标准输入读取 $N$。

$N$

接下来，你需要输出满足条件的 $(X_1, Y_1), \dots, (X_N, Y_N)$，每两个数字之间以空格分隔，所有数值按 $X_1~Y_1~X_2~Y_2~\cdots~X_N~Y_N$ 的顺序输出，最后换行并刷新缓冲区。

$X_1$ $Y_1$ $X_2$ $Y_2$ $\cdots$ $X_N$ $Y_N$

如输出合法，评测机会回复 $N$ 个整数 $Z_1, \dots, Z_N$，每个数字之间以空格分隔，表示 $f(\arccos(X_i / Y_i))$ 模 $998244353$ 的值。

$Z_1~Z_2~\cdots~Z_N$

如输出不合法，则输入会返回一行 -1。

-1

如果收到 -1，请立即退出程序。

之后，请输出你的答案，格式如下：

$A_0~A_1~\cdots~A_{N-1}$

参考上述交互流程。

注意事项

• 每次输出后务必换行并刷新缓冲区。否则可能会因评测超时（TLE）而失败。
• 如果交互过程中输出非法内容，或者程序中途退出，则评测结果不确定。
• 输出答案后（或接收到 -1 后）请立刻正常退出程序，否则评测结果不确定。
• 尤其需要注意，如果输出多余的换行，也会被判为格式错误。
• 评测程序不会根据你的查询自适应变化。也就是说，$A_0, \dots, A_{N - 1}$ 在交互开始就已经固定，期间不会改变。

输入输出样例

以下为 $N = 2$、$(A_0, A_1) = (3, 2)$ 的示例：

输入 输出 说明
`2`   给出 $N$
`0 1`
`1 1` 向评测程序查询符合条件的 $(X_i, Y_i)$
`3`
`5`   得到 $f(\arccos(X_i / Y_i))$ 的结果回复
`3`
`2`   输出结果 $(A_0, A_1) = (3, 2)$

输入格式

详见题面交互过程。

输出格式

详见题面交互过程。

提示

• 输入均为整数。
• $1 \leq N \leq 5 \times 10^{5}$。

由 ChatGPT 5 翻译