小 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 傳送字典入面恰好一個單詞。不過，兩人用嘅通訊通道唔可靠，會受雜訊干擾。具體嚟講，對第 $i$ 次傳送，將 Alice 傳送嘅原單詞記作 $x_i$，呢個 01 字串會受雜訊影響，最多翻轉 $k_i$ 位。換句話講，將 Bob 今次收到嘅 01 字串記作 $y_i$，佢同 $x_i$ 相比，最多可能有 $k_i$ 位唔同，而且 $y_i$ 可能唔喺字典 $S$ 入面。

同時，Bob 得知壞人 Eve 亦潛入咗兩人嘅通訊通道，準備干擾佢哋。佢嘅干擾方法係將 Bob 收到嘅 01 字串改成任意一個 256 位 01 字串，而且呢個字串可能唔喺字典 $S$ 入面。Eve 好狡猾，佢唔一定會干擾每次通訊。

而家 Bob 搵你幫手。對於之後每次通訊，你要根據 Bob 最後收到嘅 01 字串，同今次通訊嘅雜訊干擾門檻 $k_i$（$0\leq k_i\leq 15$），判斷今次通訊係咪有可能冇受到 Eve 干擾（即係 Bob 收到嘅 01 字串，可以由字典某個單詞翻轉最多 $k_i$ 位得到）。如果今次通訊有可能冇受到 Eve 干擾，請輸出 $1$，否則輸出 $0$。Bob 好信任你嘅能力，所以你要即時逐次回答結果，具體要求見輸入格式。

為咗減少讀入時間，Bob 收到嘅字串會用長度為 64 嘅十六進制字串畀出。十六進制字串包含數字字元 0 至 9 同大寫英文字母 A 至 F，其中字元 A 至 F 依次表示數值 $10$ 至 $15$。

十六進制字串可以逐位轉成 01 字串，例如：5 對應 0101，A 對應 1010，C 對應 1100。

輸入格式

由檔案 qi.in 讀入數據。

輸入數據第一行包含四個非負整數 $n,m,a_1,a_2$，分別表示字典大小、通訊次數，同 gen 函數參數 a1 同 a2 嘅初始值。

選手要喺自己嘅程式入面呼叫題目描述提到嘅 gen 函數，產生單詞表。選手可以複製並使用 gen.cpp 嘅程式碼，程式入面嘅布林陣列 s[N+1][256] 就係全部單詞。

之後 $m$ 行，每行包含一個長度為 64 嘅十六進制字串，同一個非負整數 $k_i$，分別表示第 $i$ 次通訊中 Bob 最後收到嘅 01 字串，同雜訊干擾門檻。

為咗強制選手即時逐次回答查詢，選手將十六進制字串還原成 256 位 01 字串之後，要將 01 字串每一位同 $lastans$ 做異或，先會得到今次通訊中 Bob 收到嘅真正 01 字串。其中 $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]$ 入面均勻隨機產生。