N: 3人協力ゲーム

リアクティブ問題です。

問題文

$1000$ ビットの非負整数が $200$ 個あり、$a_1, \ldots, a_{100}, b_1, \ldots, b_{100}$ とします。

アリスは $a_1, \ldots, a_{100}$ を確認し、$3000$ ビットのメモ $X$ をチャーリーのために残します。

ボブは $b_1, \ldots, b_{100}$ を確認し、$3000$ ビットのメモ $Y$ をチャーリーのために残します。

チャーリーはメモ $X, Y$ の情報をもとに、$100$ 個の質問に答えます。

$i$ 番目の質問は $1000$ ビットの非負整数 $c_i$ で表され、チャーリーは $a_{x_i}$ と $b_{y_i}$ のビットごとの排他的論理和が $c_i$ に等しくなるような $x_i, y_i$ を答えます。

$100$ 個の質問のうち、$95$ 個以上の質問に正答できる戦略を考えてください。

制約

  • $a_1, \ldots, a_{100}, b_1, \ldots, b_{100}, c_1, \ldots, c_{100}$ は $2$ 進数表記で与えられ、01 からなる長さ $1000$ の文字列である。
  • $a_1, \ldots, a_{100}$ は互いに異なる。
  • $b_1, \ldots, b_{100}$ は互いに異なる。
  • $c_1, \ldots, c_{100}$ は互いに異なる。
  • $i = 1, 2, \ldots, 100$ について、$a_j$ と $b_k$ のビットごとの排他的論理和が $c_i$ になるような $j, k$ が存在する。

入出力とジャッジ

あなたのプログラムは $1$ つのテストケースに対して $3$ 回実行される。

$1$ 回目の実行では次の入力形式でアリスへの情報が与えられる。

Alice
$a_1$
$a_2$
$\vdots$
$a_{100}$

$1$ 行目に必ず Alice の文字列が与えられる。 この場合、入力を全て受け取った後 01 からなる長さ $3000$ の文字列 $X$ を出力し、プログラムを即座に終了させなければならない。

$2$ 回目の実行では次の入力形式でボブへの情報が与えられる。

Bob
$b_1$
$b_2$
$\vdots$
$b_{100}$

$1$ 行目に必ず Bob の文字列が与えられる。 この場合、入力を全て受け取った後 01 からなる長さ $3000$ の文字列 $Y$ を出力し、プログラムを即座に終了させなければならない。

$3$ 回目の実行では次の入力形式でチャーリーへの質問およびメモの情報が与えられる。

Charlie
$X$
$Y$
$c_1$
$c_2$
$\vdots$
$c_{100}$

$1$ 行目に必ず Charlie の文字列が与えられる。 入力を全て受け取った後 $1$ 以上 $100$ 以下の整数 $x_1, x_2, \ldots, x_{100}$ と $1$ 以上 $100$ 以下の整数 $y_1, y_2, \ldots, y_{100}$ を以下の形式で出力し、プログラムを即座に終了させなければならない。

$x_1$ $y_1$
$x_2$ $y_2$
$\vdots$
$x_{100}$ $y_{100}$

ジャッジは、$i = 1, 2, \ldots, 100$ について $a_{x_i}$ と $b_{y_i}$ のビットごとの排他的論理和が $c_i$ に一致するか調べ、一致数が $95$ 個以上であれば正答、そうでなければ誤答と判定する。

不正な値や不正な形式での出力があった場合にも誤答とする。

注意

  • 出力の度に標準出力を flush せよ。そうしない場合、TLE となる可能性がある。
  • どの種類の入力の末尾にも EOF が与えられる。
  • プロセスは、上記によって規定された以外のいかなる通信も行ってはならない。

入出力例1

以下はビット数や非負整数の数、質問の数が異なるが、$a = (000, 011), b = (110, 111), c = (101, 100)$ としたときの対話例である。

解答プログラムの出力 解答プログラムへの入力 説明
解答プログラム(アリス)が実行される
Alice
$000$
$011$
アリスは $a = (000, 011)$ の情報を得る
$0000110\ldots 0$ アリスはメモ $X = 0000110\ldots 0$ を残す
解答プログラム(アリス)の実行が終了し、新たな解答プログラム(ボブ)が実行される
Bob
$110$
$111$
ボブは $b = (110, 111)$ の情報を得る
$1101110\ldots 0$ ボブはメモ $Y = 1101110\ldots 0$ を残す
解答プログラム(ボブ)の実行が終了し、新たな解答プログラム(チャーリー)が実行される
Charlie
$0000110\ldots 0$
$1101110\ldots 0$
$101$
$100$
チャーリーは $X, Y$ の情報を得たあと、質問の情報 $c = (101, 100)$ を得る
$2$ $1$
$2$ $2$
チャーリーは $1$ つ目の質問に対して $(x_1, y_1) = (2, 1)$、$2$ つ目の質問に対して $(x_2, y_2) = (2, 2)$ と回答する