Səhv robot

İkiölçülü labirintdə hərəkət edərək çıxışı tapması üçün bir robotu proqramlaşdırmalısınız.

Labirint $n$ sətir və $m$ sütundan ibarət bir şəbəkə şəklində təqdim olunur. Şəbəkənin bəzi hüceyrələrində robotun keçə bilməyəcəyi maneələr var; digərləri boşdur və robot onlar vasitəsilə sərbəst hərəkət edə bilər. Yalnız bir boş hüceyrə çıxış kimi işarələnib və robot həmin hüceyrəyə çatdıqda dərhal labirintdən çıxacaq.

Robotu proqramlaşdırmaq üçün ona bir komanda sətri göndərə bilərsiniz. Komanda sətri müvafiq olaraq sola, yuxarı, sağa, aşağı istiqamətlərə uyğun gələn L, U, R, D simvollarından ibarətdir. Robot komandaları ardıcıllıqla icra edərək göstərilən istiqamətdə qonşu hüceyrəyə hərəkət edir. Əgər robot maneə və ya şəbəkənin kənarına çatsa, o əmri nəzərə almayacaq, lakin növbəti əmrlərə davam edəcək. Robot çıxış hüceyrəsinə çatdıqdan sonra bütün əmrləri nəzərə almayacaq.

Dostunuz sizə bir komanda sətri göndərib, amma bu komanda sətri robotu çıxışa aparmaya bilər. Sətri elə düzəltmək lazımdır ki, robot çıxış hüceyrəsinə çatsın. Bir saniyədə istənilən simvolu silə və ya istənilən mövqeyə yeni simvol əlavə edə bilərsiniz. Lazımi minimal düzəliş vaxtını tapın ki, robot çıxışa çatsın.

Robotun çıxışa çatması üçün lazım olan vaxt önəmli deyil; sadəcə komandaların düzəldilmə müddətini minimallaşdırmaq lazımdır.

Giriş məlumatları

Birinci sətirdə iki tam ədəd $n$ və $m$ (1 \le n, m \le 50) verilir.

Növbəti $n$ sətirin hər biri şəbəkəni və $m$ simvolu təsvir edir. Boş hüceyrələr `.' simvolu ilə, robotun başlanğıc mövqeyi R, maneələr #, çıxış isə E ilə göstərilib.

Növbəti və sonuncu sətr dostunuzun komanda sətridir və $1$-dən $50$-dək simvoldan ibarət ola bilər.

Labirintdə dəqiq bir R və bir E olduğu və həmişə R-dən E-yə bir yol olduğu təmin edilir.

Çıxış məlumatları

Proqramı düzəltmək üçün lazım olan minimum vaxtı göstərən bir tam ədəd çıxarın.