给定三个长度为 $2^m$ 的数组 $f, g, h$，Bobo 定义了一个加密函数 $\text{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]]]$.

他还有 $q$ 个询问 $(a_1, b_1), \dots, (a_q, b_q)$。 对于每个 $(a_i, b_i)$，找到一对整数 $(x, y)$，满足 $0 \le x, y < 2^m$ 且 $\text{enc}(x, y) = (a_i, b_i)$。保证对于每个 $(a_i, b_i)$，都存在唯一的一对 $(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$ 行，第 $i$ 行包含两个整数 $a_i$ 和 $b_i$。

数据范围

• $1 \le m \le 16$
• $1 \le q \le 10^5$
• $0 \le f[i], g[i], h[i] < 2^m$，对于每个 $0 \le i < 2^m$
• $0 \le a_i, b_i < 2^m$，对于每个 $1 \le i \le q$
• 在每组输入中，$2^m$ 的总和不超过 $10^5$，$q$ 的总和不超过 $10^5$。

输出格式

对于每个询问，输出两个整数，表示找到的 $x$ 和 $y$。

样例

输入格式 1

2 2
0 1 2 3
1 2 3 0
2 3 0 1
0 1
2 3
1 1
0 0
0 0
0 0
0 0

输出格式 1

3 0
1 2
0 0