#include #include #include #include #include #include using namespace std; using i32 = int; using u32 = unsigned int; using i64 = long long; using u64 = unsigned long long; #define rep(i,n) for(int i=0; i<(int)(n); i++) const i64 INF = 1001001001001001001; using Modint = atcoder::static_modint<998244353>; int main(){ int H,W,K,L,R; cin >> H >> W >> K >> L >> R; L--; vector G(H); rep(y,H) cin >> G[y]; if((R-L) % 2 == 1){ cout << "No\n"; return 0; } if((H+W)%2 != K%2){ cout << "No\n"; return 0; } tuple dir[4] = {{1,0,'D',0},{-1,0,'U',1},{0,1,'R',2},{0,-1,'L',3}}; auto getdist = [&](int sy, int sx){ vector> que; vector pre(H, vector(W,-1)); pre[0][0] = -2; vector dist(H, vector(W,K+1)); dist[sy][sx] = 0; que.push_back({sy,sx}); rep(i,que.size()){ auto [y,x] = que[i]; for(auto [dy,dx,c,di] : dir){ int nx = x + dx, ny = y + dy; if(nx < 0 || ny < 0 || nx >= W || ny >= H) continue; if(G[ny][nx] == '#') continue; if(pre[ny][ny] != -1) continue; pre[ny][nx] = di; dist[ny][nx] = dist[y][x] + 1; que.push_back({ ny,nx }); } } return make_pair(move(dist), move(pre)); }; auto getpath = [&](int sy, int sx, int ty, int tx, const vector>& pre){ vector res; while(sy != ty || sx != tx){ auto [dy,dx,c,di] = dir[pre[ty][tx]]; res.push_back(di); ty -= dy; tx -= dx; } return res; }; auto [dist0, pre0] = getdist(0,0); auto [dist1, pre1] = getdist(H-1,W-1); int ty=-1, tx=-1, td=-1; for(int y=0; y