Zota si Chidil s-au certat. De aceasta data, Zota, dorind sa se razbune, planuieste sa insire o serie de capcane in padurea prin care Chidil obisnuieste sa se plimbe. Astfel, folosind o formula magica, el asterne o capcana in mai multe celule ale padurii. Toate celulele care se afla la o distanta Manhattan mai mica sau egala cu _2_ de capcana sunt si ele afectatate.
In imaginea de mai jos capcana este reprezentata prin $O$ iar celelalte celule afectate sunt marcate cu $X$.

     $.......$
     $...X...$
     $..XXX..$
     $.XXOXX.$
     $..XXX..$
     $...X...$
     $.......$

$.......$
$...X...$
$..XXX..$
$.XXOXX.$
$..XXX..$
$...X...$
$.......$

Chidil isi planifica intotdeauna traseul. El porneste intotdeauna din celula cu coordonate (0, 0). Drumul lui este descris printr-o pereche ({$D$}, {$x$}) unde D apartine multimii {$N$, $E$, $S$, $V$}, iar $x$ este un numar natural nenul. Aceasta inseamna ca din pozitia in care se afla, va face $x$ pasi in directia $D$.
Desi afla de planul malefic al lui Zota, Chidil nu vrea sa isi schimbe traseul cu nici un chip. Prefera sa afle cate celule din traseul lui contin capcane sau sunt afectate de capcane, pentru a sti exact cat praf magic pentru neutralizarea celulelor sa ia la el.

h2. Date de intrare

Pe prima linie a fisierului de intrare **zc.in** se afla doua numere naturale $N$ si $M$, reprezentand numarul de capcane intinse de Zota, respectiv numarul de perechi ({$D$}, $x$) conform carora Chidil urmeaza sa se deplaseze.

Pe prima linie a fisierului de intrare $zc.in$ se afla doua numere naturale $N$ si $M$, reprezentand numarul de capcane intinse de Zota, respectiv numarul de perechi ({$D$}, $x$) conform carora Chidil urmeaza sa se deplaseze.

Liniile $2 .. N+1$ contin cate o pereche de numere ({$x$} {$y$}), ce reprezinta coordonatele capcanelor.

h2. Date de iesire

Fisierul de iesire **zc.out** va contine pe prima linie numarul de celule periculoase care trebuie neutralizate de Chidil in drumul sau.

Fisierul de iesire $zc.out$ va contine pe prima linie numarul de celule periculoase care trebuie neutralizate de Chidil in drumul sau.

h2. Restrictii si precizari

h2. Exemplu

table(example). |_. zc.in |_. zc.out |_. Explicatii |

table(example). |_. zc.in |_. zc.out |

| 2 8
5 6
12 10

E 6
N 6
V 3

| 4
| ...........####............
............X.#............
...........XXX#............
......###.XXOX#............
......#.#..XXX#............
.....X#.#...X.#............
....XX#.#######.............
...XXO#X...................
....XX#....................
.....X#....................
#######....................
#..........................
#..........................
#.......................... |

| 4 |
 
h3. Explicatii
 
$...........####............$
$............X.#............$
$...........XXX#............$
$......###.XXOX{%{color:red}#%}............$
$......#.#..XXX#............$
$.....X#.#...X.#............$
$....XX{%{color:red}#%}.#######............$
$...XXO{%{color:red}#%}X...................$
$....XX{%{color:red}#%}....................$
$.....X#....................$
$#######....................$
$#..........................$
$#..........................$
$#..........................$

==Include(page="template/taskfooter" task_id="zc")==

729