Fireboy & Watergirl

Cerință

Fireboy și Watergirl se află într-un labirint reprezentat ca o matrice cu $N$ linii și $M$ coloane.

Cei doi se mișcă simultan, câte un pas pe rând. La fiecare pas, Fireboy și Watergirl aleg independent câte una dintre cele cinci acțiuni posibile: sus, jos, stânga, dreapta sau stai pe loc. După alegerea acțiunilor, ambele mișcări se aplică în același timp.

Scopul lor este ca Fireboy să se afle la ieșirea sa, iar Watergirl la ieșirea ei, în același moment.

Fiecare celulă a matricei este de unul dintre următoarele tipuri:

O mișcare este validă doar dacă poziția finală a jucătorului se află în interiorul matricei și nu este o celulă interzisă pentru acel jucător. Astfel, niciun jucător nu poate intra într-un perete, Fireboy nu poate intra în apă, iar Watergirl nu poate intra în foc.

Mecanismul ușilor: Un jucător poate ajunge pe celula ușii $U_k$ la sfârșitul unui pas numai dacă, după aplicarea simultană a celor două mișcări din acel pas, celălalt jucător se află pe celula butonului corespunzător $B_k$.

Cu alte cuvinte, pentru ca un jucător să fie pe $U_k$ la un anumit moment de timp, celălalt jucător trebuie să fie pe $B_k$ în același moment de timp. Celălalt jucător poate fie să ajungă pe buton chiar în acel pas, fie să fi fost deja acolo și să aleagă acțiunea să stea pe loc.

Butonul nu rămâne activ după ce jucătorul pleacă de pe el. Ușa $U_k$ poate fi folosită doar în momentele în care celălalt jucător se află pe $B_k$.

Condiția de victorie: Jocul se termină cu succes când, la sfârșitul aceluiași pas, Fireboy se află pe IB și Watergirl se află pe IG. Nu este necesar ca cei doi să ajungă la ieșiri simultan — unul poate să ajungă mai devreme și să aștepte acolo, alegând acțiunea să stea pe loc, până când celălalt îl ajunge din urmă.

Cei doi jucători pot ocupa aceeași celulă fără restricții.

Se garantează că există întotdeauna o soluție.

Date de intrare

Prima linie conține două numere întregi $N$ și $M$, dimensiunile matricei. Urmează $N$ linii, fiecare conținând $M$ valori separate prin spații, reprezentând tipul fiecărei celule.

Date de ieșire

Pe prima linie, afișați numărul $K$ de pași. Pe a doua linie, afișați un șir de $K$ caractere reprezentând mișcările lui Fireboy. Pe a treia linie, afișați un șir de $K$ caractere reprezentând mișcările lui Watergirl.

Fiecare caracter de mișcare este unul din: U (sus), D (jos), L (stânga), R (dreapta), . (stai pe loc).

Cele două șiruri de mișcări trebuie să aibă aceeași lungime $K$. La pasul $i$, se execută simultan al $i$-lea caracter din șirul lui Fireboy și al $i$-lea caracter din șirul lui Watergirl.

Orice soluție validă cu cel mult $2 \cdot 10^5$ pași este acceptată. Nu se cere numărul minim de pași.

Restricții și precizări

• $1 \leq N, M \leq 20$
• Există exact un B, un G, un IB și un IG în matrice
• Fiecare ușă $U_k$ are exact un buton corespunzător $B_k$
• Numărul de perechi ușă–buton este cel mult $4$
• Se garantează că există o soluție

Subtaskuri și punctaje

Exemplu

stdin

6 4
G . B .
. # . B1
U1 # . #
F # A .
B2 # # U2
. IB IG .

stdout

11
LLDDDDUD.DR
RRDRLDDRDDL

Explicație

Fireboy pornește din $(0, 2)$, iar Watergirl pornește din $(0, 0)$, indexare de la $0$.

La fiecare pas, se execută simultan câte o mișcare pentru fiecare dintre cei doi jucători. De exemplu, la un anumit pas, Fireboy poate alege să se deplaseze în jos, iar Watergirl poate alege să stea pe loc.

La pasul $7$, adică al $8$-lea pas dacă pașii sunt indexați de la $0$, Fireboy se află pe butonul $B_2$ de la poziția $(4, 0)$, iar Watergirl intră pe ușa $U_2$ de la poziția $(4, 3)$ în același moment de timp. Această mutare este validă deoarece, după aplicarea simultană a celor două mișcări, Fireboy se află pe butonul corespunzător ușii.

Ambii ajung la ieșirile lor, IB la poziția $(5, 1)$ și IG la poziția $(5, 2)$, în același pas.