小 Z は量子コンピュータについて独学しており、最近、量子通信の章を研究していて面白い問題に出会いました。この問題では、Alice と Bob が量子通信を行います。通信に使う言語は、サイズ $n$ の辞書 $S$ です。辞書内の各単語 $s_i$（$1 \leq i \leq n$）は、256 ビットの 01 文字列で表せます。この問題では、$s_i$ は関数 gen を呼び出して生成できます。問題ディレクトリ内の gen.cpp で確認してください。この関数のパラメータ n、a1、a2 は入力で与えられます。
Alice と Bob は、この後 $m$ 回の通信を行います。各通信では、Alice が Bob に辞書内の単語をちょうど 1 個送ります。しかし、2 人が使う通信路は信頼できず、雑音の影響を受けます。具体的には、$i$ 回目に Alice が送る元の単語を $x_i$ とすると、この 01 文字列は雑音によって最大 $k_i$ ビット反転します。つまり、Bob が受け取る 01 文字列を $y_i$ とすると、$x_i$ と異なるビットが最大 $k_i$ 個あり得ます。また、$y_i$ は辞書 $S$ に含まれない可能性があります。
一方、Bob は悪者の Eve も通信路に侵入し、通信を妨害しようとしていることを知りました。Eve は、Bob が受け取る 01 文字列を任意の 256 ビットの 01 文字列に変えて妨害します。この文字列も辞書 $S$ に含まれない可能性があります。Eve は非常にずる賢く、毎回の通信を妨害するとは限りません。
Bob はあなたに助けを求めました。これから行う各通信について、Bob が最終的に受け取った 01 文字列と、通信の雑音の上限 $k_i$（$0 \leq k_i \leq 15$）から、Eve の妨害を受けていない可能性があるかどうかを判定してください。すなわち、Bob が受け取った文字列が、辞書内のいずれかの単語を高々 $k_i$ ビット反転して得られるかどうかです。妨害を受けていない可能性があれば $1$、そうでなければ $0$ を出力してください。Bob はあなたの能力を信頼しているため、オンラインで答える必要があります。具体的な要件は入力の説明を参照してください。
読み込み時間を減らすため、Bob が受け取る文字列は、長さ 64 の 16 進文字列として与えられます。16 進文字列には数字 0 から 9 と大文字の英字 A から F が含まれ、A から F は順に値 $10 \sim 15$ を表します。
16 進文字列は 1 桁ずつ 01 文字列に変換できます。例えば、5 は 0101、A は 1010、C は 1100 に対応します。
入力
ファイル qi.in からデータを読み込んでください。
1 行目には、4 つの非負整数 $n,m,a_1,a_2$ が与えられ、辞書のサイズ、通信回数、関数 gen のパラメータ a1 と a2 の初期値をそれぞれ表します。
プログラム内で、問題文に記載した関数 gen を呼び出して単語表を生成してください。gen.cpp のコードをコピーして使えます。プログラム内のブール型配列 s[N+1][256] が、すべての単語を表します。
続く $m$ 行には、それぞれ長さ 64 の 16 進文字列と非負整数 $k_i$ が与えられ、$i$ 回目の通信で Bob が最終的に受け取った 01 文字列と雑音の上限を表します。
オンラインでクエリに答えることを強制するため、16 進文字列を 256 ビットの 01 文字列に戻した後、各ビットと $lastans$ の排他的論理和を取って初めて、この通信で Bob が実際に受け取った文字列が得られます。$lastans \in \{0,1\}$ は直前のクエリの答えで、最初のクエリの前は $lastans=0$ です。
注意：scanf と printf で unsigned long long 型の変数を読み込み、または出力するとき、対応する書式指定子は llu です。
出力
ファイル qi.out に出力してください。
全部で $m$ 行出力し、各行に現在のクエリの答えを表す整数 $0$ または $1$ を出力してください。
クエリの例
説明を簡単にするため、辞書の単語を直接与え、単語の長さを 4 に減らし、オフラインでクエリに答えてもよいとするなど、簡略化した状況を例にします。
辞書のサイズが $n=2$ で、単語が 1010 と 0111 である場合を考えます。
クエリ B = 1011、$k_1=1$ に対する答えは $1$ です。1010 の 4 番目のビットを反転すれば得られます（ビットは上位から下位へ数え、以下も同様です）。
クエリ 1 = 0001、$k_2=2$ に対する答えは $1$ です。0111 の 2 番目と 3 番目のビットを反転すれば得られます。
クエリ 1 = 0001、$k_3=1$ に対する答えは $0$ です。
1010を高々 1 ビット反転して得られるのは、1010、0010、1110、1000、1011です。0111を高々 1 ビット反転して得られるのは、0111、1111、0011、0101、0110です。1 = 0001は得られないため、必ず Eve の妨害によって生じたものです。
入出力例
入出力例 1
選手用ディレクトリ内の qi/qi1.in と qi/qi1.ans を参照してください。
入出力例 2
選手用ディレクトリ内の qi/qi2.in と qi/qi2.ans を参照してください。
入出力例 3
選手用ディレクトリ内の qi/qi3.in と qi/qi3.ans を参照してください。
制約
すべてのテストケースで、$1 \leq n \leq 4\times 10^5$、$1 \leq m \leq 1.2\times 10^5$、$0 \leq k \leq 15$ です。$a_1,a_2$ は $[0,2^{64}-1]$ 内で一様ランダムに生成されます。
| テストケース番号 | $n=$ | $m=$ | $k_i \leq$ | 特別な性質 |
|---|---|---|---|---|
| $1$ | $10$ | $10$ | $2$ | なし |
| $2$ | $500$ | $500$ | $15$ | なし |
| $3$ | $1{,}000$ | $1{,}000$ | $0$ | なし |
| $4$ | $2{,}000$ | $2{,}000$ | $2$ | なし |
| $5$ | $5{,}000$ | $5{,}000$ | $15$ | なし |
| $6$ | $10{,}000$ | $10{,}000$ | $15$ | なし |
| $7$ | $20{,}000$ | $20{,}000$ | $15$ | なし |
| $8$ | $100{,}000$ | $100{,}000$ | $1$ | なし |
| $9$ | $400{,}000$ | $120{,}000$ | $1$ | なし |
| $10$ | $50{,}000$ | $50{,}000$ | $2$ | なし |
| $11$ | $70{,}000$ | $70{,}000$ | $3$ | なし |
| $12$ | $100{,}000$ | $100{,}000$ | $2$ | なし |
| $13$ | $30{,}000$ | $30{,}000$ | $5$ | なし |
| $14$ | $60{,}000$ | $60{,}000$ | $4$ | なし |
| $15$ | $120{,}000$ | $120{,}000$ | $5$ | なし |
| $16$ | $60{,}000$ | $60{,}000$ | $8$ | すべてのクエリ文字列をランダムに生成 |
| $17$ | $120{,}000$ | $120{,}000$ | $12$ | すべてのクエリ文字列をランダムに生成 |
| $18$ | $400{,}000$ | $100{,}000$ | $15$ | すべてのクエリ文字列をランダムに生成 |
| $19$ | $30{,}000$ | $30{,}000$ | $7$ | なし |
| $20$ | $60{,}000$ | $60{,}000$ | $9$ | なし |
| $21$ | $90{,}000$ | $90{,}000$ | $11$ | なし |
| $22$ | $200{,}000$ | $120{,}000$ | $12$ | なし |
| $23$ | $400{,}000$ | $80{,}000$ | $15$ | なし |
| $24$ | $400{,}000$ | $100{,}000$ | $15$ | なし |
| $25$ | $400{,}000$ | $120{,}000$ | $15$ | なし |