#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+2); rep(i, 1, H){cin >> S.at(i); S[i] = '#' + S[i] + '#';} rep(i, 1, W+2){S[0].push_back('#'); S[H+1].push_back('#');} 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;} vector> safe(H+2, vector(W+2, -1)); vector> safe2(H+2, vector(W+2, -1)); rep(i, 1, H){rep(j, 1, W){ // 周期2 if(S[i][j] == '.' && S[i-1][j] == '.' && S[i+1][j] == '.'){safe[i][j] = 0;} if(S[i][j] == '.' && S[i][j-1] == '.' && S[i][j+1] == '.'){safe[i][j] = 1;} // 周期4 if(S[i][j] == '.' && S[i-1][j-1] == '.' && S[i][j-1] == '.' && S[i-1][j] == '.' && S[i+1][j+1] == '.' && S[i][j+1] == '.' && S[i+1][j] == '.'){safe2[i][j] = 0;} if(S[i][j] == '.' && S[i-1][j+1] == '.' && S[i][j+1] == '.' && S[i-1][j] == '.' && S[i+1][j-1] == '.' && S[i][j-1] == '.' && S[i+1][j] == '.'){safe2[i][j] = 1;} //if(S[i][j] == '.' && S[i+1][j-1] == '.' && S[i][j-1] == '.' && S[i+1][j] == '.'){safe2[i][j] = 2;} //if(S[i][j] == '.' && S[i+1][j+1] == '.' && S[i][j+1] == '.' && S[i+1][j] == '.'){safe2[i][j] = 3;} }} int di[4] = {1, -1, 0, 0}; int dj[4] = {0, 0, 1, -1}; string mv = "DURL"; string mv_rev = "UDLR"; string mv2[2] = {"UD", "LR"}; string mv4[4] = {"ULDR", "URDL", "DLUR", "DRUL"}; vector> dist_from(H+2, vector(W+2, -1)); dist_from[1][1] = 0; deque> que; que.push_back({1, 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(S[nxi][nxj] == '#'){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+2, vector(W+2, -1)); dist_to[H][W] = 0; que.push_back({H, W}); 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(S[nxi][nxj] == '#'){continue;} if(dist_to[nxi][nxj] != -1){continue;} dist_to[nxi][nxj] = dist_to[ni][nj] + 1; que.push_back({nxi, nxj}); } } //rep(i, 1, H){rep(j, 1, W){cout << dist_to[i][j] << " ";} cout << endl;} rep(i, 1, H){rep(j, 1, W){ 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;} int flag = 0; if(cnt % 4 == 0 && safe2[i][j] != -1){flag = 1;} if(cnt % 2 == 0 && safe[i][j] != -1){flag = 2;} if(flag == 0){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(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)); //cout << ans << endl; if(flag == 1){ rep(k, 1, cnt / 4){ans += mv4[safe2[i][j]];} } else{ rep(k, 1, cnt / 2){ans += mv2[safe[i][j]];} } //cout << ans << endl; ni = i; nj = j; for(ll k = dist_to[i][j]; k > 0; k--){ rep(x, 0, 3){ 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; }