pandora

Anul $2154$, undeva pe luxurianta planetă Pandora. Aici coloniștii RDA (Resources Development Administration) doresc să-și stabilească o bază stelară pentru a exploata rezervele naturale de unobtainium, un minereu rar și prețios aflat din belșug pe munții plutitori (Hallelujah Mountains), munți ce plutesc lent purtați de curenții magnetici asemănător aisbergurilor în mare, pe suprafața planetei formată din gaz lichid.

Pentru prospectarea și exploatarea zăcămintelor de minereu este necesară cartografierea suprafeței planetei și întocmirea unei hărți digitizate reprezentate sub forma unui tablou bidimensional. Astfel, regiunea de interes geologic este împărţită în $N \cdot N$ pătrate teritoriale identice (zone), fiecare zonă fiind identificată prin tripletul $(x, y, c)$, unde $(x, y)$ reprezintă coordonatele zonei teritoriale ($x$ - linia, $y$ - coloana), iar $c$ cota (înălțimea). Între zonele ocupate de munții există vaste zone de gaz lichid, zone care au cota $0$.

Pentru recoltarea și transportul unobtainiumului către baza stelară coloniștii RDA folosesc spice-harvesters, nave speciale cu aterizarea pe verticală.

Aterizarea pe munții plutitori reprezintă o adevărată provocare pentru piloții RDA. Pentru a putea ateriza, piloții trebuie să identifice un sector plat (platformă de aterizare), platformă care să respecte designul trenului de aterizare al navelor (vezi figura alăturată). Platforma are forma unui pătrat de latură $k$ ce este format din $k \cdot k$ zone teritoriale, astfel $k \cdot k - 4$ zone au aceeași cotă, iar cele $4$ colțuri ale pătratului au cota strict mai mică decât restul zonelor pătratului.

Cerinţă

Cunoscând descrierea a $M$ zone teritoriale ce alcătuiesc munții plutitori să se determine coordonatele colțului stânga-sus al platformelor de aterizare pentru munții plutitori care permit aterizarea.

Date de intrare

Fişierul de intrare pandora.in conţine pe prima linie trei numerele naturale $N$, $k$ și $M$, separate prin câte un spațiu, cu semnificația din enunț. Pe următoarele $M$ linii se află descrierea celor $M$ zone ce alcătuiesc munții plutitori, zone date sub forma unui triplet de numere naturale nenule $x$, $y$, $c$, numerele fiind despărțite prin câte un spațiu.

Date de ieșire

În fişierul de ieşire pandora.out se vor afla scrise, câte o pereche pe linie, coordonatele $x$, $y$ despărțite prin spațiu, ce reprezintă colțul stânga-sus al platformelor de aterizare pentru fiecare munte plutitor ce permite aterizarea. Dacă nu există platforme de aterizare se va afișa $0$.

Restricții și precizări

• $2 \leq N \leq 1 \ 000$
• $2 \leq M \leq 200 \ 000$
• $3 \leq k < 400$
• $1 \leq x, y \leq N$
• $0 \leq c \leq 1 \ 000$
• Prin munte plutitor înțelegem totalitatea zonelor cu cotă nenulă ce sunt împrejmuite de gaz lichid. și sunt vecine pe una din cele $4$ direcții: nord, est, sud, vest. Zona muntoasă este compactă, adică nu conţine în interior zone cu $c = 0$. Munții sunt despărțiți prin zone de gaz. Harta digitală se consideră mărginită de gaz atmosferic.
• Platformele de aterizare au cote nenule
• Dacă un munte are mai multe platforme de aterizare se va determina cea cu coordonată $x$ mai mică, iar la coordonate $x$ egale, cea cu coordonata $y$ mai mică.
• Pentru $10\%$ dintre teste $k < 10$. Pentru alte $20\%$ dintre teste $N \leq 500$

Exemplu

pandora.in

9 3 43
1 2 1
1 3 2
1 4 1
2 1 4
2 2 2
2 3 2
2 4 2
3 1 3
3 2 1
3 3 2
3 4 1
1 6 2
1 7 3
1 8 1
2 6 3
2 7 3
2 8 3
2 9 1
3 6 1
3 7 3
3 8 2
5 2 1
5 3 4
5 4 3
6 2 4
6 3 4
6 4 4
6 5 4
7 2 2
7 3 4
7 4 3
7 5 3
8 2 2
8 3 2
6 7 5
6 8 2
6 9 5
7 7 2
7 8 2
7 9 2
8 7 1
8 8 2
8 9 1

pandora.out

1 2
5 2
1 6

Explicație

Atenție, platforma din dreapta-jos nu este corectă, deoarece sunt valori din colțuri (valorile de $5$) care sunt mai mari decât valorile din platformă.