Problem
Melone vuole testare il suo nuovo sviluppo: un robot in grado di muoversi nei labirinti.
Il robot si trova in un labirinto rettangolare di dimensioni n × m. Ognuna delle celle del labirinto è vuota o occupata da un ostacolo.
Il robot può spostarsi tra celle adiacenti a sinistra (simbolo "L"), a destra (simbolo "R", in alto (simbolo "U") o in basso (simbolo "D"). Il robot può spostarsi in una cella solo se è vuota. Inizialmente, il robot si trova in una gabbia vuota.
Melone vuole che il robot percorra il ciclo lessicograficamente minimo di lunghezza esattamente k, che inizia e finisce nella cella in cui si trova inizialmente il robot. Il robot può visitare qualsiasi cella un numero illimitato di volte (inclusa quella iniziale).
Il percorso del robot è dato da una stringa composta dai caratteri "L", "R", "U" e "D". Ad esempio, se il robot scende prima, poi a sinistra, poi a destra e poi su, il suo percorso viene scritto come "DLRU".
Aiuta Melona a determinare quale percorso del robot corrisponde al ciclo lessicograficamente minimo di lunghezza esattamente k, oppure dimmi che non esiste nulla del genere.
Inserimento:
La prima riga è seguita da tre numeri interi n, m e k (1 ≤ n, m ≤ 1000, 1 ≤ k ≤ 10
6< / sup>) — dimensioni del labirinto e lunghezza del ciclo.
Ognuna delle n righe successive contiene m caratteri — descrizione del labirinto Se il simbolo è ".", la cella corrente è vuota. Se il simbolo è "*", la cella corrente è occupata da un ostacolo. Se il simbolo è uguale a "X", inizialmente il robot si trova in questa cella ed è vuota. È garantito che il carattere "X" si verifica esattamente una volta nel labirinto.
Uscita:
Stampa il percorso lessicograficamente minimo del Robot di lunghezza esattamente k, che inizia e finisce nella cella in cui si trova inizialmente il Robot. Se tale percorso non esiste, stampa "IMPOSSIBILE" (senza virgolette).
Esempi:
| Input |
Uscita |
2 3 2
.**
X.. |
RL |
5 6 14
..***.
*...X.
..*...
..*.**
....*. |
DLDDLLLRRRUURU |
3 3 4
***
*X*
*** |
IMPOSSIBILE |