Kirándulás Manhattanben

Manhattan New York egy látványosságokkal és veszélyekkel teli része. A város(rész) tervezői annak idején úgy döntöttek, hogy a területet egymással párhuzamos utcákra és ezekre merőleges sugárutakra bontják, így Manhattan nagyjából úgy néz ki, mint egy sakktábla. Ez már önmagában is elég nagy látványosság, így nekünk, mint turistáknak a célunk az, hogy bejárjuk a városrészt miközben minél több érdekességet nézünk meg. Sajnos azonban a kor eljárt felettünk is, így alaposan meg kell gondolnunk, hogy merre sétálunk. Rozoga ízületeinknek köszönhetően nem tudunk visszafordulni, így a kiindulási pontból ("bal felső csücsök") csakis jobbra és lefelé közlekedhetünk. A sétálgatás során az alábbi ismeretek, szabályok állnak rendelkezésünkre:

• Manhattan térképe egy téglalap mely cellákra van osztva. Mi a bal felső, (0,0) indexű cellából indulunk.
• Mindegyik cellának van egy egész szám értéke. Minél nagyobb ez az érték annál érdekesebb az adott helyen lévő látványosság.
• A mozgás során mindig egy cellányit haladhatunk, mely történhet hozzánk képest jobbra (az x koordináta nő 1-el), vagy lefelé (az y koordináta nő 1-el).
• A célunk eljutni a jobb alsó cellába úgy, hogy az össz hasznunk a lehető legnagyobb legyen.

Mivel fiatalabb korunkban roppant mód érdekelt minket az algoritmusok elemzése, így rájöttünk, hogy az optimális haszon megkapása egyszerű:

• A kezdeti cella értéke önmaga.
• A 0. sor többi elemének értéke a tőle balra lévő érték és a cella értékének összege.
• A 0. oszlop többi elemének értéke a felette lévő cella értéke és a cella értékének összege.
• Minden egyéb cella értéke a max(1-el balra lévő érték,1-el feljebb lévő érték)+cella érték képlettel számolható ki.

A feladatunk azonban ennek elkészítésénél egy fokkal nehezebb: el kell mesélnünk a kisunokánknak, hogy merre mentünk és miket láttunk, így a feladat célja az, hogy meghatározzuk, hogy mely cellákon szükséges végigmennünk ahhoz, hogy megkapjuk a fenti szabályrendszer alapján kiszámolt jobb alsó cellaértéket (azaz kirajzoljuk az útvonalat).

Input

Az input az alábbi három egységből áll:

• Az első sor egy n pozitív egész, mely a táblázat sorainak számát adja meg.
• A második sor egy m pozitív egész, mely a táblázat oszlopainak számát adja meg.
• A következő n darab sor mindegyike m darab szóközzel elválasztott egészet tartalmaz, melyek az egyes cellákban lévő látnivalók "szépségét" adják meg.

Output

A kimenet egyetlen sor, mely azt az útvonalat írja le a kiindulási 0,0 cellától a jobb alsó n-1,m-1 celláig, melyet a fenti szabályrendszer alapján követnünk kell, hogy a jobb alsó cellában szereplő értéket elérjük. A kiírás során az egyes cellák sor és oszlop indexeit szükséges megjeleníteni oly módon, hogy az indexeket egyetlen vessző karakterrel szeparáljuk, míg az egyes cellák értékei között egyetlen szóköz karakternek kell állnia. Például n=6, m=5 esetén egy lehetséges útvonal leírása: 0,0 0,1 1,1 2,1 3,1 4,1 4,2 4,3 4,4 5,4

Megkötések

Példa