これはインタラクティブな問題です。
Plang Province では、$n = 300$ 人の学生が Plang OI 2026 に参加しました。そのうち、金メダルを獲得した学生とそうでない学生がいます。
Plang Province の学生には奇妙な習慣があります。金メダルを獲得しなかった場合、正直に「獲得していない」と言います。しかし、金メダルを獲得した場合、確率 $\frac{1}{2}$ で「獲得した」と言い、もう一方の確率 $\frac{1}{2}$ で「獲得していない」と言います。なお、各応答はランダムであり、以前の応答とは無関係です。
あなたは Plang Province のコーチとして、各学生が金メダルを獲得したかどうかを知りたいです。そのために、Una に以下の操作を行わせることができます：
- 互いに異なる学生を選び、Una にそれぞれの学生が金メダルを獲得したかどうかを尋ねさせます。Una は「はい」と答えた人数を教えてくれます。
Plang OI 2025 の金メダルラインは 571 点だったため、平均して 568 回未満のクエリで答えを見つける必要があります。
Plang OI の制限により、金メダルを獲得した学生はちょうど 48 人であると仮定できます。
画像 1：学生に隠した得点を尋ねるコーチ。
インタラクション
これはインタラクティブな問題です。各出力の後、必ず出力バッファをフラッシュしてください。出力バッファをフラッシュするには、以下を使用できます：
- C/C++ では
fflush(stdout)またはcout.flush() - Java および Kotlin では
System.out.flush() - Python では
sys.stdout.flush()
まず、テストケースの数 $T$ ($T = 20$) を示す整数を読み込みます。
各テストケースについて、学生の数 $n$ ($n = 300$) を示す整数を読み込みます。
クエリを行うには、"? $k$ $p_1$ $p_2$ ... $p_k$" ($1 \le p_i \le n$、$1 \le i < j \le k$ に対して $p_i \ne p_j$) という形式の行を出力します。
次に、Una が見つけた答えを示す整数を読み込みます。クエリが無効である場合、または合計で $568T$ 回を超えるクエリを行った場合、ジャッジプログラムは -1 を出力します。-1 を読み込んだら、未定義の動作を避けるためにすぐに終了してください。
答えが得られたら、"! $s_1s_2...s_n$" という形式の行を出力します。ここで、$s_i = 1$ は $i$ 番目の学生が金メダルを獲得したことを示し、$0$ はそうでないことを示します。
次に、OK または WA という単語を読み込み、答えが正しいかどうかを確認します。プログラムが WA を読み込んだ場合、未定義の動作を避けるためにすぐに終了してください。
ジャッジはアダプティブではないことに注意してください。つまり、クエリの後でも答えは変わりません。テストケースは最大で 10 個です。
入出力例
入力 1
1 2 0 0 1 OK
出力 1
? 2 1 2 ? 1 1 ? 1 2 ! 01
注記
この例は参照用であり、$T = 20$ および $n = 300$ を満たしておらず、最終テストには表示されません。
テストツールが提供されており、競技者は解法を開発およびテストできます。このツールは添付ファイルからダウンロードできます。「-h」オプションを付けてツールを実行すると、ツールの使用方法が説明されます。テストツールは一部のテストシナリオと、実際のジャッジプログラムの一部の機能のみを実装します。