AB

Cerință

Alice tocmai s-a decis sa iși impresioneze fratele mai mic, Bob, cu abilitățile sale de deducție matematică. Astfel, ea așeaza într-o matrice cu $N$ linii si $M$ coloane toate numerele $1, 2, ..., N×M$, astfel încât fiecare linie, și respectiv fiecare coloană, să fie sortată strict crescător. O matrice cu aceste proprietăți se numește o matrice $AB$.
Alice îi cere apoi lui Bob să elimine $K$ valori din matrice, care să nu fie adiacente orizontal sau adiacente vertical. Apoi, ea va încerca să reintroducă aceste $K$ valori în matrice astfel încât să rămână o matrice $AB$. După câteva încercări, Alice realizează că, în anumite situații, pot exista mai multe moduri de a aranja cele $K$ numere pe pozițiile libere.
Scrieți un program care, cunoscând matricea $AB$ inițială și $Q$ interogări, constând fiecare dintr-o listă de elemente eliminate din matrice, determină pentru fiecare interogare dacă există o soluție unică de a aranja elementele eliminate în matrice astfel încât aceasta să fie matrice $AB$.

Date de intrare

Prima linie a datelor de intrare conține trei numere naturale $N$, $M$ și $Q$, separate prin câte un spațiu, având semnificația din enunț. Pe următoarele $N$ linii se află câte $M$ valori, separate prin câte un spațiu, reprezentând matricea $AB$ construită de Alice. Urmează apoi $Q$ interogări, fiecare interogare fiind descrisă pe două linii. Prima linie care descrie o interogare conține numărul natural $K$, reprezentând numărul de valori eliminate de către Bob. Pe a doua linie din descrierea interogării se află cele $K$ numere eliminate, separate prin câte un spațiu.

Date de ieșire

Veți afișa $Q$ linii, fiecare reprezentând un număr întreg. Cea de a $i$-a linie va conține răspunsul pentru a $i$-a interogare: răspunsul va fi $1$ dacă există o soluție unică de a aranja elementele eliminate astfel încât să se obțină o matrice $AB$, respectiv $0$ în caz contrar.

Restricții și precizări

• $1 \leq N, M \leq 2 \ 000$;
• $1 \leq Q \leq 25$;
• $K \geq 1$;
• Se garantează că în orice interogare numerele eliminate sunt distincte și respectă condiția din enunț (nu sunt adiacente orizontal sau vertical).
• Numărul total al valorilor din interogări nu depășește $4\ 000\ 000$.
• Punctajul pentru un test va fi acordat doar dacă răspunsurile pentru toate interogările din testul respectiv sunt corecte.

Exemplul 1

stdin

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

stdout

1
0

Explicație

Prima interogare presupune eliminarea numerelor 1, 5 și 9, matricea dupa eliminare arătând astfel:

? 2 4
3 ? 8
6 7 ?

Se observă că aranjarea celor trei numere este unică, obținându-se matricea originală.
A doua interogare presupune eliminarea valorilor 5, 4 și 6:

1 2 ?
3 ? 8
? 7 9

Rearanjarea nu este unica, o soluție alternativă fiind:

1 2 5
3 6 8
4 7 9