| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 9 | 7 | 7 | 77.778% |
Given three arrays $f$, $g$, $h$ of length $2^m$, Bobo defines a cryptographic function $\mathrm{enc}(x, y) = (a, b)$ where
He also has $q$ questions $(a_1, b_1), \dots, (a_q, b_q)$.
For each $(a_i, b_i)$, find a pair of integers $(x, y)$ where $0 \leq x, y < 2^m$ and $\mathrm{enc}(x, y) = (a_i, b_i)$. It is guaranteed that for each $(a_i, b_i)$, there exists a unique pair $(x, y)$ satisfying the condition.
Note: $\oplus$ denotes the bitwise exclusive-or, i.e., xor.
The input consists of several test cases terminated by end-of-file. For each test case,
The first line contains two integers $m$ and $q$.
The second line contains $2^m$ integers $f[0], \dots, f[2^m - 1]$.
The third line contains $2^m$ integers $g[0], \dots, g[2^m - 1]$.
The forth line contains $2^m$ integers $h[0], \dots, h[2^m - 1]$.
For the following $q$ lines, the $i$-th line contains two integers $a_i$ and $b_i$.
For each question, output two integers which denote the found $x$ and $y$.
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
3 0 1 2 0 0