Se dă o matrice cu 2 linii si n coloane care are k celule ocupate. Se dau q interogări de forma (x1, y1, x2, y2), cu următoarea semnificație: dacă se ocupă două celule libere distincte ale matricii inițiale, (x1, y1) și (x2, y2), se poate pava complet matricea cu piese de domino de dimensiuni 2 x 1 și 1 x 2? După efectuarea unei interogări celulele ocupate asociate acesteia vor deveni din nou libere (modificările aduse matricei nu persistă între interogări).

Cerința

Să se determine, pentru fiecare interogare, dacă este posibil ca matricea să fie pavată complet cu piese de domino de dimensiuni 2 x 1 și 1 x 2.

Date de intrare

Pe prima linie a fișierului dominoes.in se află n și k. Pe următoarele k linii se află coordonatele pozițiilor ocupate, de forma (x, y). Pe a (k + 2)-a linie se află q. Pe fiecare dintre următoarele q linii se găsesc valorile x1, y1, x2 și y2, separate prin câte un spațiu, cu semnificația din cerință.

Date de ieșire

Fișierul de ieșire dominoes.out va conține q linii, pe fiecare linie aflându-se răspunsul (1 dacă se poate, respectiv 0 dacă nu se poate) corespunzător câte unei interogări, în ordinea în care acestea se găsesc în fișierul de intrare.

Restricții și precizări

• Se garantează faptul că matricea inițială se poate pava complet cu piese de domino.
• 1 ≤ x, x1, x2 ≤ 2
• 1 ≤ y, y1, y2 ≤ n
• 0 ≤ k ≤ 100.000, k par
• 1 ≤ q ≤ 100.000
• 1 ≤ n ≤ 1.000.000.000
• Pentru 9 puncte, n, k, q ≤ 8
• Pentru 6 puncte, k = 0
• Pentru 11 puncte, n, k, q ≤ 5000
• Pentru 12 puncte, k, q ≤ 5000
• Pentru 23 de puncte, n ≤ 100.000
• Pentru 6 puncte, y1 = y2 pentru fiecare interogare
• Pentru 8 puncte, y1 ≠ y2 pentru fiecare interogare
• Pentru 25 de puncte, fără alte restricții suplimentare

Exemplul 1:

dominoes.in

5 2
1 1
2 5
4
1 3 2 3
2 1 1 5
2 3 2 4
1 2 2 4

dominoes.out

0
1
1
1

Explicație

Dedesubt se găsesc configurațiile matricei pentru fiecare interogare, in ordinea din input, cu negru fiind marcate celulele blocate:

Exemplul 2:

dominoes.in

6 4
1 1
2 3
1 4
2 6
3
1 2 2 2
1 2 1 3
1 2 1 5

dominoes.out

0
1
0

Explicație

Configurațiile matricei pentru fiecare interogare:

Exemplul 3:

dominoes.in

6 2
1 1
2 3
3
1 4 2 6
1 4 2 5
1 3 2 5

dominoes.out

1
0
0

Explicație

Configurațiile matricei pentru fiecare interogare: