bloxorz

E posibil să cunoașteți jocul Bloxorz. Dacă nu cunoașteți, vă rugăm să vizionați stagiul 1 din acest videoclip pentru a înțelege mecanicile acestui joc. În problema aceasta nu există butoane, posibilitatea de a despărți jucătorul în două cuburi, sau alte lucruri care nu apar în stagiul 1 al videoclipului.

Jucătorul este un paralelipiped dreptunghic de dimensiuni $2 \times 1 \times 1$. La început, înălțimea acestuia este $2$ iar lungimea și lățimea sunt $1$. Pentru a se mișca pe hartă, jucătorul se va roti în cele 4 direcții (Nord, Sud, Est, Vest). La o rotație, înălțimea, lungimea și lățimea jucătorului se vor schimba între ele. Spre exemplu, din stadiul inițial al jucătorului se poate ajunge la înălțimea $1$, lungimea $2$ și lățimea $1$.

Cerință

Aveți la dispoziție o hartă bidimensională care conține, în unele poziții, platforme. Jucătorul are voie să meargă doar pe platforme. Verificați dacă este posibil ca jucătorul să ajungă de pe o platformă inițială pe o platformă finală, având la sfârșit înălțimea $2$ și lungimea și lățimea $1$. În cazul în care este posibil, afișați un traseu corect pe care jucătorul îl poate folosi.

Date de intrare

Pe prima linie se află numerele $N$ și $M$, reprezentând dimensiunile hărții (numărul de linii respectiv numărul de coloane).

Pe următoarele $N$ linii se află $M$ caractere, fiecare reprezentând o bucată din hartă. Caracterele pot fi:

• _ — Acest caracter reprezintă o platformă.
• # — Acest caracter reprezintă că acolo nu există nimic. Înseamnă că jucătorul nu are voie să meargă pe acolo.
• A — Acest caracter reprezintă platforma inițială.
• B — Acest caracter reprezintă platforma finală.

Date de ieșire

În cazul în care nu există niciun traseu, afișați NU.
În cazul în care există un traseu, afișați pe prima linie DA, iar pe a doua linie o înșiruire de caractere din mulțimea $\{$N$,$ S$,$ E$,$ V$\}$ reprezentând direcțiile pe care jucătorul le va parcurge la fiecare pas (N — Nord, S — Sud, E — Est, V — Vest).

Restricții și precizări

• $1 \leq N,M \leq 2\ 000$
• Jucătorul trebuie să stea integral pe platforme. Nu este permis ca o jumătate din jucător să fie pe o platformă iar cealaltă jumătate să nu fie pe o platformă.
• Problema nu cere neapărat un traseu cu număr minim de pași.
• În afara hărții nu există nicio platformă.
• Veți primi $40\%$ din punctajul unui subtask pentru afișarea corectă doar a primului mesaj (DA/NU).

Exemplu

stdin

6 10
___#######
_A____####
_________#
#_________
#####__B__
######___#

stdout

DA
EESEEES

Explicație

Exemplul este același ca cel din videoclip, precum și mutările făcute.

Soluțiile ESSEESE sau EESENVSEEESSNVNSVNESEVSSVENVNEESVNESVNESV sunt de asemenea corecte.