Dağsiçanını xilas et

Bir dəfə Losyaşanın evciyinin qapısını bir neçə dağsiçanı döydü. Onlar hamısı astaca burunlarını çəkir və ağlamaqdan qızarmış nəmli gözlərini silirdilər. “Nə olub?”- deyə Losyaşa soruşdu və cavab olaraq dəhşətli məlumat eşitdi: iki dağsiçanı Pinin öz supersərt kompasını soyutması üçün tikdiyi ventilyasiya sistemində ilişib qalmışdılar.

Losyaşa dağsiçanlarının öz dostlarını xilas etməsinə kömək etməyi qərar aldı. Problem onda idi ki, heyvanlara kömək etməyin yeganə üsulu-onlara radio ilə komandaların ötürülməsi idi. Losyaşaya dağ siçanların xilası proqramını yazmaqda kömək edin.

Ventilyasiyanın labirinti daxili boşluqları müstəvi düzbucaqlı lövhə ilə kəsilmiş şəkildədir. Labirintdə cəmi bir çıxış var. Dağsiçanları o qədər də ağıllı və fərasətli deyildirlər və labirintdən özləri çıxa bilmirlər. Lakin onlar komandalar toplusunu icra edə bilirlər. Komandalar hər iki dağsiçanına eyni vaxtda verilir. Dağsiçanları eyni sürətlə hərəkət edirlər. Komandalar aşağıdakı tiplərdə olur:

• Sağa sürün - R

• Sola sürün - L

• İrəli sürün - U

• Geri sürün - D

Sadəlik üçün hesab edəcəyik ki, labirint xanalardan ibarətdir. Hər xana ya keçid yolu, ya sədd, ya da çıxış ola bilər. Dağsiçanları eyni vaxtda eyni bir xanada ola bilərlər. Dağsiçanları ventilyasiyanın səddindən keçə bilməzlər. Bundan əlavə, onlar elə keyləşiblər ki, çaşdıqlarından labirintdən yalnız birlikdə çıxa bilərlər. Əgər çıxış xanasına yalnız bir dağsiçanı gəlib çatıbsa, onda o, labirintdən çıxa bilmir və komandaları icra etməyə davam edir.

Giriş verilənləri

Birinci sətirdə labirintin uyğun olaraq şaquli və üfiqi ölçüləri olan H və W kimi iki tam ədəd yazılır. Sonra hər birində W simvol olan H sayda sətir gəlir. Simvolların hər biri aşağıdakılar biri kimi ola bilər: *-çıxış, 1-keçiddə olan birinci dağsiçanı, **2-**keçiddə olan 2-ci dağsiçanı, .-aşıq zolaq, yol, # -uçurum. H, W <= 100.

Çıxış verilənləri

Birinci sətirdə proqramın uzunluğunu verin. İkinci sətirdə dağsiçanları üçün proqramı verin. Cavab yoxdursa, -1 yazın.

Nümunələr