Cerința

Se consideră o tablă de șah de dimensiune n (alcătuită din n linii si n coloane), pe care se află m piese de șah, fiecare putând fi: pion, rege, regină, nebun, tură sau cal). Se dau coordonatele a t căsuțe de pe tablă și se cere să se verifice pentru fiecare dacă este atacată, ocupată sau neatacată de piesele care se află pe tablă .

Date de intrare

Fișierul de intrare piesesah.in conține pe prima linie trei numere n m t. Următoarele m linii conțin un caracter, literă mică (reprezentând tipul piesei) urmat de două numere naturale reprezentând coordonatele piesei. Următoarele t linii conțin câte două numere naturale reprezentând coordonatele unei căsuțe care trebuie verificată.

Date de ieșire

Fișierul de ieșire piesesah.out va conține pe t linii câte un singur număr natural 0 , 1 sau 2, după cum căsuța corespunzătoare este neatacată, atacată sau ocupată.

Restricții și precizări

• 1 ≤ n ≤ 1000
• 1 ≤ m < n * n
• 1 ≤ t ≤ 50000
• Nu vor exista două piese pe aceeași poziție;
• Caracterele care precizează piesele de pe tablă pot fi:
  • p – pion;
  • r – rege;
  • q – regină;
  • n – nebun;
  • t – tură;
  • c – cal;
• Piesele de pe tablă atacă astfel:
  • regele atacă oricare dintre cele 8 căsuțe vecine pe linie, coloană sau diagonale, situate pe tablă;
  • pionul atacă oricare dintre cele 4 căsuțe vecine pe diagonale, situate pe tablă;
  • calul atacă oricare dintre 8 căsuțe, situate pe tablă, în care poate ajunge sărind în L;
  • regina atacă orice căsuță de pe tablă aflată pe aceeași linie, coloană sau diagonală cu ea, dar până la întâlnirea altei piese;
  • nebunul atacă orice căsuță de pe tablă aflată pe aceeași diagonală cu el, dar până la întâlnirea altei piese;
  • tura atacă orice căsuță de pe tablă aflată pe aceeași linie sau coloană cu ea, dar până la întâlnirea altei piese;

Exemplul 1

piesesah.in

10 6 10
p 1 1
r 8 9
q 3 2
n 6 7
t 2 9
c 9 3
1 1
5 5
2 3
5 2
9 6
8 9
10 10
9 2
2 2
7 2

piesesah.out

2
0
1
1
0
2
0
1
1
1

Explicație

Tabla de șah arată astfel:

2 1 0 1 0 0 0 0 1 0 
1 1 1 1 1 1 1 1 2 1 
1 2 1 1 1 1 1 1 1 1 
1 1 1 0 1 0 0 0 1 0 
0 1 0 1 0 1 0 1 1 0 
0 1 0 0 1 0 2 0 1 0 
0 1 0 1 0 1 0 1 1 1 
1 1 0 0 1 0 1 1 2 1 
0 1 2 1 0 0 0 1 1 1 
1 1 1 0 1 0 0 0 1 0

Exemplul 2

piesesah.in

7 4 5
q 5 5
p 3 3
c 5 2
r 7 7
4 4
5 1
1 1
7 3
3 3

piesesah.out

1
0
0
1
2

Explicație

Tabla de șah arată astfel:

0 0 0 0 1 0 0 
0 1 0 1 1 0 0 
1 0 2 0 1 0 1 
0 1 0 1 1 1 0 
0 2 1 1 2 1 1 
0 0 0 1 1 1 1 
1 0 1 0 1 1 2