Two Prisoners and 01 Array

問題文

この問題は $2$ ステップ問題（あなたの作成したプログラムが独立して $2$ 回実行される形式の問題）です。

Alice と Bob として振る舞い、以下の手続きを成功させてください。

1. Alice と Bob に、正整数 $N$ が与えられる。
2. Alice のみに、長さ $2^N$ の $01$ 列 $B$ と $0$ 以上 $2^N - 1$ 以下の整数 $X$ が与えられる。
3. Alice は、 $B$ とのハミング距離が高々 $1$ である長さ $2^N$ の $01$ 列 $B'$ を Bob に伝える。
4. Bob は、 Alice が教えられた整数 $X$ を復元する。

$1$ 回の実行につき、 $T$ 個のテストケースが与えられます。

制約

• $1 \le T \le 100$
• $1 \le N \le 10$
• $0 \le X \le 2^N - 1$
• $B_i ~ (1 \le i \le 2^N)$ は $0$ または $1$
• $T, N, X, B_i$ は整数

1回目の実行

$1$ 回目の実行において、あなたのプログラムは Alice として振る舞う必要がある。

$1$ 回目の実行の入力は以下の形式で標準入力から与えられる。

$1$ 回目の実行における各テストケース $\mathrm{case}_{1, t} ~ (1 \le t \le T)$ は以下の形式で与えられる。

その後、各テストケースに対する出力を以下の形式で出力せよ。

各テストケースに対する出力 $\mathrm{output}_{1, t}$ として、 Bob に伝える長さ $2^N$ の $01$ 列 $B'$ を以下の形式で出力せよ。

2回目の実行

$2$ 回目の実行において、あなたのプログラムは Bob として振る舞う必要がある。

$2$ 回目の実行の入力は以下の形式で標準入力から与えられる。

$2$ 回目の実行における各テストケース $\mathrm{case}_{2, t} ~ (1 \le t \le T)$ は以下の形式で与えられる。

ここで、 $B' = (B'_1, B'_2, \cdots, B'_{2^N})$ は $1$ 回目の実行で Alice が Bob に伝えた $B'$ である。

その後、各テストケースに対する出力を以下の形式で出力せよ。

各テストケースに対する出力 $\mathrm{output}_{2, t}$ として、復元した後の $X$ を以下の形式で出力せよ。

サンプル 1

1 回目の入力

Alice
3
1 0
0 1
2 1
0 1 0 1
4 15
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

1 回目の出力

0 0
0 1 0 0
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0

どのテストケースでも、 $B'$ と $B$ のハミング距離は $1$ です。条件を満たす $B'$ であれば、これ以外を出力しても構いません。

2 回目の入力

Bob
3
1
0 0
2
0 1 0 0
4
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0

$1$ 回目に上の出力をした場合の入力です。

2 回目の出力

0
1
15