問題 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_i₁ + x_i₂ + ... + x_{i_k}\ (mod 2)を出力する．

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

入出力

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

printf("?x₁x₂...x_n\n"); fflush(stdout);

とする．ここで各 x_i の間にスペースをいれてはならない．次に，

scanf("%d", &v);

とすると v に対応する出力 x_i₁ + x_i₂ + ... + x_{i_k}\ (mod 2) が入る．最終的に回路 A が依存するビット i₁,...,i_k を出力するには

printf("!i₁ i₂ ...i_k\n"); fflush(stdout);

とする．ここで各 i_j の間はスペースを丁度 1 つずついれる．

制約

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 1
?00
	0
?01
	0
!1

入力例 2

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

プログラムの出力	プログラムへの入力
	2 2
!1 2