• 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ța

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 ≤ L ≤ 2.000.000.000
• 1 ≤ F ≤ 1000
• 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 ≤ Q ≤ 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 ≤ 100, F ≤ 100 și apar doar fulgere de tipul 1;
• Pentru alte 18 puncte, L ≤ 100, F ≤ 100;
• Pentru alte 12 puncte, L ≤ 10.000 și apar doar fulgere de tipul 1;
• Pentru alte 8 puncte, L ≤ 10.000;
• Pentru alte 13 puncte, L ≤ 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:
1 0 1 0
0 1 0 1
1 0 1 0
0 1 0 1
După aplicarea primului fulger starea becurilor devine
1 0 1 0
1 0 1 0
0 1 0 1
1 0 1 0
După aplicarea celui de-al doilea fulger starea becurilor devine
1 0 0 1
1 1 0 1
1 0 1 0
0 1 0 1
După aplicarea celui de-al treilea starea becurilor devine
1 0 1 0
1 1 1 0
1 0 0 1
0 1 1 0