#include #include #include #define rep(i, l, r) for(ll i = (l); i <= (r); i++) #define rrep(i, l, r) for(ll i = (r); i >= (l); i--) #define ff first #define ss second #define pb push_back #define ALL(a) (a).begin(),(a).end() typedef long long ll; const int INF32 = 2147483647; const ll INF64 = 9223372036854775807ll; const int MAX=5100000; using namespace std; using namespace atcoder; const ll MOD=998244353ll; using mint = modint998244353; // aよりもbが大きいならばaをbで更新する // (更新されたならばtrueを返す) template bool chmax(T &a, const T& b) { if (a < b) { a = b; // aをbで更新 return true; } return false; } // aよりもbが小さいならばaをbで更新する // (更新されたならばtrueを返す) template bool chmin(T &a, const T& b) { if (a > b) { a = b; // aをbで更新 return true; } return false; } //cin, cout void CIN() {}; template void CIN(T &&x, U &&...y) { cin >> x; CIN(forward(y)...); } void _COUT() { cout << '\n'; } template void _COUT(T &&x, U &&...y) { cout << ' ' << x; _COUT(forward(y)...); } void COUT() { _COUT(); }; template void COUT(T &&x, U &&...y) { cout << x; _COUT(forward(y)...); } vector fact, fact_inv, inv; /* init_nCk :二項係数のための前処理 計算量:O(n) */ void init_nCk(int SIZE) { fact.resize(SIZE + 5); fact_inv.resize(SIZE + 5); inv.resize(SIZE + 5); fact[0] = fact[1] = 1; fact_inv[0] = fact_inv[1] = 1; inv[1] = 1; for (int i = 2; i < SIZE + 5; i++) { fact[i] = fact[i - 1] * i % MOD; inv[i] = MOD - inv[MOD % i] * (MOD / i) % MOD; fact_inv[i] = fact_inv[i - 1] * inv[i] % MOD; } } /* nCk :MODでの二項係数を求める(前処理 int_nCk が必要) 計算量:O(1) */ long long nCk(int n, int k) { assert(!(n < k)); assert(!(n < 0 || k < 0)); return fact[n] * (fact_inv[k] * fact_inv[n - k] % MOD) % MOD; } bool check_grid(ll x, ll y, ll H, ll W){ if(x < 0 || H <= x){return false;} else if(y < 0 || W <= y){return false;} return true; } int main() { cin.tie(0); ios::sync_with_stdio(false); ll H, W, K, L, R; cin >> H >> W >> K >> L >> R; vector S(H); rep(i, 0, H-1){cin >> S.at(i);} ll dist = (H-1) + (W-1); ll move = K - (R - L + 1); if(dist % 2 != K % 2){cout << "No" << endl; return 0;} if(move < dist){cout << "No" << endl; return 0;} if((R-L+1) % 2 == 1){cout << "No" << endl; return 0;} if(L == 1){cout << "No" << endl;} if(R == K){cout << "No" << endl;} vector> safe(H, vector(W, 0)); rep(i, 1, H-2){rep(j, 0, W-1){ if(S[i][j] == '.' && S[i-1][j] == '.' && S[i+1][j] == '.'){safe[i][j] = 1;} }} rep(i, 0, H-1){rep(j, 1, W-2){ if(S[i][j] == '.' && S[i][j-1] == '.' && S[i][j+1] == '.'){safe[i][j] = 2;} }} int di[4] = {1, -1, 0, 0}; int dj[4] = {0, 0, 1, -1}; string mv = "DURL"; string mv_rev = "UDLR"; vector> dist_from(H, vector(W, -1)); dist_from[0][0] = 0; deque> que; que.push_back({0, 0}); while(!que.empty()){ auto [ni, nj] = que.front(); que.pop_front(); rep(i, 0, 3){ int nxi = ni + di[i]; int nxj = nj + dj[i]; if(check_grid(nxi, nxj, H, W) == false){continue;} if(dist_from[nxi][nxj] != -1){continue;} dist_from[nxi][nxj] = dist_from[ni][nj] + 1; que.push_back({nxi, nxj}); } } vector> dist_to(H, vector(W, -1)); dist_to[H-1][W-1] = 0; que.push_back({H-1, W-1}); while(!que.empty()){ auto [ni, nj] = que.front(); que.pop_front(); rep(i, 0, 3){ int nxi = ni + di[i]; int nxj = nj + dj[i]; if(check_grid(nxi, nxj, H, W) == false){continue;} if(dist_to[nxi][nxj] != -1){continue;} dist_to[nxi][nxj] = dist_to[ni][nj] + 1; que.push_back({nxi, nxj}); } } rep(i, 0, H-1){rep(j, 0, W-1){ ll cnt = K - dist_to[i][j] - dist_from[i][j]; if(safe[i][j] == 0){continue;} if(dist_from[i][j] == -1){continue;} if(dist_to[i][j] == -1){continue;} if(dist_from[i][j] >= L){continue;} if(dist_to[i][j] < (K - R)){continue;} if(dist_to[i][j] % 2 != (K - R) % 2){continue;} if(cnt % 2 == 1){continue;} string ans = ""; cout << "Yes" << endl; int ni = i, nj = j; for(ll k = dist_from[i][j]; k > 0; k--){ rep(x, 0, 3){ if(check_grid(ni+di[x], nj+dj[x], H, W) == false){continue;} if(dist_from[ni+di[x]][nj+dj[x]] == k-1){ ni = ni+di[x]; nj = nj+dj[x]; ans.push_back(mv_rev[x]); break; } } } reverse(ALL(ans)); rep(k, 1, cnt){ if(safe[i][j] == 1){ if(k % 2 == 0){ans.push_back('U');} else{ans.push_back('D');} } else{ if(k % 2 == 0){ans.push_back('L');} else{ans.push_back('R');} } } ni = i; nj = j; for(ll k = dist_to[i][j]; k > 0; k--){ rep(x, 0, 3){ if(check_grid(ni+di[x], nj+dj[x], H, W) == false){continue;} if(dist_to[ni+di[x]][nj+dj[x]] == k-1){ ni = ni+di[x]; nj = nj+dj[x]; ans.push_back(mv[x]); break; } } } cout << ans << endl; return 0; }} cout << "No" << endl; return 0; }