AT_utpc2024_f Fourier Coefficients

この問題は**インタラクティブな問題**（あなたの作成したプログラムとジャッジプログラムが標準入出力を介して対話を行う形式の問題）です。ジャッジプログラムの実行は最大で $ 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 $ を、 $ 0 $ 以上 $ 998244353 $ 未満の整数であって、 $ Z_i Q_i \equiv P_i \pmod{998244353} $ を満たす整数として定義します。なお、このような $ Z_i $ は常に存在して一意であることが示せます。 ### Input & Output Format この問題はインタラクティブな問題（あなたの作成したプログラムとジャッジプログラムが標準入出力を介して対話を行う形式の問題）です。 最初に、 $ 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} $

N/A

N/A

### 注意点 - **出力を行うたびに、末尾に改行を入れて標準出力を flush してください。そうしなかった場合、ジャッジ結果が 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) $ を出力します。 ### Constraints - 入力は全て整数 - $ 1 \leq N \leq 5 \times 10^{5} $