Pēteris ir izdomājis jaunu datorspēli, kas notiek uz $N \times N$ liela rūtiņu laukuma un kurā darbojas viens vai vairāki tēli. Katrs tēls atrodas kādā no laukuma rūtiņām. Vienā laukuma rūtiņā var atrasties vairāki tēli. Spēlētājam ir atklātas(redzamas) tikai tās rūtiņas, kuras atrodas netālu no kāda tēla, bet pārējās ir aizklātas(slēptas). Precīzāk - dotam skaitlim $d$ spēlētājam ir redzamas tikai laukuma rūtiņas ar koordinātām $[t_{x_i}, t_{y_i}]$, kurās atrodas tēli, un visas rūtiņas, kuru koordinātām $[x, y]$ vienlaikus ir spēkā sakarības $|x-t_{x_i}| \leq d$ un $|y-t_{y_i}| \leq d$.

1. attēlā parādīts spēles laukuma piemērs, kur $N=8$, $d=1$ un tēli atrodas rūtiņās ar koordinātām [$2; 0$], [$4; 2$] un [$5; 6$]. Attēlā šīs rūtiņas atzīmētas ar cipariem.

Šajā situācijā atklātas ir $23$ no $64$ laukuma rūtiņām.

Spēles gaitā tēli var pārvietoties uz blakus rūtiņām (kopīga mala) un tad mainās tas, kuras rūtiņas ir vai nav atklātas. Piemēram, ja $2.$ tēls paiet vienu soli rindas indeksa pieaugšanas virzienā, tad atklāto rūtiņu skaits ir $24$, bet, ja divus, tad - $22$.

Uzrakstiet programmu, kas dotam tēlu izvietojumam un veiktajiem gājieniem nosaka katrā brīdī atklāto rūtiņu skaitu!

evaddatu pirmajā rindā dotas četru veselu nenegatīvu skaitļu $N$ (laukuma malas garums, $1 \leq N \leq 2000$), $d$ (ap tēliem atklāto rūtiņu attālums, $0 \leq d \leq 30$), $T$ (tēlu skaits, $1 \leq T \leq 10^5$) un $G$ (tēlu izdarīto gājienu skaits, $0 \leq G \leq 2 \times 10^5$) vērtības.

Nākamajās $T$ ievaddatu rindās katrā dotas viena tēla atrašanās vietas koordinātas - kolonnas numurs $k$ ($0 \leq k < N$) un rindas numurs $r$ ($0 \leq r < N$). Katram $i$ ($1 \leq i \leq T$) $i$-tā tēla atrašanās vietas koordinātas ir dotas ievaddatu $i+1$-ajā rindā.

Nākamajās $G$ ievaddatu rindās katrā dots viena tēla viena gājiena apraksts - tēla numurs $t$ ($1 \leq t \leq T$) un $v$ (pārvietošanās virzieni, $1 \leq v \leq 4$). Virziena $v$ vērtība $1$ nozīmē, ka tēla atrašanās vietas rindas koordinātas vērtība palielinās par $1$, vērtība $2$ - ka kolonnas koordinātas vērtība palielinās par $1$, vērtība $3$ - ka rindas koordinātas vērtība samazinās par $1$, bet vērtība $4$ - ka kolonnas koordinātas vērtība samazinās par $1$. Starp katriem diviem blakus skaitļiem ievaddatos ir tukšumzīme.

zvaddatos jābūt $G+1$ rindai, kur katrā rindā ir naturāla skaitļa vērtība. Pirmajā rindā jābūt atklāto rūtiņu skaitam laukumā pirms tēli ir sākuši izdarīt gājienus. Katram $i$ ($1 \leq i \leq G$) izvaddatu $i+1$-ajā rindā jābūt atklāto rūtiņu skaitam pēc pirmo $i$ ievaddatos doto gājienu izdarīšanas.