Alice tocmai s-a decis să-și impresioneze fratele mai mic, Bob, cu abilitățile sale de deducție matematică. Astfel, ea așează într-o matrice cu N linii și 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 sa nu fie adiacente orizontal sau adiacente vertical. Apoi, ea va încerca să reintroducă aceste K valori în matrice astfel încât sa 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.

Cerința

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 ≤ N, M ≤ 2.000
• 1 ≤ Q ≤ 25
• K ≥ 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.
• Datorită dimensiunilor mari ale datelor de intrare, doar unele teste au fost adăugate.

Exemplu:

Intrare

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

Ieșire

1
0

Explicație

Prima interogare presupune eliminarea numerelor 1, 5 și 9, matricea după 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 unică, o soluție alternativă fiind:
1 2 5
3 6 8
4 7 9