Malog Vedrana oteli su izvanzemaljci i zarobili ga u labirint. Labirint možemo zamisliti kao tablicu s \(N\) redaka i \(M\) stupaca. Tuđinci su Vedrana spustili na gornje lijevo polje s oznakom \(( 1, 1 )\) te mu dozvolili kretanje po labirintu u dva smjera: dolje i desno.

Labirint je poseban po tome što se na svakom polju \((x,y)\) nalazi \(P[x][y]\) kilograma mistične tvari. Ta tvar djeluje na čovjeka i oduzima mu energiju.

Svaki put kada Vedran stupi na neko polje \((x,y)\), na njega djeluje sva mistična tvar koja se nalazi u poljima do kojih je moguće doći u \(K\) ili manje koraka od polja \((x,y)\) krećući se u osam smjerova: gore-lijevo, gore, gore-desno, lijevo, desno, dolje-lijevo, dolje, dolje-desno. Jedan kilogram mistične tvari Vedranu oduzme jednu jedinicu energije.

Npr. ako Vedran stane na polje \(( 2, 3 )\) i ako je \(K=1\), tada će na njega djelovati tvar iz polja koja su na slici osjenčana.

Vedran je u velikoj panici, želi pobjeći i raditi JHIO zadatke i moli tebe da mu pronađeš i ispišeš put koji vodi od polja \(( 1, 1 )\) do nekog polja na desnom rubu (zadnji stupac) ili donjem rubu (zadnji redak) tablice tako da mu mistična tvar tijekom putovanja oduzme što manje energije.

Ulazni​ podaci

U prvom retku nalaze se prirodni brojevi \(N\), \(M\) i \(K\) \(( 3 \leq N, M \leq 1000, 1 \leq K \leq min(N, M))\).

U sljedećih \(N\) redaka nalazi se po \(M\) brojeva \(P[i][j]\) \(( 0 \leq P[i][j] \leq 1\) \(000\) \(000\) \(000 )\), broj kilograma mistične tvari na polju \((i,j)\) u tablici.

Izlazni podaci

Ako se put sastoji od \(A\) polja, u prvom retku ispiši broj \(A\) i zatim u \(A\) redaka ispiši oznake polja (redak i stupac) kroz koja će Vedran prolaziti na putu koji si mu odredio.

Bodovanje

Ako Vedranu tijekom putovanja mistična tvar oduzme \(X\) jedinica energije, dobit ćeš \(\frac{T}{log(X-Y-10)}\) bodova gdje je \(T\) broj bodova na tom test podatku i \(Y\) najmanji broj jedinica energije koju Vedran može izgubiti na putu do ruba.

U test podacima vrijednima \(10\) bodova vrijedit će: \(K=0,\) \(3 \leq N,\) \(M \leq 50\) i na svakom polju u tablici nalazit će se jedan kilogram mistične tvari.

U test podacima vrijednima dodatnih \(10\) bodova vrijedit će: \(K=0,\) \(3 \leq N,\) \(M \leq 50\) i na svakom polju u tablici nalazit će se jednak broj kilograma mistične tvari.

U test podacima vrijednima dodatnih \(30\) bodova vrijedit će: \(3 \leq N, M \leq 50\).

U test podacima vrijednima dodatnih \(30\) bodova vrijedit će: \(3 \leq N, M \leq 300\).

Primjeri test​ podataka

Ulaz

5 5 1
5 9 0 3 1000
5 4 7 8 6
6 4 5 6 8
2 1 3 0 5
1000 4 1 4 6

Izlaz

7
1 1
2 1
3 1
3 2
3 3
4 3
5 3

Objašnjenje

Na polju \((1,1)\) Vedran je izgubio \(23\) jedinice energije, na \((2,1)\) \(33\) jedinice, na \((3,1)\) \(22\), na \((3,2)\) \(37\), na \((3,3)\) \(38\), na \((4,3)\) \(28\) i na \((5,3)\) \(13\) jedinica energije. Na ovom putu je izgubio \(194\) jedinica energije što je najmanje što je mogao izgubiti na putu prema rubu. S ovim putem bi dobili sve bodove za taj test podatak.

Ulaz

3 3 0
1 2 8
4 1 5
1 1 1

Izlaz

3
1 1
2 1
3 1

Objašnjenje

Za dani ispis, dobio bi \(0.96*T\), gdje je \(T\) broj bodova za taj test primjer jer na tom putu mistična tvar Vedranu oduzme \(6\) jedinica energije. Najbolje bi bilo da je Vedran išao \((1,1)\rightarrow(1,2)\rightarrow(2,2)\rightarrow(3,2)\). U tom slučaju mistična tvar bi Vedranu oduzela \(5\) jedinica energije.

Ulaz

4 4 0
2 2 2 2
2 2 2 2
2 2 2 2
2 2 2 2

Izlaz

4
1 1
2 1
3 1
4 1