==Include(page="template/taskheader" task_id="pseudobil")==

Suprafaţa plană a unei mese de pseudo-biliard este formată din $n x n$ celule pătratice cu lungimea laturii egală cu $1$ (o unitate), lipite, dispuse pe $n$ linii numerotate de la $1$ la $n$ şi $n$ coloane, numerotate de la $1$ la $n$. Pe masă se aşează $K$ bile, fiecare bilă găsindu-se în centrul unei anumite celule a mesei. Un jucător doreşte să plaseze pe suprafaţa mesei un cadru pătratic având lungimea diagonalei egală cu $D$ unităţi.

Suprafaţa plană a unei mese de pseudo-biliard este formată din $n x n$ celule pătratice cu lungimea laturii egală cu $1$ (o unitate),  lipite, dispuse pe $n$ linii numerotate de la $1$ la $n$ şi $n$ coloane, numerotate de la $1$ la $n$. Pe masă se aşează $K$ bile, fiecare bilă găsindu-se în centrul unei anumite celule a mesei. Un jucător doreşte să plaseze pe suprafaţa mesei un cadru pătratic având lungimea diagonalei egală cu $D$ unităţi.

El trebuie să răspundă la $m$ întrebări de forma: $x y$. Fiecare întrebare are semnificaţia: câte bile se găsesc în interiorul sau pe laturile cadrului?

El trebuie să răspundă la $m$ întrebări de forma: $x y$. Fiecare întrebare are semnificaţia: câte bile se găsesc în interiorul sau pe laturile cadrului ?

Cadrul se plasează astfel încât fiecare colţ să fie poziţionat în centrul unei celule, colţurile opuse să se găsească pe aceeaşi coloană, respectiv pe aceeaşi linie, iar colţul “de sus” să fie plasat în centrul celulei aflată pe linia $x$ şi coloana $y$.
h2. Cerinta

Fişierul de intrare $pseudobil.in$ conţine pe prima linie un număr natural $p$. Pentru toate testele de intrare, numărul $p$ poate avea doar valoarea $1$ sau valoarea $2$.
Pe linia a doua se găsesc numerele naturale $n$, $K$ şi $D$ separate prin câte un spaţiu.

Pe fiecare dintre următoarele $K$ linii, se găsesc câte două numere $a$ şi $b$ $(a, b ≤ n)$ reprezentând linia şi coloana celulei în centrul căreia va fi aşezată o bilă.

Pe fiecare dintre următoarele $K$ linii, se găsesc câte două numere $a$ şi $b$ ($a$, $b$ ≤ $n$) reprezentând linia şi coloana celulei în centrul căreia va fi aşezată o bilă.

Pe linia $K + 3$ se găseşte un număr natural $m$.
Următoarele $m$ linii conţin câte două numere naturale $x$ şi $y$, reprezentând linia şi coloana celulei în centrul căreia se va plasa colţul „de sus” al cadrului.

h2. Restrictii si precizari
* $3 ≤ n ≤ 1.500$

* $1 ≤ K ≤ 55.000$

* $1 ≤ K &ke; 55.000$

* $2 ≤ D ≤ n - 1$, $D$ numar par
* $1 ≤ m ≤ 100.000$
* Poziţiile cadrului sunt distince.
* Se garantează pentru $x$ şi $y$ valori pentru care cadrul este plasat în interiorul suprafeţei mesei de pseudo-biliard.

* Pentru rezolvarea corectă a primei cerinţe se acordă $20$ de puncte, iar pentru cerinţa a doua se acordă $80$ de puncte.

* Pentru rezolvarea corectă a primei cerinţe se acordă 20 de puncte, iar pentru cerinţa a doua se acordă 80 de puncte.

* Pentru primele $35%$ dintre testele care verifică cerinţa $2$,  $m ≤ 1000$  şi $n ≤ 500$

* Pentru primele $75%$ din testele care verifică cerinţa $2$, $m ≤ 10.000$ şi $n ≤ 1.000$

* Pentru primele $75%$ din testele care verifică cerinţa 2, $m ≤ 10.000$ şi $n ≤ 1.000$

h2. Exemplu

Numărul de celule aflate în întregime în interiorul cadrului este n1 = 5 |
| 2
6 5 4

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

| 3
2
| p = 2, n = 6,  K = 5,  D = 4.