Se dă o matrice de numere naturale cu $N$ linii și $M$ coloane. Prin intermediul unei transformări putem obține o altă matrice de $N$ linii și $M$ coloane astfel: fiecare element de coordonate $(i, j)$ cu $0 ≤ i < N$, $0 ≤ j < M$, din matricea nou obținută va fi egal cu suma xor a valorilor de la următoarele patru poziții $(i, j)$, $(i+1, j)$, $(i, j+1)$, $(i+1, j+1)$ din matricea inițială (dacă vreuna din pozițiile respective este în afara matricei, valoarea de la acea poziție se va considera $0$).

Cerinţă

Dându-se o matrice cu $N$ linii și $M$ coloane, să se răspundă la întrebări de forma: care este valoarea de pe prima linie și prima coloană, dacă aplicăm $K$ transformări asupra matricei inițiale.

Interacțiune

Trebuie să implementați funcțiile

void initialize(int N, int M, int **matrice);

Funcția primește ca parametri dimensiunile matricei și matricea. Aceasta nu trebuie să returneze nimic.

int query(int K);

Funcția primește ca parametru valoarea $K$ pentru o întrebare, și trebuie să returneze răspunsul la întrebare, după cum este descris în enunț.
Interactorul va citi datele din fișierul de intrare $xortransform.in$ și va afișa răspunsurile la funcția query în fișierul de ieșire $xortransform.out$ în formatul observabil în exemplu.

Restricţii și precizări

• $1 ≤ N \times M ≤ 2\ 500\ 000$
• $1 ≤ matrice[x][y] ≤ 2^{30}$, pentru orice $0 ≤ x < N$ și $0 ≤ y < M$.
• $1 ≤ K ≤ 1\ 000\ 000\ 000$
• Funcția query va fi apelată de maxim $1\ 000\ 000$ de ori în cadrul unui test.

Exemplu

xortransform.in

4 5 3
9 8 1 3 6
1 2 5 2 5
3 4 3 7 7
7 8 3 5 1
3
18
100

xortransform.out

13
8
15

Explicații

Formatul datelor de intrare

N M Q
A0,0 A0,1 … A0,M-1
A1,0 A1,1 … A1,M-1
…
AN-1,0 AN-1,1 … AN-1,M-1
K1
K2
…
KQ