양자 통신

Alice와 Bob은 양자 통신을 하고 있다. 두 사람이 쓰는 언어는 크기가 $n$인 사전 $S$이다. 사전의 각 단어 $s_i$ ($1 \le i \le n$)는 256비트 이진 문자열이며, gen 함수를 호출해서 생성할 수 있다. gen.cpp 파일을 참고해도 되고, 매개변수 $n$, $a_1$, $a_2$는 각 테스트 케이스에서 주어진다.

Alice와 Bob은 $m$ 라운드 동안 통신한다. 각 라운드에서 Alice는 사전의 단어를 정확히 하나 Bob에게 보낸다. 다만 통신 채널은 믿을 수 없어서 잡음의 영향을 받을 수 있다. 정확히 말하면, $i$번째 라운드에서 Alice가 보내려는 단어가 $x_i$라면 이진 문자열의 최대 $k_i$개 비트가 뒤집힐 수 있다. 즉 Bob이 받는 문자열 $y_i$는 $x_i$와 최대 $k_i$개 위치에서 다르다. $y_i$가 사전 $S$에 있어야 하는 것은 아니다.

Eve가 통신 채널에 침입해 통신을 조작한다. Eve는 Bob이 받을 문자열을 임의의 256비트 이진 문자열로 바꿀 수 있다. 이 문자열도 사전에 있을 필요는 없다. Eve가 모든 라운드를 조작하는 것은 아니다.

Bob은 각 라운드가 Eve의 조작을 받지 않았을 가능성이 있는지 알고 싶다. Bob이 받은 문자열과 잡음 임계값 $k_i$ ($0 \le k_i \le 15$)가 주어지면, 사전의 어떤 단어에서 최대 $k_i$개 비트를 뒤집어 받은 문자열을 얻을 수 있는지 판단한다. 가능하면 1을, 그렇지 않으면 0을 출력한다. 질의는 온라인으로 답해야 한다. 자세한 내용은 입력 부분을 참고한다.

첫 줄에 음이 아닌 정수 네 개 $n$, $m$, $a_1$, $a_2$가 주어진다. 각각 사전의 크기, 라운드 수, 함수 gen의 매개변수 $a_1$, $a_2$의 초기값이다. 사전은 gen 함수로 생성한다. gen.cpp의 코드를 복사해 사용해도 된다. 불리언 배열 s[N+1][256]에는 모든 단어가 들어 있다.

이어지는 $m$개 줄에는 길이 64의 16진수 문자열과 음이 아닌 정수 $k_i$가 주어진다. 16진수 문자열은 라운드 $i$에서 Bob이 최종적으로 받은 이진 문자열이고, $k_i$는 그 라운드의 잡음 임계값이다.

질의를 온라인으로 처리하도록 하기 위해, 16진수 문자열을 256비트 이진 문자열로 바꾼 뒤 lastans와 비트별로 XOR 연산을 해야 Bob이 실제로 받은 문자열을 얻을 수 있다. lastans는 $\{0,1\}$ 중 하나이며 직전 질의의 답이다. 첫 라운드 전 lastans의 값은 0이다.

16진수 한 자리는 4비트로 바꾼다. 예를 들어 5는 0101, A는 1010, C는 1100이 된다. 각 자리는 0-9와 대문자 A-F이며, A-F는 순서대로 10부터 15를 나타낸다.

unsigned long long 변수를 scanf나 printf로 읽거나 쓸 때는 llu를 사용한다.

$m$개의 줄을 출력한다. 각 줄에는 해당 질의에 대한 답인 0 또는 1을 출력한다.

모든 테스트 케이스에 대해 $1 \le n \le 4 \times 10^5$, $1 \le m \le 1.2 \times 10^5$, $0 \le k \le 15$이다. $a_1$과 $a_2$는 $[0,2^{64}-1]$ 범위에서 균등한 확률로 무작위 선택된다.