Ir dots labirints, kas izskatās kā taisnstūris ar izmēriem M*N rūtiņas. Katra labirinta rūtiņa var būt gan tāda, caur kuru ir iespējams pārvietoties, gan tāda, caur kuru nav.
Vienība izsēdina desantnieku labirinta rūtiņā (M1,N1)(Šeit un turpmāk pirmais skaitlis - rindas numurs, otrais - kolonnas numurs).
Desantniekam nepieciešams nokļūt rūtiņā (M2,N2) pa īsāko iespējamo ceļu. Pārvietoties katrā solī drīkst tikai uz tādu brīvo rūtiņu, kurai ar pašreizējo ir kopīga mala.

Uzrakstiet programmu, kas atrod un izvada visus īsākos iespējamos ceļus no sākotnējās līdz beigu rūtiņai.

Ievaddatu pirmajā rindā doti labirinta izmēri - naturāli skaitļi M(rindiņu skaits) un N(kolonnu skaits), kas atdalīti ar tukšumsimbolu. Zināms, ka 0 < M,N < 101.
Ievaddatu otrajā rindā dotas desantnieka sākotnējās rūtiņas koordinātas - M1 un N1 vērtības, kas atdalītas ar tukšumsimbolu.
Ievaddatu otrajā rindā dotas desantnieka beigu rūtiņas koordinātas - M2 un N2 vērtības, kas atdalītas ar tukšumsimbolu.
Ievaddatu nākošajās M rindās dots pa N simboliem - vienas labirinta rindas apraksts.
Ar simbolu # apzīmētās tās rūtiņas, caur kurām iziet nav iespējams, bet ar * tās, caur kurām pārvietošanās ir iespējama.

Izvaddatu katrā rindā jāizvada visu īsāko ceļu apraksts, izvadot pa viena ceļa aprakstam katrā rindā.
Katra ceļa apraksts ir ciparu virkne, kur cipars «0» nozīmē «soli pa kreisi», «1» - soli uz augšu, «2» - soli pa labi, «3» - soli uz leju. Ciparu skaits skaitlī ir ceļa garums.
Ceļu apraksti jāizvada augošā secībā. Izvad faila izmērs nepārsniedz 1 megabaitu, un noteikti eksistē vismaz viens ceļš no sākotnējās uz beigu rūtiņu.

Uzdevums ņemts no Baltkrievijas 2001. gada sacensībām.