問題 G XOR 回路

問題文

計算機科学実験及演習 3 は CAD を用いて CPU を設計する授業である．CPU は多くの回路を組み合わせなければ動かず，その中の 1 つに n ビット入力の XOR 回路がある．ここで XOR 回路とは，入力ビット列 x₁x₂...x_n に対して，x₁ + x₂ + ... + x_n\ (mod 2) を出力する回路のことを言う．しかし完璧に動作する XOR 回路を設計するのは時間がかかるので，とりあえず n ビットのうち k ビットだけ使う XOR 回路 A を作ることにした．つまり，ある i₁, ... , i_k が存在し，回路 A は x_i1 + x_i2 + ... + x_ik\ (mod 2)を出力する．

暫く後に今度は k ビット入力の XOR 回路が欲しくなった．何だ簡単ではないか．先ほどの回路 A を使えばよい．ただ残念なことに，回路 A がどの k ビットを使っていたのか忘れてしまった上に，回路 A の設計図も間違って削除してしまった．しかしコンパイル済みの回路 A は残っている．なので，入力 x₁x₂...x_n を入れて回路 A を実行することで，その出力 x_i1 + x_i2 + ... + x_ik\ (mod 2) を見ることは出来る． 出来るだけ作業の時間を短くしたいので，回路 A の実行回数には上限を設定することにしよう．どうすれば回路Aが依存しているビット i₁, ... , i_k を見つけられるだろうか？

入出力

最初に n と k がスペース区切りで与えられる．以降，プログラムは回路 A に入力を与え，その出力を読むことが出来る．例えば C/C++ で回路 A にビット列 x₁x₂...x_n を与えるには

printf("?x1x2...xn\n"); fflush(stdout);

scanf("%d", &v);

printf("!i1 i2 ...ik\n"); fflush(stdout);

制約

• 1 ≤ n ≤ 10,000
• 1 ≤ k ≤ min(10, n)
• 各データセットごとに，回路 A の実行回数の上限は 200 回であり，それを超えると誤答 (Query Limit Exceeded) と判定される．

入出力例

入力例 1

以下の例はプログラムの入出力の例である．左の列はプログラムの出力，右の列はプログラムへの入力を時系列順に示している．最初に n k が入力として与えられる．ここでは n = 2, k = 1 である．次に回路 A に 00 という入力をいれると，回路 A は 0 を返した．次に回路 A に 01 という入力をいれると，回路 A は再び 0 を返した．このことから回路 A は 1 ビット目のみ利用していることが分かり，プログラムは 1 を解答として出力した．

入力例 2

以下の例では，n = 2, k = 2 であり，直ちに回路 A が 1 ビット目と 2 ビット目の両方を利用していることが分かる．よってプログラムは 1 と 2 を解答として出力した．