メモ

これはAdvent Calendar Contest 2020の3日目用の問題です。
Codeforces Round #654(Div.2) の没問のうちのひとつです。

問題文

この問題はインタラクティブな問題です。

$A=\{A_1,A_2,...,A_{N^2-N}\}$ は $\{N,N+1,...,N^2-1\}$ を丁度 $1$ つずつ含む順列です。 (これらは $N$ 進法で丁度 $2$ 桁の数です。)
以下のクエリを用いて、この順列を特定してください。

? $i$ $j$

1. $p = \lfloor A_i/N \rfloor - \lfloor A_j/N \rfloor $とする。直感的には、$p$ を $N$ 進法での( $A_i$ の $N$ の位) $-$ ( $A_j$ の $N$ の位)とする。
2. $q = A_i\%N - A_j\%N$ とする。直感的には、$q$ を $N$ 進法での( $A_i$ の $1$ の位) $-$ ( $A_j$ の $1$ の位)とする。
3. もし $p>q$ であるなら、 $p,q$ を入れ替える。
4. $p$,$q$ の組をこの順に空白区切りで返答する。

! $A_1$ $A_2$ ... $A_{N^2-N}$

入出力

はじめに、整数 $N$ が $1$ 行で与えられます。 $N$ は $2 \le N \le 50$ である整数です。
その後、あなたはいくつかのクエリを実行することができます。各クエリ毎に $1$ 行に出力し、最後に改行してください。
? クエリごとに、返答が $1$ 行で与えられます。
! クエリに対しては、返答はありません。クエリを出力した後、直ちにプログラムを終了してください。
出力ごとに、プログラム内でflushを行う必要があります。 flushの方法について、一部の言語については、こちらの例を参照することができます。

注意

この問題のジャッジは、適応的(adaptive)である可能性があります。
ジャッジが適応的であるとは、以下のような項目を満たすようなジャッジを指します。

• ジャッジは、最初、何らかの解を想定して、提出されたプログラムへの返答を行う。
• ジャッジは、任意のタイミングで、今までの返答と整合性がとれる限り、想定している解を変更する可能性がある。

サンプル

2

-1 0

? 2 1

! 3 2

3

1 2

? 4 1

! 3 5 4 8 7 6