Šeštadieninė informatikos olimpiadininkų mokykla

Kambaryje yra robotas. Jis moka judėti tik keturiomis kryptimis: į šiaurę, į rytus, į pietus ir į vakarus. Roboto ėjimus galima programuoti simbolių N, E, S ir W seka. Pavyzdžiui, seka NNESSW priverstų robotą du kartus pajudėti į šiaurę, kartą į rytus, dukart į pietus ir kartą į vakarus - robotas atsidurtų toje vietoje, iš kurios pradėjo judėti.

Tačiau paprastiems žmonėms nėra paprasta programuoti robotą. Parašykite programą, kuri pagal duotą kambario planą ir pradinę roboto poziciją parašytų programą, kurią vykdydamas robotas apeitų visą kambario plotą.

Pradiniai duomenys

Pirmoje pradinių duomenų faile kambario planas pateikiamas simboliais. Pirmoje eilutėje įrašytas žemėlapio eilučių skaičius N ir stulpelių skaičius M (skaičiai neviršija 20). Tolesnėse N eilučių pateikiamas kambario žemėlapis. Tuščia kambario vieta žymima simboliu . (tašku), siena - simboliu #, o robotas kambaryje - raide r.

Kambario teritorija yra visada jungi ir uždara. Vienu ėjimu robotas pereina į gretimu simboliu žymimą plotą.

Rezultatai

Rezultatą turi sudaryti simbolių N, E, S ir W seka. Sekos ilgis (ėjimų skaičius) neturi viršyti 1000. Jūsų programa gali pateikti bet kurią tinkamą seką.

Pavyzdžiai

5 5
#####
#...#
#.#.#
#r..#
#####

NNEESSW

8 4
####
#.##
#..#
##.#
#..#
#.##
#.r#
####

WNNENNWN