Popularna TV emisija Nindža ratnici je kako bi podigla gledanost uvela novu igru u šou: Lavirint. U toj igri takmičari treba da što pre nađu izlaz iz lavirinta. Lavirint je pravougaonog oblika, i izdeljen u mrežu od N x M jednakih soba (N redova po M soba). Svaka soba je povezana vratima sa susednim sobama. Dakle, sobe u sredini lavirinta su povezane sa četiri susedne sobe, sobe na ivicama sa tri, a one u ćošku sa dve susedne sobe. Na sredini svake sobe se nalazi sto na kome je jedan ili više kimono pojaseva. Takmičari kreću od ulaza u lavirint koji ih uvodi u gornju levu sobu lavirinta, a izlaz iz lavirinta je uvek u krajnje desnoj donjoj sobi lavirinta. Pobednik je takmičar koji u najkraćem vremenu stigne do cilja, a ukoliko više takmičara stigne u isto vreme pobednik je onaj koji usput sakupi najviše kimono pojaseva.

Potrebno je pronaći optimalnu putanju kojom takmičar treba da se kreće kako bi pobedio u ovoj igri i sebi osigurao laskavu titulu nindža ratnika.

Napomena: Smatrati da je vreme koje je takmičaru potrebno da prođe kroz sobu i pokupi sve pojaseve u njoj konstantno, bez obzira na koja vrata takmičar ulazi, i na koja izlazi. Takođe smatra se da su takmičari sposobni da ponesu proizvoljan broj kimono pojaseva sa sobom.

U prvom redu su zadata dva prirodna broja N i M.

U narednih N redova je u svakom zadato po M prirodnih brojeva koji predstavljaju broj kimono pojaseva u svakoj od soba u lavirinu.

Potrebno je ispisati instrukcije kako takmičar treba da se kreće od početne sobe do sobe u kojoj je izlaz iz lavirinta. Na izlazu treba ispisati po jednu od komandi: Gore, Dole, Levo, Desno u svakom redu.

Ukoliko postoji više optimalnih putanja potrebno je pronaći i ispisati samo jednu od njih.

N, M < 1 000

Najkraća putanja na kojoj može da se sakupi 22 kimono pojasa je označena na primeru:

1 1 3 1 2
2 5 3 1 1
6 1 2 4 2
1 1 1 3 2