Fişierul intrare/ieşire:	xortransform.in, xortransform.out	Sursă	Lot Seniori Tulcea 2018, baraj 2
Autor	Bogdan Ciobanu, Bogdan Iordache	Adăugată de	Tamio Vesa Nakajima •tamionv
Timp execuţie pe test	1.25 sec	Limită de memorie	256000 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Xortransform

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).
Să se răspundă la Q întrebări de forma: care este valoarea de pe prima linie și prima coloană, dacă aplicăm K transformări asupra matricei inițiale.

Date de intrare

Pe primul rând al fişierului de intrare xortransform.in se vor găsi N, M şi Q
Pe următoarele N rânduri se vor găsi elementele matricii, câte M pe fiecare rând.
Pe următoarele Q rânduri se vor găsi valorile K ce ne intereseaza, codificate astfel: dacă valoarea citită este X, şi răspunsul la interogarea precedentă este Y (Y = 0 daca este vorba de prima interogare), atunci valoarea lui K în această interogare este X xor Y.

Date de ieşire

Fişierul de ieşire xortransform.out va conţine răspunsurile celor Q interogări, câte unul pe un rând.

Restricţii și precizări

• 1 ≤ N*M ≤ 2 500 000
• 1 ≤ elementele matricii ≤ 2³⁰
• 1 ≤ K ≤ 1 000 000 000
• Q ≤ 1 000 000

Exemplu

Explicaţii

Valorile lui K pentru cele 3 interogări sunt, în ordine: 3, 18, 100.

Cum se trimit solutii?