marmote

Marmote

== include(page="template/taskheader" task_id="marmote") ==

Poveste şi cerinţă...

Miruna a primit mostenire de la matusa Tamara o livada ce poate fi reprezentanta sub forma unei matrice cu $N$ linii si $M$ coloane. Livada se afla la baza unui munte locuit de $K$ marmote. Deoarece a venit iarna, este timpul ca marmotele sa coboare la altitudini mai mici pentru a se adaposti de frig. In fiecare zi, cate o marmota soseste in livada Mirunei si vrea sa isi construiasca o vizuina. Fiecare marmota isi alege un punct de coordonate {$X$}{$~i~$} si {$Y$}{$~i~$}. Vizuina sa va fi formata din toate pozitiile campului aflate la o distanta Manhattan mai mica sau egala cu un numar dat $L$ de pozitia ({$X$}{$~i~$}, {$Y$}{$~i~$}). In cazul in care exista cel putin o pozitie din vizuina care face deja parte dintr-o vizuina construita anterior, marmota va refuza sa se stabileasca in livada Mirunei si va pleca in lumea larga.

h2. Date de intrare

Fişierul de intrare $marmote.in$ ...

Fişierul de intrare $marmote.in$ va contine pe prima linie $4$ numere intregi $N$, $M$, $K$ si $L$ avand semnficatia din enunt. Urmatoarele $K$ linii vor contine cate doua numere intregi {$X$}{$~i~$} si {$Y$}{$~i~$}, valorile asociate marmotei cu indicele $i$.

h2. Date de ieşire

În fişierul de ieşire $marmote.out$ ...

În fişierul de ieşire $marmote.out$ veti afisa in ordine crescatoare indicii marmotelor care isi vor construi viziuna in livada Mirunei. Aceste valori vor fi afisate pe cate o linie.

h2. Restricţii

h2. Restricţii si precizari

* $... ≤ ... ≤ ...$

* $1 ≤ N ≤ 1 000$
* $1 ≤ M ≤ 1 000$
* $1 ≤ K ≤ 100 000$
* $1 ≤ L ≤ N, M$
* $1 ≤ X{~i~} ≤ N$
* $1 ≤ Y{~i~} ≤ M$
* Distanta Manhattan intre doua puncte $(X{~1~}, Y{~1~})$ si $(X{~2~}, Y{~2~})$ este egala cu $|X{~1~} - X{~2~}| + |Y{~1~} - Y{~2~}|$

h2. Exemplu
table(example). |_. marmote.in |_. marmote.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

| 10 12 6 3
  3 6
  5 9
  7 1
  9 4
  4 11
  2 10
| 1
  3

|

h3. Explicaţie
 
...
 

== include(page="template/taskfooter" task_id="marmote") ==

3568