Slavko je surfajući na internetu naišao na reklamu koja prikazuje sustav spremnika i cijevi (primjer takvog sustava ilustriran je na slici ispod) s porukom: “Ako se u spremnik \(1\) počinje dovoditi voda, odredite redoslijed kojim će se spremnici napuniti”.

Sustav se sastoji od \(K\) spremnika označenih brojevima od \(1\) do \(K\) i možemo ga opisati matricom znakova dimenzije \(N\) redaka i \(M\) stupaca. Spremnici imaju oblik pravokutnika, a obrisi spremnika i cijevi prikazuju se sljedećim znakovima:

• - ako se radi o vodoravnom dijelu obrisa,
• | ako se radi o okomitom dijelu obrisa i
• + ako se radi o mjestu na kojem se vodoravni i okomiti dijelovi obrisa spajaju. Iznimka je mjesto spajanja spremnika i cijevi, kod kojeg dominira obris spremnika (vidi primjere test podataka).

Na proizvoljnom mjestu unutar svakog spremnika nalazi se i niz znamenki koje predstavljaju oznaku spremnika, a sva ostala polja u matrici jednaka su . (točki).

Svi spremnici osim onog s oznakom \(1\) imaju točno jednu dovodnu cijev koja u spremnik ulazi na njegovoj gornjoj površini. Spremnik s oznakom \(1\) nema dovodnih cijevi.

Spremnici mogu imati više (moguće i nula) odvodnih cijevi koje iz spremnika izlaze s bočne strane. Mjesta iz kojih odvodne cijevi nekog spremnika izlaze iz njega nalazit će se u međusobno različitim retcima u matrici.

Cijevi izravno povezuju dva spremnika što znači da nije moguće razdvajanje cijevi ili spajanje više cijevi u jednu, a ni jedne dvije cijevi se neće međusobno sjeći. Cijevi na svom putu od izvornog prema odredišnom spremniku uvijek se spuštaju u sljedeći redak ili ostaju u istom retku, tj. nikad se ne vraćaju u prethodni redak, tako da voda može slobodno teći iz jednog spremnika u drugi.

Voda u spremnik ulazi sve dok se ne napuni. Ako se razina vode digne do razine kod koje izlazi odvodna cijev, voda će teći kroz tu cijev sve dok se ne napuni spremnik do kojeg ta cijev vodi.

Pomozite Slavku i odredite redoslijed kojim će se spremnici napuniti.

Napomena: Test primjeri će biti takvi da će svaki znak + biti okružen s točno jednim znakom - s lijeve ili desne strane i s točnim jednim znakom | s gornje ili donje strane, a svi ostali susjedni znakovi u smjerovima gore, dolje, lijevo i desno bit će jednaki . (točki).

Ulazni​ podaci

U prvom retku nalaze se dva prirodna broja \(N\) i \(M\) \(( 1 \leq N, M \leq 1000 )\), dimenzije matrice. U sljedećih \(N\) redaka nalazi se po \(M\) znakova koji opisuju izgled sustava.

Izlazni podaci

Potrebno je ispisati \(K\) redaka. U \(i\)-tom retku ispišite oznaku spremnika koji će se napuniti \(i\)-ti po redu. Rješenje će uvijek postojati i bit će jedinstveno.

Bodovanje

U test podacima ukupno vrijednima \(70 \%\) bodova vrijedit će \(N, M \leq 100\).

Primjeri test​ podataka

Ulaz

12 13
..+--+.......
+-|..|.......
|.|.1|--+....
|.+--+..|....
|......+----+
+---+..|..2.|
....|..+----+
.+--+........
.|...........
+---+........
|.3.|........
+---+........

Izlaz

2
3
1

Objašnjenje

U spremnik \(1\) počinje se dovoditi voda.

Razina vode u spremniku \(1\) raste i u jednom trenutku doseže razinu na kojoj se nalazi odvodna cijev koja vodi do spremnika \(2\). Voda kroz cijev teče tako dugo dok se ne napuni spremnik \(2\).

Nakon toga, razina vode u spremniku \(1\) nastavlja rasti dok ne dođe do razine na kojoj se nalazi odvodna cijev koja vodi do spremnika \(3\), koji se sljedeći napuni.

Konačno, razina vode u spremniku \(1\) opet nastavlja rasti i spremnik se napuni do vrha.

Ulaz

8 10
..........
.......+-+
...+---|1|
...|...+-+
...|......
..+-+.....
..|2|.....
..+-+.....

Izlaz

2
1