#include using namespace std; #define rep(i,n) for (int i=0;i<(int)(n);i++) #define all(v) v.begin(),v.end() using ll=long long; using pll=pair; using tll=tuple; const ll INF=(1ll<<60); template void chmin(T &a,T b){ if(a>b){ a=b; } } template void chmax(T &a,T b){ if(a pi={0,1,0,-1},pj={1,0,-1,0}; string dir="RDLU"; struct enemy{ int i,j,d; }; struct input{ int n,d,h; vector s; int m; vector e; vector> grid_enemy; int si,sj,ki,kj,gi,gj; void input_cin(){ cin >> n >> d >> h; s.resize(n); rep(i,n) cin >> s[i]; cin >> m; e.resize(m); grid_enemy.resize(n); rep(i,n) grid_enemy[i].resize(n,0); rep(i,m){ cin >> e[i].i >> e[i].j >> e[i].d; grid_enemy[e[i].i][e[i].j]=e[i].d; } rep(i,n){ rep(j,n){ if(s[i][j]=='S'){ si=i; sj=j; } if(s[i][j]=='K'){ ki=i; kj=j; } if(s[i][j]=='G'){ gi=i; gj=j; } } } } } input; struct solver{ struct result{ int score,hp; vector> visited; }; bool outside(int i,int j){ if(i<0||input.n<=i||j<0||input.n<=j) return true; else return false; } int char_idx(char c){ if(c=='R') return 0; else if(c=='D') return 1; else if(c=='L') return 2; else return 3; } int dist_root(vector> &v,vector>>> &dist_juwel){ int n=v.size(); int ret=0; rep(i,n-1){ int d=dist_juwel[v[i].first][v[i].second][v[i+1].first][v[i+1].second]; if(d==-1) return 1e9; ret+=d; } return ret; } result play(string &s){ int nt=s.size(); int ni=input.si,nj=input.sj; vector> visited(input.n,vector(input.n)); result ret={0,input.h,visited}; ret.visited[ni][nj]=true; rep(t,nt){ ni+=pi[char_idx(s[t])]; nj+=pj[char_idx(s[t])]; if(outside(ni,nj)){ ret.score=-1e9; ret.hp=-1e9; return ret; } if(!ret.visited[ni][nj]&&input.s[ni][nj]=='J') ret.score+=10; ret.visited[ni][nj]=true; ret.hp--; for(int i=ni;0<=i;i--){ if(input.s[i][nj]=='#') break; if(input.s[i][nj]=='E'){ if((t+1)%input.grid_enemy[i][nj]==0) ret.hp-=input.d; break; } } for(int i=ni;i> visited(input.n,vector(input.n)); result ret={0,input.h,visited}; ret.visited[ni][nj]=true; rep(t,nt){ ni+=pi[char_idx(s[t])]; nj+=pj[char_idx(s[t])]; if(outside(ni,nj)){ ret.score=-1e9; ret.hp=-1e9; return ret; } if(!ret.visited[ni][nj]&&input.s[ni][nj]=='J') ret.score+=10; ret.visited[ni][nj]=true; ret.hp--; for(int i=ni;0<=i;i--){ if(input.s[i][nj]=='#') break; if(input.s[i][nj]=='E'){ if((t+1)%input.grid_enemy[i][nj]==0) ret.hp-=input.d; break; } } for(int i=ni;i> bfs(int si,int sj){ queue> q; q.push({si,sj}); vector> dist(input.n,vector(input.n,-1)); dist[si][sj]=0; while(!q.empty()){ int ni,nj; tie(ni,nj)=q.front(); q.pop(); rep(k,4){ int ti=ni+pi[k],tj=nj+pj[k]; if(outside(ti,tj)) continue; if(input.s[ti][tj]=='#'||input.s[ti][tj]=='E') continue; if(dist[ti][tj]==-1){ dist[ti][tj]=dist[ni][nj]+1; q.push({ti,tj}); } } } return dist; } string min_path(int si,int sj,int gi,int gj){ string ret; queue> q; q.push({gi,gj}); vector> dist(input.n,vector(input.n,-1)); dist[gi][gj]=0; while(!q.empty()){ int ni,nj; tie(ni,nj)=q.front(); q.pop(); rep(k,4){ int ti=ni+pi[k],tj=nj+pj[k]; if(outside(ti,tj)) continue; if(input.s[ti][tj]=='#'||input.s[ti][tj]=='E') continue; if(dist[ti][tj]==-1){ dist[ti][tj]=dist[ni][nj]+1; q.push({ti,tj}); } } } int ni=si,nj=sj; while(ni!=gi||nj!=gj){ rep(k,4){ int ti=ni+pi[k],tj=nj+pj[k]; if(outside(ti,tj)) continue; if(dist[ti][tj]==dist[ni][nj]-1){ ni=ti; nj=tj; ret.push_back(dir[k]); break; } } } return ret; } string solve_root(string first_root,int si,int sj,int gi,int gj,int min_hp,int time_limit,vector>>> &dist_juwel){ string root=first_root; vector> visit_juwel; int ni=si,nj=sj; while(true){ vector> visited=play(root).visited; while(true){ auto now=chrono::system_clock::now(); int msec=chrono::duration_cast(now-start).count(); if(time_limit<=msec) break; vector> dist=bfs(ni,nj); pair> p={(int)1e9,{0,0}}; rep(i,input.n){ rep(j,input.n){ if(dist[i][j]==-1) continue; if(!visited[i][j]&&input.s[i][j]=='J') chmin(p,{dist[i][j],{i,j}}); } } if(p.first==1e9) break; int ti,tj; tie(ti,tj)=p.second; string new_root=root; new_root+=min_path(ni,nj,ti,tj); string new_new_root=new_root+min_path(ti,tj,gi,gj); if(play(new_new_root).hp<=min_hp){ break; } visit_juwel.emplace_back(ti,tj); result res=play(new_root); ni=ti; nj=tj; root=new_root; visited=res.visited; } auto now_a=chrono::system_clock::now(); int msec_a=chrono::duration_cast(now_a-start).count(); if(time_limit<=msec_a) break; auto now_start=chrono::system_clock::now(); int n=visit_juwel.size(); if(n==0) break; int pre_dist=dist_root(visit_juwel,dist_juwel); while(true){ auto now_now=chrono::system_clock::now(); int msec=chrono::duration_cast(now_now-now_start).count(); if(20<=msec) break; int a=mt()%n,b=mt()%n; if(b(now-start).count(); if(time_limit<=msec) break; } root+=min_path(ni,nj,gi,gj); return root; } void solve(){ vector>>> dist_juwel(input.n,vector>>(input.n,vector>(input.n,vector(input.n,-1)))); rep(i,input.n){ rep(j,input.n){ if(input.s[i][j]=='J') dist_juwel[i][j]=bfs(i,j); } } pair ans={(int)-1e9,""}; for(int i=0;i<=input.h;i+=60){ string root=""; root=solve_root(root,input.si,input.sj,input.ki,input.kj,i,100*(i/60+1)-50,dist_juwel); root=solve_root(root,input.ki,input.kj,input.gi,input.gj,0,100*(i/60+1),dist_juwel); chmax(ans,{play(root).score,root}); } for(auto &i:ans.second){ cout << "M " << i << '\n'; } } } solver; int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); input.input_cin(); solver.solve(); }