import java.io.*; import java.util.*; import java.util.concurrent.ThreadLocalRandom; import java.util.function.IntUnaryOperator; import java.util.function.LongUnaryOperator; import java.util.stream.Collectors; public class Main { static boolean isLocal; Random rand = new Random(); In in = new In(System.in); PrintStream out = System.out; long inf = 0x1fffffffffffffffL; int iinf = 0x3fffffff; long startTime; public static final int N = 60; public int D; public static final int H = 1500; public int M; public int J; public char[] grid; public Pos[] ps; public int[] ds; public Pos[] jps; int[][] distances; int[][] beam = new int[60][N * N]; int[] avgWait = new int[N * N]; int[] jid = new int[N * N]; public static final String[] ss = {"M L", "M U", "M R", "M D", "S"}; long solve(int seed) { startTime = System.currentTimeMillis(); in(); distances = new int[J+3][J+3]; for (int i = 0; i < J + 3; i++) { Arrays.fill(distances[i], iinf); } for (int i = 0; i < M; i++) { for (int d = 0; d < 4; d++) { Pos cur = ps[i]; while (true) { cur = cur.moved(d); if (cur == null || grid[cur.z] == '#') { break; } for (int j = 0; j < 60; j += ds[i]) { beam[j][cur.z]++; } } } } for (int i = 0; i < N * N; i++) { int c = 1; for (int j = 0; j < 60; j++) { if (beam[j][i] > 0) { c++; } else { c = 1; } avgWait[i] += c; } } for (int i = 0; i < J + 3; i++) { calcDist(i); } // BitSet visited = new BitSet(J + 3); // visited.set(J); // visited.set(J + 1); // visited.set(J + 2); // List routes = new ArrayList<>(); // routes.add(J); // routes.add(J + 1); // routes.add(J + 2); // int dsum = distances[J][J+1] + distances[J+1][J+2]; // int c = 0; // while (elapsed() < 2000) { // int p; // do { // p = rand.next(0, J); // } while (visited.get(p)); // int bi = -1; // int bd = iinf; // for (int i = 1; i < routes.size(); i++) { // int f = routes.get(i - 1); // int t = routes.get(i); // int diff = distances[f][p] + distances[p][t] - distances[f][t]; // if (bd > diff) { // bd = diff; // bi = i; // } // } // if (bi == -1) { // continue; // } //// debug(p, bi, bd, dsum); // if (routes.size() >= 200) { // break; // } //// if (dsum + bd * MUL[D] >= 60 * 500) { ////// c++; ////// if (c >= 100) { ////// break; ////// } else { ////// continue; ////// } //// continue; //// } // visited.set(p); // dsum += bd; // routes.add(bi, p); // } debug("?", elapsed()); State result = annealing(new State(), 180*10, 180, 2500); List routes = result.routes; debug("?", elapsed()); Pos p = jps[J]; int tt = 0; int ds1 = 0; int ds2 = 0; totalCost = 0; for (int i = 1; i < routes.size(); i++) { Result res = route(jps[routes.get(i - 1)], jps[routes.get(i)], tt); // debug(distances[routes.get(i - 1)][routes.get(i)], res.damage * 60); ds1 += distances[routes.get(i - 1)][routes.get(i)]; ds2 += res.damage; // debug(p, res.from, res.to, res.damage, (tt+res.time)%60); res.out(p, tt); tt = (tt + res.time) % 60; p = res.to; } debug(D, result.dsum, ds1, result.dsum/60, ds1/60, ds2, ds2*60./result.dsum); if (ds2 >= 1500) { debug("!"); throw new RuntimeException(); } debug(ds2, totalCost, routes.size() * 10); return routes.size() * 10L; // List routes = new ArrayList<>(); // routes.add(route(jps[J], jps[J + 1], 0)); // routes.add(route(jps[J + 1], jps[J + 2], routes.get(0).time)); // int dsum = routes.get(0).damage + routes.get(1).damage; // while (true) { // int p; // do { // p = rand.next(0, J); // } while (visited.get(p)); // int tt = 0; // int bi = 0; // int bd = iinf; // Result br1 = null, br2 = null; // for (int i = 0; i < routes.size(); i++) { // Result r = routes.get(i); // Result r1 = route(r.from, jps[p], tt); // Result r2 = route(jps[p], r.to, (tt + r.time) % 60); // int diff = r1.damage + r2.damage - r.damage; // if (bd > diff) { // bd = diff; // bi = i; // br1 = r1; // br2 = r2; // } // tt = (tt + r.time) % 60; // } // debug(p, bi, bd, dsum); // if (dsum + bd >= 700) { // break; // } // visited.set(p); // dsum += bd; // routes.set(bi, br1); // routes.add(bi + 1, br2); // } // Pos p = jps[J]; // int tt = 0; // for (Result res : routes) { // debug(p, res.from, res.to); // res.out(p, tt); // tt = (tt + res.time) % 60; // p = res.to; // } // visited.set(J + 2); // visited.set(J); // tt = moveTo(J, J+1, tt, visited); // visited.clear(J + 2); // tt = moveTo(J+1, J+2, tt, visited); } //1678 int totalCost = 0; // int moveTo(int s, int g, int tt, BitSet visited) { // int cur = s; // int ds = 0; // while (cur != g) { // int md = iinf; // int mi = -1; // for (int i = 0; i < J + 3; i++) { // if (visited.get(i)) { // continue; // } //// debug(i, cur, jps[i].dist(jps[g]), distances[cur * (J + 3) + i]); // int d = distances[cur * (J + 3) + i] + jps[i].dist(jps[g]) * 50; // if (md > d) { // md = d; // mi = i; // } // } // ds += distances[cur * (J + 3) + mi]; // visited.set(mi); // tt = moveStraight(cur, mi, tt); // cur = mi; // } // debug(ds, totalCost); // return tt; // } public static final double[] MUL = {0, 0, 0, 1.25, 1.33, 1.4, 1.6, 1.8}; class State { BitSet visited = new BitSet(J + 3); List routes = new ArrayList<>(); int dsum; double score; boolean hasScore; State prevCopy; State() { visited.set(J); visited.set(J + 1); visited.set(J + 2); routes.add(J); routes.add(J + 1); routes.add(J + 2); dsum = distances[J][J+1] + distances[J+1][J+2]; } State(State prev) { this.visited = (BitSet)prev.visited.clone(); this.routes = new ArrayList<>(prev.routes); this.dsum = prev.dsum; this.score = prev.score; this.hasScore = true; } int real() { int damage = 0; int tt = 0; for (int i = 1; i < routes.size(); i++) { Result res = route(jps[routes.get(i - 1)], jps[routes.get(i)], tt); // debug(distances[routes.get(i - 1)][routes.get(i)], res.damage * 60); damage += res.damage; // debug(p, res.from, res.to, res.damage); tt = (tt + res.time) % 60; } return damage; } State rollback() { return prevCopy; } int neighbor0(double stage) { while (true) { int p; do { p = rand.next(0, J); } while (visited.get(p)); int bi = -1; int bd = iinf; for (int i = 1; i < routes.size(); i++) { int f = routes.get(i - 1); int t = routes.get(i); int diff = distances[f][p] + distances[p][t] - distances[f][t]; if (bd > diff) { bd = diff; bi = i; } } if (bi == -1) { continue; } visited.set(p); dsum += bd; routes.add(bi, p); score = calcScore(0); break; } return 0; } int neighbor1(double stage) { int bd = -iinf; int bp = 0; for (int p = 1; p + 1 < routes.size(); p++) { int f = routes.get(p - 1); int t = routes.get(p + 1); int r = routes.get(p); if (r >= J) { continue; } int diff = distances[f][r] + distances[r][t] - distances[f][t]; if (bd < diff) { bd = diff; bp = p; } } visited.clear(routes.get(bp)); dsum -= bd; routes.remove(bp); score = calcScore(0); return 1; } int neighbor(double stage, double rs) { hasScore = false; prevCopy = copy(); if (routes.size() >= 60 && rand.next(3) == 0 || dsum * MUL[D] >= 60 * 1000 * rs) { // debug(dsum * MUL[D], getScore(stage), routes.size(), 36000, 1); return neighbor1(stage); } else { // debug(dsum * MUL[D], getScore(stage), routes.size(), 36000, 0); return neighbor0(stage); } } State copy() { return new State(this); } double getScore(double stage) { if (!hasScore) { score = calcScore(stage); hasScore = true; } return score; } double calcScore(double stage) { double score = (routes.size() - 3) * 180*5 - dsum * MUL[D]; return score; } long realScore() { int score = 0; return score; } } State annealing(State state, double startTemp, double endTemp, long timeLimit) { State bestState = state.copy(); double bestScore = state.getScore(0); int itr = 0; int rb = 0; int c0 = 0; double rs = 1; boolean calc = false; while (true) { long nowTime = System.currentTimeMillis() - startTime; if (nowTime >= timeLimit) { break; } double stage = (double)nowTime / timeLimit; if (stage > 0.8 && !calc) { calc = true; rs = 1300. / state.real(); debug("??", rs); } itr++; double prevScore = state.getScore(stage); double temp = startTemp + (endTemp - startTemp) * nowTime / timeLimit; double thres = prevScore + rand.nextLog() * temp; int nid = state.neighbor(stage, rs); if (nid == -1) { continue; } if (nid == 0) { c0++; } if (bestScore < state.getScore(stage)) { bestScore = state.getScore(stage); bestState = state.copy(); } if (state.getScore(stage) <= thres) { state = state.rollback(); rb++; } } debug(itr, rb, c0); return bestState; } class Result { List route; int damage; int time; Pos from; Pos to; public Result(List route, int damage, Pos from, Pos to) { this.route = route; this.damage = damage; this.time = route.size() % 60; this.from = from; this.to = to; } public void out(Pos p, int tt) { for (int v : route) { if (v < 4) p = p.moved(v); tt = (tt + 1) % 60; totalCost += D * beam[tt][p.z]; totalCost++; out.println(ss[v]); } } } Result route(Pos s, Pos g, int tt) { class S { private final Pos p; private final int t; private final int d; public S(Pos p, int t, int d) { this.p = p; this.t = t; this.d = d; } } PriorityQueue queue = new PriorityQueue<>(Comparator.comparingInt(v -> v.d)); queue.add(new S(s, tt, 0)); int[][] dist = new int[60][N * N]; int[][] prev = new int[60][N * N]; for (int i = 0; i < 60; i++) { Arrays.fill(dist[i], iinf); Arrays.fill(prev[i], -1); } dist[tt][s.z] = 0; while (!queue.isEmpty()) { S v = queue.remove(); if (dist[v.t][v.p.z] < v.d) { continue; } if (v.p.z == g.z) { List route = new ArrayList<>(); Pos cur = v.p; int ct = v.t; int damage = dist[ct][cur.z]; while (prev[ct][cur.z] != -1) { route.add(prev[ct][cur.z]); if (prev[ct][cur.z] < 4) { cur = cur.moved((prev[ct][cur.z] + 2) % 4); } ct = (ct + 59) % 60; } Collections.reverse(route); return new Result(route, damage, s, g); } int nt = (v.t + 1) % 60; for (int d = 0; d < 4; d++) { Pos q = v.p.moved(d); if (q == null || grid[q.z] == '#') { continue; } int cost = dist[v.t][v.p.z] + 1 + beam[nt][q.z] * D; if (dist[nt][q.z] > cost) { dist[nt][q.z] = cost; prev[nt][q.z] = d; queue.add(new S(q, nt, cost)); } } int cost = dist[v.t][v.p.z] + 1 + beam[nt][v.p.z] * D; if (dist[nt][v.p.z] > cost) { dist[nt][v.p.z] = cost; prev[nt][v.p.z] = 4; queue.add(new S(v.p, nt, cost)); } } throw new RuntimeException(); } void calcDist(int s) { class S { private final Pos p; private final int d; public S(Pos p, int d) { this.p = p; this.d = d; } } PriorityQueue queue = new PriorityQueue<>(Comparator.comparingInt(v -> v.d)); queue.add(new S(jps[s], 0)); int[] dist = new int[N * N]; Arrays.fill(dist, iinf); dist[jps[s].z] = 0; while (!queue.isEmpty()) { S v = queue.remove(); if (dist[v.p.z] < v.d) { continue; } if (jid[v.p.z] != -1) { distances[s][jid[v.p.z]] = v.d; } for (int d = 0; d < 4; d++) { Pos q = v.p.moved(d); if (q == null || grid[q.z] == '#') { continue; } int cost = dist[v.p.z] + avgWait[q.z]; if (dist[q.z] > cost) { dist[q.z] = cost; queue.add(new S(q, cost)); } } } } void in() { in.nextInt(); D = in.nextInt(); in.nextInt(); grid = new char[N * N]; int jc = 0; for (int i = 0; i < N; i++) { char[] s = in.nextCharArray(); for (int j = 0; j < N; j++) { grid[i * N + j] = s[j]; if (grid[i * N + j] == 'J') { jc++; } } } M = in.nextInt(); J = jc; jps = new Pos[J + 3]; ps = new Pos[M]; ds = new int[M]; for (int i = 0; i < M; i++) { int y = in.nextInt(); int x = in.nextInt(); int d = in.nextInt(); ps[i] = pos(x, y); ds[i] = d; } jc = 0; Arrays.fill(jid, -1); for (int i = 0; i < N * N; i++) { if (grid[i] == 'S') { jps[J] = pos(i); jid[i] = J; grid[i] = '.'; } else if (grid[i] == 'K') { jps[J + 1] = pos(i); jid[i] = J + 1; grid[i] = '.'; } else if (grid[i] == 'G') { jps[J + 2] = pos(i); jid[i] = J + 2; grid[i] = '.'; } else if (grid[i] == 'J') { jid[i] = jc; jps[jc++] = pos(i); } else if (grid[i] == 'E') { grid[i] = '#'; } } } static Pos pos(int x, int y) { return Pos.instances[y * N + x]; } static Pos pos(int z) { return Pos.instances[z]; } static class Timing { Pos p; int t, z; public Timing(Pos p, int t) { this.p = p; this.t = t; this.z = p.z * 60 + t; } } static class Pos implements Comparable { static Pos[] instances; static Pos[] moved; static { instances = new Pos[N * N]; moved = new Pos[4 * N * N]; for (int i = 0; i < N * N; i++) { instances[i] = new Pos(i % N, i / N, i); } for (int i = 0; i < N * N; i++) { for (int d = 0; d < 4; d++) { // LURD int nx = i % N + (d - 1) % 2; int ny = i / N + (d - 2) % 2; if (0 <= nx && nx < N && 0 <= ny && ny < N) { moved[i * 4 + d] = instances[ny * N + nx]; } } } } final int x, y, z; private Pos(int x, int y, int z) { this.x = x; this.y = y; this.z = z; } Pos moved(int d) { return moved[z * 4 + d]; } int dist(Pos o) { return Math.abs(x - o.x) + Math.abs(y - o.y); } Pos[] neighbors() { Pos[] p = new Pos[4]; int i = 0; if ((p[i] = moved(0)) != null) i++; if ((p[i] = moved(1)) != null) i++; if ((p[i] = moved(2)) != null) i++; if ((p[i] = moved(3)) != null) i++; return i == 4 ? p : Arrays.copyOf(p, i); } @Override public int compareTo(Pos o) { return Integer.compare(z, o.z); } @Override public boolean equals(Object o) { return o instanceof Pos && z == ((Pos)o).z; } @Override public int hashCode() { return z; } @Override public String toString() { return String.format("(%d, %d)", x, y); } } static void debug(Object... args) { if (!isLocal) { return; } if (args == null || args.getClass() != Object[].class) { args = new Object[] {args}; } System.err.println(Arrays.stream(args).map(obj -> { Class clazz = obj == null ? null : obj.getClass(); return clazz == byte[].class ? Arrays.toString((byte[])obj) : clazz == short[].class ? Arrays.toString((short[])obj) : clazz == int[].class ? Arrays.toString((int[])obj) : clazz == long[].class ? Arrays.toString((long[])obj) : clazz == char[].class ? Arrays.toString((char[])obj) : clazz == float[].class ? Arrays.toString((float[])obj) : clazz == double[].class ? Arrays.toString((double[])obj) : clazz == boolean[].class ? Arrays.toString((boolean[])obj) : obj instanceof Object[] ? Arrays.deepToString((Object[])obj) : String.valueOf(obj); }).collect(Collectors.joining(" "))); } long elapsed() { return (long)((System.currentTimeMillis() - startTime) * (isLocal ? 1.7 : 1)); } boolean elapsed(long timeLimit) { return elapsed() >= timeLimit; } public static void main(String[] args) { new Main().solve(0); } static class Random { private long a, b, c, d; Random() { this(ThreadLocalRandom.current().nextLong()); } Random(long seed) { this.a = seed; for (int i = 0; i < 20; i++) { rand(); } } private int rand() { long t = a ^ (a << 11); a = b; b = c; c = d; d = d ^ (d >>> 19) ^ t ^ (t >>> 8); return (int)(a & 0x7fffffff); } long next() { return (long)rand() << 31 | rand(); } int next(int n) { return rand() % n; } int next(int l, int r) { return rand() % (r - l) + l; } double nextDouble() { return rand() / 2147483648.0; } double nextLog() { return Math.log(rand() + 1) - 21.487562597358306; } } static class In { private final BufferedReader reader; private StringTokenizer tokenizer; In(InputStream input) { this.reader = new BufferedReader(new InputStreamReader(input), 0x10000); } String next() { try { while (tokenizer == null || !tokenizer.hasMoreTokens()) { tokenizer = new StringTokenizer(reader.readLine()); } } catch (IOException ignored) { } return tokenizer.nextToken(); } int nextInt() { return Integer.parseInt(next()); } long nextLong() { return Long.parseLong(next()); } double nextDouble() { return Double.parseDouble(next()); } char[] nextCharArray() { return next().toCharArray(); } String[] nextStringArray(int n) { String[] s = new String[n]; for (int i = 0; i < n; i++) { s[i] = next(); } return s; } char[][] nextCharGrid(int n, int m) { char[][] a = new char[n][m]; for (int i = 0; i < n; i++) { a[i] = next().toCharArray(); } return a; } int[] nextIntArray(int n) { int[] a = new int[n]; for (int i = 0; i < n; i++) { a[i] = nextInt(); } return a; } int[] nextIntArray(int n, IntUnaryOperator op) { int[] a = new int[n]; for (int i = 0; i < n; i++) { a[i] = op.applyAsInt(nextInt()); } return a; } int[][] nextIntMatrix(int h, int w) { int[][] a = new int[h][w]; for (int i = 0; i < h; i++) { a[i] = nextIntArray(w); } return a; } long[] nextLongArray(int n) { long[] a = new long[n]; for (int i = 0; i < n; i++) { a[i] = nextLong(); } return a; } long[] nextLongArray(int n, LongUnaryOperator op) { long[] a = new long[n]; for (int i = 0; i < n; i++) { a[i] = op.applyAsLong(nextLong()); } return a; } long[][] nextLongMatrix(int h, int w) { long[][] a = new long[h][w]; for (int i = 0; i < h; i++) { a[i] = nextLongArray(w); } return a; } List> nextEdges(int n, int m, boolean directed) { List> res = new ArrayList<>(); for (int i = 0; i < n; i++) { res.add(new ArrayList<>()); } for (int i = 0; i < m; i++) { int u = nextInt() - 1; int v = nextInt() - 1; res.get(u).add(v); if (!directed) { res.get(v).add(u); } } return res; } } }