問題文

この問題はインタラクティブな問題（あなたの作成したプログラムとジャッジプログラムが標準入出力を介して対話を行う形式の問題）です。ジャッジプログラムの実行は最大で 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 と定められる。

制約

• 入力は全て整数
• 1 \leq N \leq 5 \times 10^{5}

入出力

この問題はインタラクティブな問題（あなたの作成したプログラムとジャッジプログラムが標準入出力を介して対話を行う形式の問題）です。

最初に、N を標準入力から受け取ってください。

N

その後、条件を満たすような (X_1, Y_1), \dots, (X_N, Y_N) を標準出力に以下の形式で出力してください。

X_1 Y_1
X_2 Y_2
\vdots
X_N Y_N

出力が正当な場合、返答が以下の形式で標準入力から与えられます。

Z_1
Z_2
\vdots
Z_N

出力が不正な場合、返答の代わりに -1 が与えられます。

-1

-1 が入力に与えられた場合、直ちにプログラムを終了してください。

その後、答えを標準出力に以下の形式で出力してください。

A_0
A_1
\vdots
A_{N-1}

注意点

• 出力を行うたびに、末尾に改行を入れて標準出力を flush してください。そうしなかった場合、ジャッジ結果が TLE となる可能性があります。
• 対話の途中で不正な出力を行った、あるいはプログラムが途中で終了した場合のジャッジ結果は不定です。
• 答えを出力したら（または -1 を受け取ったら）直ちにプログラムを正常終了してください。そうしなかった場合、ジャッジ結果は不定です。
• 特に、余計な改行も不正なフォーマットの出力とみなされるので注意してください。
• ジャッジは適応的ではありません。つまり、整数 A_0, \dots, A_{N - 1} は対話の開始時に固定され、対話の途中で変更されることはありません。

入出力例

以下は N = 2 および (A_0, A_1) = (3, 2) の場合の入出力例です。