Hide

Problem K
Skidor

Johan gillar att åka skidor. Då menar vi inte att åka slalom, vilket Johan nämligen är väldigt rädd för. Långfärdsskidor däremot, det är hans grej. När man åker långfärdsskidor måste man dock ha stora plana ytor.

Johan har undersökt ett stort rektangulärt område ute i skogen, som har ganska ojämn mark. Här vill Johan välja ut en viss kvadrat att åka runt på, som är tillräckligt stor för att göra skidåkningen intressant. Kvadraten ska ha exakt storlek $L \times L$, och ha sidor parallella med områdets sidor.

Nu ber han dig hitta en sådan kvadrat. För att den ska passa bra för långfärdsskidor har han två krav. Dels får det inte finnas några träd i kvadraten, och dels ska höjdskillnaden mellan den högsta och den lägsta punkten i denna kvadrat vara så liten som möjligt.

Om det finns finns flera möjliga sådana kvadrater, ska du i första hand välja den som ligger längst norrut, d.v.s har lägst radnummer. Om det fortfarande finns flera möjliga ska du i andra hand välja den som ligger längst västerut, d.v.s. har lägst kolumnnummer.

Indata

Den första raden innehåller tre heltal $R$, $C$, $L$ sådana att $1\leq R,C \leq 1000, 1 \leq L \leq min(R,C)$. $R$ är antalet rader i det stora området, $C$ antalet kolumner, och $L$ storleken på den sökta kvadraten.

Därefter följer $R$ rader, en för varje rad i området. En rad innehåller $C$ heltal, en för varje kolumn i området.

Det $c$:te talet på den $r$:te raden beskriver höjden $H_{rc}$ på den punkten i området, som är sådan att sådana att $-1 \leq H_{rc} \leq 10^9$. Om $H_{rc} = -1$ finns det istället att det står ett träd på den platsen.

Output

Hitta $r_ l$, $c_ l$ sådana att Johans kvadrat spänner över koordinaterna $r_ l \leq r <r_ l + L$, $c_ l \leq c < c_ l + L$. $r_ l$ och $c_ l$ ska vara 0-indexerade, exemplevis är $r_ l = 0$ om den första raden (som ligger längst norrut) menas, och $c_ l = 0$ om den första kolumnen (som ligger längst västerut) menas.

Det är garanterat att det finns en lösning.

Poängsättning

Din lösning kommer att testas på en mängd testfallsgrupper. För att få poäng för en grupp så måste du klara alla testfall i gruppen.

Grupp

Poängvärde

Gränser

1

21

$0 \leq H_{rc} \leq 1$

2

36

$R,C \leq 50$

3

27

$R,C \leq 300$

4

16

$R,C \leq 1000$

Sample Input 1 Sample Output 1
3 3 2
10 3 5
2 4 3
2 8 1
0 1

Please log in to submit a solution to this problem

Log in