#include<bits/stdc++.h>

using namespace std;

const int INF = 1000000000;
int n,m;
vector<string> g;
const int N = 55;
const int dx[4] = {0,  0, 1, -1};
const int dy[4] = {1, -1, 0,  0};
string way = "DURL";
int dp[N][N][3001];
int solve(int x,int y,int k){
	int &res = dp[x][y][k];
	if (res != -1){
		return res;
	}
	if (k == 0 && x == n - 1 && y == m - 1){
		return res = 0;
	}
	if (k == 0 && x != n - 1 && y != m - 1){
		return res = INF;
	}
	if (k > 0){
		int ans = INF;
		for(int i = 0; i < 4; i++){
			int x1 = x + dx[i];
			int y1 = y + dy[i];
			if (0 <= x1 && x1 < n && 0 <= y1 && y1 < m && g[x1][y1] == '.'){
				ans = min(ans,solve(x1,y1,k - 1) + 1);
			}
		}
		return res = ans;
	}
}
string lastAns;
void findAns(int x,int y,int k){
	if (k == 0 && x == n - 1 && y == m - 1){
		return;
	}
	if (k == 0 && x != n - 1 && y != m - 1){
		return;
	}
	if (k > 0){
		int ans = INF;
		int r1,r2,tt;
		for(int i = 0; i < 4; i++){
			int x1 = x + dx[i];
			int y1 = y + dy[i];
			if (0 <= x1 && x1 < n && 0 <= y1 && y1 < m && g[x1][y1] == '.' && dp[x1][y1][k - 1] != -1 && dp[x1][y1][k - 1] + 1 < ans){
				ans = dp[x1][y1][k - 1] + 1;
				r1 = x1;
				r2 = y1;
				tt = i;
			}
		}
		lastAns = lastAns + way[tt];
		findAns(r1,r2,k - 1);
	}
}
class StepsConstruct {
public:
	string construct(vector <string> a, int k) {
		n = a.size();
		m = a[0].length();
		g = a;
		memset(dp,-1,sizeof dp);
		int x = solve(0,0,k);
		findAns(0,0,k);
		cout << "x = " << lastAns << endl;
		if ( x == k){
			cout << lastAns << endl;
			return lastAns;
		}
		return "";
	}
};


<%:testing-code%>
//Powered by KawigiEdit 2.1.8 (beta) modified by pivanof!