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

Paftenie barbarul este un renumit aventurier. A condus razboaie, a descoperit comori, a cucerit cetati si inimile domnitelor. Insa de aceasta data a fost capturat de catre dusmanii sai cei mai temuti si aruncat intr-o temnita. Temnita este de fapt un grid de dimensiune {$R*C$}. In anumite celule exista dragoni, unele sunt ocupate de pereti, iar altele sunt libere. Paftenie trebuie sa iasa din temnita mergand numai prin celule libere (o celula are maxim 4 vecini) , si asta stand cat mai departe de fiorosii dragoni ale caror flacari ii pot deteriora vestimentatia (astfel incat minima din distantele pana la cel mai apropiat dragon din fiecare din celulele traseului sau sa fie maxim).

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?
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

Ajutati-l pe barbarul Paftenie sa iasa din temnita, determinand un traseu astfel incat distanta minima pana la cel mai apropiat dragon din fiecare dintre celulele traseului sau sa fie maxima!

Cunoscând lungimea $n$ a laturilor mesei, numărul $m$ de întrebări, numărul $K$ de bile aşezate pe masă, poziţiile lor şi lungimea $D$ a diagonalei cadrului pătratic, se cere:
a) Numărul de celule care se vor găsi în întregime în interiorul cadrului, dacă acesta se aşează pe suprafaţa mesei, conform descrierii de mai sus.
b) Câte un răspuns pentru fiecare dintre cele $m$ întrebări.

h2. Date de Intrare

Pe prima linie a fisierului de intrare $barbar.in$ sunt date doua numere intregi $R$ si {$C$}, reprezentand numarul liniilor, respectiv al coloanelor temnitei. Pe urmatoarele $R$ linii se afla cate $C$ caractere, neseparate prin spatii, cu urmatoarele semnificatii:
$.$ celula libera
$*$ perete
$D$ dragon
$I$ punctul de plecare al lui Paftenie
$O$ iesirea din temnita

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 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. Date de Iesire

Fisierul de iesire $barbar.out$ va contine pe prima linie un singur numar, reprezentand valoarea maxima pentru minima din distantele pana la cel mai apropiat dragon din fiecare din celulele traseului. In caz ca nu exista solutie se va afisa {$-1$}.

Dacă valoarea lui $p$ este $1$,  se va rezolva numai punctul $1$ din cerinţă. În acest caz, în fişierul de ieşire $pseudobil.out$ se va scrie un singur număr natural $n1$, reprezentând numărul de celule care se vor găsi în întregime în interiorul cadrului.
Dacă valoarea lui $p$ este $2$, se va rezolva numai punctul $2$ din cerinţă. În acest caz, fişierul de ieşire $pseudobil.out$ va conţine $m$ linii. Pe fiecare linie $i$ se va scrie câte un număr natural $n2$, reprezentând răspunsul pentru întrebarea $i$.

h2. Restrictii si precizari

* $1 ≤ R, C ≤ 1.000$
* Se garanteaza ca in temnita exista cel putin un dragon

* $3 ≤ n ≤ 1.500$
* $1 ≤ K ≤ 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 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$

h2. Exemplu

table(example). |_. pseudobil.in |_. pseudobil.out |
| 10 10
..........
.I....D...
..........
..D...D...
.*........
D*........
*...D.....
..****....
...O......
..........
| 2 |
 
h3. Explicatii
 
O solutie posibila:
$..........$
$.I{*ooo*}.D...$
$....{*o*}.....$
$..D.{*o*}.D...$
$.*..{*oo*}....$
$D*...{*ooooo*}$
${@*@}...D....{*o*}$
$..****...{*o*}$
$...O{*oooooo*}$
$..........$

table(example). |_. pseudobil.in |_. pseudobil.out |_. Explicatii |
| 1
5 2 4
3 4
5 2
1
1 3
| 5
| p = 1
n = 5,  K = 2,  D = 4
D = (3 unităţi + 2*0.5 unităţi) = 4
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.
Prima întrebare este: 1 3 .  Sunt două bile pe laturile cadrului şi una în interior, deci n2 = 3
A doua întrebare este: 2 4. O bilă se găseşte pe una dintre laturile  cadrului şi una în interior, deci n2 = 2
Atenţie! Pentru acest test se rezolvă doar cerinţa 2. |

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