Dominoes

Se dă o matrice cu $2$ linii și $n$ coloane care are $k$ celule ocupate.

Se dau $q$ interogări de forma $(x_1, y_1, x_2, y_2)$, cu următoarea semnificație: dacă se ocupă două celule libere distincte ale matricii inițiale, $(x_1, y_1)$ și $(x_2, y_2)$, se poate pava complet matricea cu piese de domino de dimensiuni $2 \times 1$ și $1 \times 2$? După efectuarea unei interogări celulele ocupate asociate acesteia vor deveni din nou libere (modificările aduse matricii nu persistă între interogări).

Cerință

Să se determine, pentru fiecare interogare, dacă este posibil ca matricea să fie pavată complet cu piese de domino de dimensiuni $2 \times 1$ și $1 \times 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 $x_1$, $y_1$, $x_2$ și $y_2$, 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 \leq x, x_1, x_2 \leq 2$
• $1 \leq y, y_1, y_2 \leq n$
• $0 \leq k \leq 100 \ 000$, $k$ par
• $1 \leq q \leq 100 \ 000$
• $1 \leq n \leq 1 \ 000 \ 000 \ 000$

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, în ordinea din input, cu negru fiind marcate celulele blocate:

Figura 1 din enunțul original al problemei Dominoes.Mărește schema ↗

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:

Figura 2 din enunțul original al problemei Dominoes.Mărește schema ↗

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:

Figura 3 din enunțul original al problemei Dominoes.Mărește schema ↗