Na velikoj pravougaonoj šah tabli dimenzija R x C nalaze se protivničke i domaće figure. Figura može biti mnogo više negu u običnom šahu
a njihove životne vrednosti su označene celim brojevima Vi, tako da su protivničke figure sa pozitivnim a domaće sa negativnom
životnom vrednošću. Nula označava slučaj kada nema figure na nekom polju.
Super Dama iskače iz GligBull GT helikoptera i padobranom se spušta na teren. Može da se spusti na neko od polja velike pravougaone šah table
na kome nema druge figure ali može, ako smatra da je to povoljnije za nju da se spusti van table, ali samo uz red ili kolonu koji su tik uz tablu.
Sa mesta na koje se spustila, Super Dama mora da izabere jedno od 8 smerova kretanja (gore, gore-desno, desno, dole-desno, dole,
dole-levo, levo, gore-levo) i, za razliku od obične dame, da počisti sve fugure koje se nalaze u tom smeru čime će
preuzimanjem životnih vrednosti tih figura povećati svoju.
Vaš zadatak je da odaberete neko od polja na koje Super dama treba da se spusti i smer u kojem treba da počisti figure tako da maksimizira svoju životnu vrednost.
Ulaz:
U prvom redu standardnog ulaza nalaze se dva cela broja, R i C (1 ≤ R, C ≤ 1000) koji predstavljaju dimenzije table.
U sledećih R redova, nalaze se po C celih brojeva Vi (-109 ≤ Vi ≤ 109)
koji predstavljaju životnu vrednost figure na tom polju. Pozitivno Vi predstavlja protivničke a negativno sopstvene figure.
Izlaz:
U prvom redu standardnog izlaza treba ispisati dva broja odvojena praznim mestom, koji predstavljaju oznaku reda i kolone na koje se Super Dama treba spustiti.
U drugi red treba ispisati smer u kome superdama treba da počisti figure, kako bi do maksimuma povećala svoju životnu snagu.
Ako ima više mogućih rešenja, ispiši bilo koje. Koordinate polja moraju biti u granicama [0..1001] i za red i za kolonu.
Napomena.
Ako dama počisti neku od svojih figura, kao nadoknadu za kolateralnu štetu, njena životna snaga se smanjuje. Takodje, ako je to za nju najpovoljnija mogućnost, može i da "puca u prazno".
Primer:
Ulaz:
|
|
Izlaz:
|
4 10
1 2 3 4 5 6 7 8 9 10
0 -7 5 4 0 5 -1 0 15 1
1 1 1 1 1 1 1 20 1 1
9 -9 8 7 6 5 11 -6 8 -5
|
|
5 6
gore-desno
|
Objašnjenje.
Maksimalno povećanje životne snage Super Dame je 56. To se može ostvariti na dva načina ако dama sleti na polje (5,6) i počisti sve figure u smeru
“gore-desno” ili ako sleti na polje (0,11) i počisti sve u smeru “dole-levo”.