lumini

Privită din spațiu, harta insulei din povestea noastră are forma unui caroiaj pătratic cu $L$ linii și $L$ coloane. Liniile și coloanele sunt numerotate de la $1$ la $L$. În fiecare dintre cele $L \cdot L$ celule se află câte un far. Inițial cel de la poziția $1,1$ este aprins și toate respectă regula: orice far are farurile vecine (pe linie și coloană, deci maximum $4$) în starea opusă față de starea sa.

În urma unei furtuni, s-au întâmplat lucruri ciudate: fulgerele au lovit unul după altul și au afectat starea unor faruri.
Sunt trei tipuri de fulgere:

• Fulger de tip $1$. Pentru acesta se indică linia pe care lovește și el afectează starea farurilor de pe linia respectivă și de pe liniile cu număr de ordine mai mare. Mai exact, toate farurile de pe aceste linii își schimbă instantaneu starea.
• Fulger de tip $2$. Pentru acesta se indică un număr ce reprezintă coloana pe care lovește și el afectează starea farurilor de pe coloana respectivă și de pe coloanele cu număr de ordine mai mare. Mai exact, toate farurile de pe aceste coloane își schimbă instantaneu starea.
• Fulger de tip $3$. Pentru acesta se indică linia apoi coloana unui element din caroiaj. Toate farurile aflate pe aceeași paralelă cu diagonala secundară cu elementul specificat și pe paralelele cu diagonala secundară aflate sub aceasta, își schimbă starea.

Prin schimbarea stării unui far înțelegem că acesta se aprinde dacă este stins și se stinge dacă este aprins.

Cerință

Se dau date despre fulgere, în ordinea în care acestea acționează. Se cere ca la finalul furtunii să se indice care este starea anumitor faruri, aflate la coordonate precizate de pe insulă.

Date de intrare

Prima linie a fișierului lumini.in conține un numărul natural $L$, cu semnificația de mai sus. Pe linia a doua se află un număr natural $F$, reprezentând numărul de fulgere.

Pe următoarele $F$ linii se află date despre câte un fulger, în ordinea în care acestea apar. Primul număr de pe fiecare linie este tipul de fulger ($1$ sau $2$ sau $3$). Dacă acest număr este $1$ sau $2$, se mai află pe această linie un spațiu și încă un număr. Acesta reprezintă linia pe care lovește fulgerul (dacă linia din fișier are la început $1$), respectiv coloana pe care lovește fulgerul (dacă linia respectivă din fișier are la început $2$). Dacă este vorba despre fulger de tip $3$, pe acea linie se mai află două numere, reprezentând linia și coloana elementului de pe insulă unde lovește fulgerul, separate prin spațiu.

Linia următoare conține un număr $Q$. Pe următoarele $Q$ linii se află câte două numere (separate prin spațiu) reprezentând linia și coloana unui far de pe insulă pentru care se dorește aflarea stării după furtună.

Date de ieșire

Fișierul de ieșire lumini.out conține pe o linie, separate prin câte un spațiu, $Q$ numere, reprezentând rezultatele interogărilor în ordinea în care acestea apar în fișierul de intrare. Dacă farul corespunzător este aprins se va scrie valoarea $1$, iar dacă este stins se va scrie valoarea $0$.

Restricții și precizări

• $2 \leq L \leq 2 \ 000 \ 000 \ 000$;
• $1 \leq F \leq 1 \ 000$;
• Se garantează că la precizarea fulgerelor linia începe cu $1$, $2$ sau $3$, iar celelalte valori de pe liniile respective sunt cuprinse între $1$ și $L$ inclusiv.
• $1 \leq Q \leq 100 \ 000$;
• Se garantează că pentru fiecare far a cărei stare trebuie aflată linia și coloana sunt cuprinse între $1$ și $L$ inclusiv.
• Pentru $24$ de puncte, $L \leq 100$, $F \leq 100$ și apar doar fulgere de tipul $1$;
• Pentru alte $18$ puncte, $L \leq 100$, $F \leq 100$;
• Pentru alte $12$ puncte, $L \leq 10 \ 000$ și apar doar fulgere de tipul $1$;
• Pentru alte $8$ puncte, $L \leq 10 \ 000$;
• Pentru alte $13$ puncte, $L \leq 1 \ 000 \ 000$;
• Pentru restul de $25$ de puncte nu sunt restricții suplimentare.

Exemplu

lumini.in

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

lumini.out

1 0 0 1 0

Explicație

Inițial starea becurilor de pe insulă poate fi reprezentată astfel:
$\begin{matrix} 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 \\ 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 \end{matrix}$

După aplicarea primului fulger starea becurilor devine:

$\begin{matrix} 1 & 0 & 1 & 0 \\ \textbf{1} & \textbf{0} & \textbf{1} & \textbf{0} \\ \textbf{0} & \textbf{1} & \textbf{0} & \textbf{1} \\ \textbf{1} & \textbf{0} & \textbf{1} & \textbf{0} \end{matrix}$

După aplicarea celui de-al doilea fulger starea becurilor devine:

$\begin{matrix} 1 & 0 & \textbf{0} & \textbf{1} \\ 1 & \textbf{1} & \textbf{0} & \textbf{1} \\ \textbf{1} & \textbf{0} & \textbf{1} & \textbf{0} \\ \textbf{0} & \textbf{1} & \textbf{0} & \textbf{1} \end{matrix}$

După aplicarea celui de-al treilea starea becurilor devine:

$\begin{matrix} 1 & 0 & \textbf{1} & \textbf{0} \\ 1 & 1 & \textbf{1} & \textbf{0} \\ 1 & 0 & \textbf{0} & \textbf{1} \\ 0 & 1 & \textbf{1} & \textbf{0} \end{matrix}$