암호학

길이가 $2^m$인 세 배열 $f$, $g$, $h$가 주어진다. Bobo는 다음과 같이 암호 함수 $\mathrm{enc}(x, y) = (a, b)$를 정의한다.

$a = y \oplus g[x \oplus f[y]]$

$b = x \oplus f[y] \oplus h[y \oplus g[x \oplus f[y]]]$

Bobo에게는 $q$개의 질문 $(a_1, b_1), \dots, (a_q, b_q)$가 있다. 각 $(a_i, b_i)$에 대해 $\mathrm{enc}(x, y) = (a_i, b_i)$를 만족하는 정수 $(x, y)$를 $0 \le x, y < 2^m$ 범위에서 구한다. 각 질문마다 이 조건을 만족하는 쌍 $(x, y)$가 정확히 하나 존재함이 보장된다.

$\oplus$는 비트 단위 배타적 논리합(xor)을 뜻한다.

입력은 여러 개의 테스트 케이스로 이루어지며, 파일 끝(EOF)에서 끝난다. 각 테스트 케이스는 다음 형식으로 주어진다.

첫 줄에 정수 $m$과 $q$가 주어진다. 둘째 줄에 $2^m$개의 정수 $f[0], \dots, f[2^m - 1]$이 주어진다. 셋째 줄에 $2^m$개의 정수 $g[0], \dots, g[2^m - 1]$이 주어진다. 넷째 줄에 $2^m$개의 정수 $h[0], \dots, h[2^m - 1]$이 주어진다. 이어서 $q$개의 줄에 각각 정수 $a_i$와 $b_i$가 주어진다.

각 질문에 대해 구한 $x$와 $y$를 공백으로 구분하여 한 줄에 출력한다.

• $1 \le m \le 16$\n- $1 \le q \le 10^5$\n- 각 $0 \le i < 2^m$에 대해 $0 \le f[i], g[i], h[i] < 2^m$\n- 각 $1 \le i \le q$에 대해 $0 \le a_i, b_i < 2^m$\n- 한 입력에서 $2^m$의 합은 $10^5$를 넘지 않는다. $q$의 합도 $10^5$를 넘지 않는다.