/* Topcoder SRM 707, D2 500-Pointer
   StepsConstruct
   James S. Plank
   Mon Feb 13 15:27:05 EST 2017
 */

#include <string>
#include <vector>
#include <iostream>
#include <cstdio>
#include <cstdlib>
using namespace std;

class StepsConstruct
{
    public:
        string construct(vector <string> board, int k);
};

string StepsConstruct::construct(vector <string> board, int k)
{
    int R, C;                     // Rows and columns of the boards
    vector <int> BFSQ;            // The BFS queue, holds index: r*C + c
    vector <string> Direction;    // This holds each node's direction on the shortest path

    int r, c, i;                  // Loop variables.
    int l;                        // The final path length.
    string path;                  // You construct the final path backward and store it here.
    string rv;                    // Then you reverse it and return it here.

    vector <char> opposite;       // Opposite(d) is the opposite direction of d.
                                  // This helps extend the path to be the right size.

    /* First, set up the opposite vector entries for 'U', 'D', 'L' and 'R'. */

    opposite.resize('U'+1);
    opposite['U'] = 'D';
    opposite['D'] = 'U';
    opposite['L'] = 'R';
    opposite['R'] = 'L';

    /* Set R and C, and initialize Direction. */

    R = board.size();
    C = board[0].size();
    Direction.resize(R);
    for (i = 0; i < R; i++) Direction[i].resize(C, '-');

    /* If the upper-left square is not a dot, then it's impossible. */

    if (board[0][0] == '#') return "";

    /* Push node [0,0] onto the BFSQ, and set its entry in the board to '#'. */

    BFSQ.push_back(0);         /* Push node 0*C+0 = 0 onto the BFSQ. */
    board[0][0] = '#';

    /* Now, process the BFSQ. We're going to be pushing nodes onto
       BFSQ, so its size can increase from iteration to iteration.
       We don't delete nodes on the BFSQ. */

    for (i = 0; i < BFSQ.size(); i++) {

        r = BFSQ[i]/C;         /* Get the row and column of the node from its value in BFSQ */
        c = BFSQ[i]%C;

        /* If it is not the ending node, then check the nodes to the left, right,
           up and down, and push them onto the BFSQ (setting board and Direction
           at the same time */

        if (r != R-1 || c != C-1) {

            /* Check the left node. */

            if (c > 0 && board[r][c-1] == '.') {
                BFSQ.push_back((r)*C+c-1);
                board[r][c-1] = '#';
                Direction[r][c-1] = 'L';
            }

            /* Check the right node. */

            if (c+1 < C && board[r][c+1] == '.') {
                BFSQ.push_back((r)*C+c+1);
                board[r][c+1] = '#';
                Direction[r][c+1] = 'R';
            }

            /* Check the upper node. */

            if (r > 0 && board[r-1][c] == '.') {
                BFSQ.push_back((r-1)*C+c);
                board[r-1][c] = '#';
                Direction[r-1][c] = 'U';
            }

            /* Check the lower node. */

            if (r+1 < R && board[r+1][c] == '.') {
                BFSQ.push_back((r+1)*C+c);
                board[r+1][c] = '#';
                Direction[r+1][c] = 'D';
            }

            /* Otherwise, we are at the target node.  We need to do a lot here,
               so I'll go through it in steps. */

        } else {

            /* First, find the path back to the starting node, pushing the
               directions onto the path vector.  This creates the path in reverse. */

            while (r != 0 || c != 0) {
                path.push_back(Direction[r][c]);
                if (Direction[r][c] == 'L') {
                    c += 1;
                } else if (Direction[r][c] == 'R') {
                    c -= 1;
                } else if (Direction[r][c] == 'D') {
                    r -= 1;
                } else {
                    r += 1;
                }
            }

            /* Set l to be the path length, and return when it's impossible. */

            l = path.size();
            if (l > k) return "";
            if (l % 2 != k % 2) return "";

            /* Now, while l is smaller than k, keep doing the opposite of the last step.
               The path is reversed right now, so this will keep repeating the first step
               of the path, and then going back to the starting spot. */

            while (l < k) {
                path.push_back(opposite[path[l-1]]);
                l++;
            }

            /* Reverse the path and return it. */

            for (i = 0; i < path.size(); i++) rv.push_back(path[path.size()-i-1]);
            return rv;
        }
    }

    /* If you get here, you couldn't get from the starting node to
       the ending node.  It's impossible */

    return "";
}