namespace atcoder {}

#ifdef LOCAL
#define dbg(x) cerr << __LINE__ << " : " << #x << " = " << (x) << endl;
#else
#define NDEBUG
#define dbg(x) true;
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#endif

#ifdef GTEST
#include <gtest/gtest.h>
#endif

#include <math.h>

#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <chrono>
#include <cstdlib>
#include <cstring>
#include <functional>
#include <iomanip>
#include <iostream>
#include <limits>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#ifdef PERF
#include <gperftools/profiler.h>
#endif

using namespace std;
using namespace atcoder;
#define fast_io                     \
  ios_base::sync_with_stdio(false); \
  cin.tie(0);                       \
  cout.tie(0);
#define ll long long int
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define reps(i, n) for (int i = 1; i <= (int)(n); i++)
#define REP(i, n) for (int i = n - 1; i >= 0; i--)
#define REPS(i, n) for (int i = n; i > 0; i--)
#define MOD (long long int)(1e9 + 7)
#define INF (int)(1e9)
#define LINF (long long int)(1e18)
#define chmax(a, b) a = (((a) < (b)) ? (b) : (a))
#define chmin(a, b) a = (((a) > (b)) ? (b) : (a))
#define all(v) v.begin(), v.end()
typedef pair<int, int> Pii;
typedef pair<ll, ll> Pll;
constexpr double PI = acos(-1);

#ifdef NDEBUG
#define CHECK(v1, op, v2)
#else
#define CHECK(v1, op, v2)                            \
  if (!((v1)op(v2))) {                               \
    cerr << "ERROR:" << (v1) << " " << (v2) << endl; \
    assert((v1)op(v2));                              \
  }
#endif

long double nCr(const int n, const int r) {
  long double ret = 1;
  rep(t, r) {
    ret *= (n - t);
    ret /= (r - t);
  }
  return ret;
}

template <typename T>
string to_string(const vector<T>& vec) {
  string ret = "";
  rep(i, vec.size()) {
    ret += vec[i].to_string();
    if (i + 1 != vec.size()) {
      ret += ",";
    }
  }
  return ret;
}

template <typename T>
ostream& operator<<(ostream& os, const vector<T>& vec) {
  os << to_string(vec);
  return os;
}

uint32_t xorshift() {
  static uint32_t x = 12345789;
  static uint32_t y = 362436069;
  static uint32_t z = 521288629;
  static uint32_t w = 88675123;
  uint32_t t;
  t = x ^ (x << 11);
  x = y;
  y = z;
  z = w;
  w ^= t ^ (t >> 8) ^ (w >> 19);

  return w;
}

int rand(const uint32_t l, const uint32_t r) {
  return xorshift() % (r - l) + l;
}

uint32_t rand_other_than(const uint32_t l, const uint32_t r,
                         const uint32_t other) {
  const uint32_t num = rand(l, r - 1);
  return num + (num >= other);
}

template <typename T>
const T& rand_vec(const vector<T>& vec) {
  assert(vec.size() > 0);
  return vec[rand(0, vec.size())];
}

template <typename T>
void shuffle(vector<T>& vec) {
  rep(l, (int)vec.size() - 1) {
    const int idx = rand(l, vec.size());
    swap(vec[idx], vec[l]);
  }
}






class Timer {
  chrono::system_clock::time_point _start, _end;
  ll _sum = 0, _count = 0;

 public:
  void start() { _start = chrono::system_clock::now(); }

  void stop() { _end = chrono::system_clock::now(); }

  void add() {
    const chrono::system_clock::time_point now = chrono::system_clock::now();
    _sum += static_cast<double>(
        chrono::duration_cast<chrono::nanoseconds>(now - _start).count());
    _count++;
  }

  ll sum() const { return _sum / 1000; }

  int count() const { return _count; }

  string average() const {
    if (_count == 0) {
      return "NaN";
    }
    return to_string(_sum / 1000 / _count);
  }

  void reset() {
    _start = chrono::system_clock::now();
    _sum = 0;
    _count = 0;
  }

  inline int ms() const {
    const chrono::system_clock::time_point now = chrono::system_clock::now();
    return static_cast<double>(
        chrono::duration_cast<chrono::microseconds>(now - _start).count() /
        1000);
  }

  inline int ns() const {
    const chrono::system_clock::time_point now = chrono::system_clock::now();
    return static_cast<double>(
        chrono::duration_cast<chrono::microseconds>(now - _start).count());
  }
};

#ifdef LOCAL
struct Timers : unordered_map<string, Timer> {
  friend ostream& operator<<(ostream& os, const Timers& timers) {
    for (const auto& pa : timers) {
      os << pa.first << " time: " << pa.second.sum() / 1000
         << " count: " << pa.second.count() << endl;
    }
    return os;
  }
};
#else
struct Timers {
  struct Dummy {
    void start() const {}
    void add() const {}
  };
  Dummy dummy;
  const Dummy& operator[](const std::string& str) { return dummy; }
  friend ostream& operator<<(ostream& os, const Timers& timers) { return os; }
};
#endif

Timers global_timers;


// NBD = neighborhood
template <class Solution, class NBDGenerator>
struct SimulatedAnnealing {
 public:
  SimulatedAnnealing(double end_time, double start_temp, double end_temp)
      : end_time_(end_time),
        inv_time_(1.0 / end_time_),
        cur_time_(0.0),
        start_temp_(start_temp),
        end_temp_(end_temp),
        diff_temp_(end_temp - start_temp),
        cur_temp_(start_temp) {
    timer_.start();
  }

  Solution run(const Solution& initial_sol, NBDGenerator& nbd_generator) {
    Solution sol(initial_sol);

    int acc = 0;
    int g = 0;
    for (;; ++g) {
      // if (g % 10000 == 0) {
      //   cout << sol.Eval() << " " << sol.Score() << endl;
      //   cout << sol.Convert() << endl << endl;
      // }
      if ((g & 0xf) == 0) {
#ifdef SA_MAX_G
        if (g >= SA_MAX_G) {
          break;
        }
#endif
        UpdateTime();
        UpdateTemp();
        if (cur_time_ > end_time_) {
          break;
        }
      }

      // const auto prev_sol = sol;
      const auto nbd = nbd_generator.Generate(&sol, g);
      constexpr int mod = 1'000'000'000;
      const int r = rand(0, mod);
      if (static_cast<double>(r) / mod < exp(-nbd->Diff() / cur_temp_)) {
        acc++;
        nbd->Update(&sol);
      } else {
        // const auto mid_sol = sol;
        nbd->Restore(&sol);
        // if (prev_sol != sol) {
        //   for (const auto& obj : prev_sol.pos_pairs) {
        //     cerr << obj.Idx() << " ";
        //   }
        //   for (const auto& obj : mid_sol.pos_pairs) {
        //     cerr << obj.Idx() << " ";
        //   }
        //   for (const auto& obj : sol.pos_pairs) {
        //     cerr << obj.Idx() << " ";
        //   }
        //   abort();
        // }
      }
    }
    cerr << "g,acc: " << g << " " << acc << endl;
    return sol;
  }

 private:
  double end_time_, inv_time_, cur_time_;
  double start_temp_, end_temp_, diff_temp_, cur_temp_;
  Timer timer_;

  void UpdateTime() { cur_time_ = timer_.ms(); }
  void UpdateTemp() {
    cur_temp_ = max(0.0, start_temp_ - cur_time_ * diff_temp_ * inv_time_);
  }
};



enum Dir {
  // y-1, y+1, x-1, x+1
  kU,
  kD,
  kL,
  kR
};

struct Pos {
  int idx_;
  Pos() {}
  explicit Pos(const int _idx) : idx_(_idx) {}
  Pos(int _x, int _y) : idx_(_y * N + _x) { assert(N > 0); }
  int X() const { return pos_2_x[*this]; }
  int Y() const { return pos_2_y[*this]; }
  int Idx() const { return idx_; }
  operator int() const { return Idx(); }
  operator size_t() const { return Idx(); }
  const vector<Pos>& Adj() const { return adj_poses[*this]; }
  const vector<Dir>& AdjDirs() const { return adj_dirs[*this]; }
  int Manhattan(const Pos& other) const {
    return abs(X() - other.X()) + abs(Y() - other.Y());
  }
  bool Move(const Dir dir) {
    if (move_to[dir][*this].IsDummy()) {
      return false;
    } else {
      *this = move_to[dir][*this];
      return true;
    }
  }
  bool operator<(const Pos& other) const { return this->Idx() < other.Idx(); }
  bool operator==(const Pos& other) const { return this->Idx() == other.Idx(); }
  bool operator!=(const Pos& other) const { return this->Idx() != other.Idx(); }
  friend ostream& operator<<(ostream& os, const Pos& pos) {
    os << pos.X() << " " << pos.Y();
    return os;
  }
  bool IsDummy() const { return this->idx_ < 0; }
  static Pos Dummy() {
    Pos p;
    p.idx_ = -1;
    return p;
  }

  static Pos TryCreate(const int x, const int y, const int z) {
    if (y < 0 || y >= N || x < 0 || x >= N) {
      return Pos::Dummy();
    } else {
      return Pos(x, y);
    }
  }

  static void StaticInit(const int n) {
    N = n;
    N2 = N * N;
    N4 = N2 * N2;
    adj_poses = vector<vector<Pos>>(N2);
    adj_dirs = vector<vector<Dir>>(N2);
    move_to = vector<vector<Pos>>(4, vector<Pos>(N2, Pos::Dummy()));
    pos_2_y.resize(N2);
    pos_2_x.resize(N2);

    rep(y, N) {
      rep(x, N) {
        const Pos p{x, y};
        pos_2_y[p] = y;
        pos_2_x[p] = x;
        for (int dy = -1; dy <= 1; ++dy) {
          for (int dx = -1; dx <= 1; ++dx) {
            if (abs(dy) + abs(dx) != 1) continue;
            const int adj_y = y + dy;
            const int adj_x = x + dx;
            if (adj_y < 0 || adj_y >= N) continue;
            if (adj_x < 0 || adj_x >= N) continue;
            adj_poses[p].emplace_back(adj_x, adj_y);

            Dir dir;
            if (dy == -1) {
              dir = kU;
            } else if (dy == 1) {
              dir = kD;
            } else if (dx == -1) {
              dir = kL;
            } else if (dx == 1) {
              dir = kR;
            } else {
              assert(false);
            }

            move_to[dir][p] = {adj_x, adj_y};
            adj_dirs[p].emplace_back(dir);
          }
        }
      }
    }
  }
  static int N, N2, N4;
  static vector<vector<Pos>> adj_poses;
  static vector<vector<Dir>> adj_dirs;
  static vector<vector<Pos>> move_to;
  static vector<int> pos_2_x, pos_2_y;
};

vector<vector<Pos>> Pos::adj_poses;
vector<vector<Dir>> Pos::adj_dirs;
vector<vector<Pos>> Pos::move_to;
vector<int> Pos::pos_2_x, Pos::pos_2_y;
int Pos::N, Pos::N2, Pos::N4;












/* start */

template <typename Point, typename Dist>
class Graph_T {
 public:
  struct Edge {
    Point to;
    Dist dist;

    Edge(const Point _to, const Dist _dist) : to(_to), dist(_dist) {}
  };
  explicit Graph_T(const int n) : n_(n), adjs_(n) {}
  int N() const { return n_; }
  void AddEdge(const Point a, const Point b, const Dist dist) {
    adjs_[a].emplace_back(b, dist);
  }
  const vector<Edge>& Adj(const Point a) const { return adjs_[a]; }
  void RemoveEdge(const Point a, const Point b) {
    {
      const auto itr = std::find_if(
          all(adjs_[a]), [&](const Edge& edge) { return edge.to == b; });
      adjs_[a].erase(itr);
    }
  }

 private:
  int n_;
  vector<vector<Edge>> adjs_;
};

template <typename Point, typename Dist>
struct DijkstraData {
  Dist dist = 1e9;
  Point prev;
};

template <class Graph, typename Point, typename Dist>
vector<DijkstraData<Point, Dist>> Dijkstra(const Graph& graph,
                                           const Point& base_point) {
  vector<DijkstraData<Point, Dist>> datas(graph.N());
  using P = tuple<Dist, Point, Point>;
  priority_queue<P, vector<P>, greater<P>> pq;

  datas[base_point] = {0, base_point};
  pq.emplace(0, base_point, base_point);
  while (pq.size() > 0) {
    const auto [dist, point, prev_point] = pq.top();
    pq.pop();
    if (datas[point].dist < dist) continue;
    for (const auto& edge : graph.Adj(point)) {
      const Point to = edge.to;
      const Dist edge_dist = edge.dist;
      const Dist new_dist = dist + edge_dist;
      if (datas[to].dist > new_dist) {
        datas[to].dist = new_dist;
        datas[to].prev = point;
        pq.emplace(new_dist, to, point);
      }
    }
  }
  return datas;
}

template <typename Point, typename Dist>
vector<Point> Keiro(const vector<DijkstraData<Point, Dist>>& dijkstra_results,
                    const Point& from, const Point& to) {
  // 到達可能であることは仮定
  vector<Point> ret;
  Point p = to;
  while (p != from) {
    ret.emplace_back(p);
    p = dijkstra_results[p].prev;
  }

  ret.emplace_back(from);

  reverse(all(ret));
  return ret;
}

/* start */

struct Board {
  using Graph = Graph_T<Pos, float>;
  Board() {}
  Board(istream& is) {
    is >> N >> D >> H;
    Pos::StaticInit(N);
    rep(i, N) {
      string s;
      is >> s;
      S += s;
    }
    enemy_ds_.resize(Pos::N2);
    is >> M;
    rep(i, M) {
      int y, x, d;
      is >> y >> x >> d;
      Tanchiki tanchiki{Pos(x, y), d};
      tanchikies_.emplace_back(tanchiki);
      enemy_ds_[Pos(x, y)] = d;
    }

    rep(idx, Pos::N2) {
      const Pos p(idx);
      if (S[p] == 'S') {
        start_pos = p;
      } else if (S[p] == 'G') {
        goal_pos = p;
      } else if (S[p] == 'K') {
        key_pos = p;
      } else if (S[p] == 'J') {
        jewel_count++;
      }

      if (IsCheckPoint(p)) {
        check_points.emplace_back(p);
      }
    }

    InitBeamCount();
    InitDist();
  }

  void InitBeamCount() {
    pm2beams_.resize(Pos::N2, vector<int>(60));
    for (const auto& tanchiki : tanchikies_) {
      for (const auto dir : {kU, kD, kL, kR}) {
        Pos p = tanchiki.p;
        while (p.Move(dir) && CanMove(p)) {
          rep(t, 60) {
            if (t % tanchiki.d == 0) {
              pm2beams_[p][t]++;
            }
          }
        }
      }
    }
  }

  void InitDist() {
    Graph graph(Pos::N2);
    rep(idx1, Pos::N2) {
      const Pos p1(idx1);
      if (!CanMove(p1)) continue;
      int acc_p1 = std::accumulate(all(pm2beams_[p1]), 0);
      for (const auto& p2 : p1.Adj()) {
        if (!CanMove(p2)) continue;
        const float expected_hps =
            (acc_p1 + std::accumulate(all(pm2beams_[p2]), 0)) * D * 0.7 /
                120.0 +
            1.0;
        graph.AddEdge(p1, p2, expected_hps);
      }
    }

    dists_.resize(Pos::N2);
    keiros_.resize(Pos::N2);

    rep(idx1, Pos::N2) {
      const Pos p1(idx1);
      if (!IsCheckPoint(p1)) continue;
      dists_[idx1].resize(Pos::N2, INF);
      keiros_[idx1].resize(Pos::N2);

      const auto ret = Dijkstra<Graph, Pos, float>(graph, p1);
      rep(idx2, Pos::N2) {
        const Pos p2(idx2);
        if (!IsCheckPoint(p2)) continue;

        const auto& [dist, _] = ret[idx2];
        dists_[idx1][idx2] = dist;
        if (dist < INF * 0.1) {
          keiros_[idx1][idx2] = ::Keiro(ret, p1, p2);
        }
      }
    }
  }

  bool IsCheckPoint(const Pos& p) const {
    // TODO: Fも追加
    return S[p] == 'S' || S[p] == 'G' || S[p] == 'K' || S[p] == 'J';
  }

  int BeamCount(const Pos& p, const int t) const {
    return pm2beams_[p][t % 60];
  }

  bool CanMove(const Pos& p) const {
    return S[p] != '#' && S[p] != 'B' && S[p] != 'E';
  }

  bool IsEnemy(const Pos& p) const { return S[p] == 'E'; }

  bool IsFire(const Pos& p) const { return S[p] == 'F'; }

  bool IsDefaultEmpty(const Pos& p) const { return S[p] == '.' || S[p] == 'S'; }

  int GetEnemyD(const Pos& p) const {
    assert(IsEnemy(p));
    assert(enemy_ds_[p] > 0);
    return enemy_ds_[p];
  }

  float Dist(const Pos& p1, const Pos& p2) const { return dists_[p1][p2]; }

  const vector<Pos>& Keiro(const Pos& from, const Pos& to) const {
    return keiros_[from][to];
  }

  // 消費したHPを返す
  int Simulate(const vector<Pos>& poses, int t) const {
    // posesはSとGも含む
    int hp = (int)poses.size() - 1;
    reps(i, (int)poses.size() - 1) {
      const auto& p = poses[i];
      hp += pm2beams_[p][(t + i) % 60] * D;
    }
    return hp;
  }

  // 消費したHPをDPで最小化してから、返す
  pair<vector<Pos>, int> DPSimulate(const vector<Pos>& poses, int t,
                                    const int limit_hp) const {
    // posesはSとGも含む
    struct Data {
      int hp = INF;
      int prev_i;
      int prev_j;
    };
    // dp[i][j] : poses[i]の行動が終わっていて、t%60がj (次のt%60はj+1)
    vector<vector<Data>> dp(poses.size(), vector<Data>(60));
    dp[0][t % 60].hp = 0;
    rep(i, (int)poses.size() - 1) {
      const Pos& p = poses[i];
      const Pos& next_p = poses[i + 1];
      rep(_, 2) {
        // トーラスなので2週する
        rep(t, 60) {
          const int hp = dp[i][t].hp;
          const int next_time = (t + 1) % 60;

          // 移動する
          {
            auto& next_data = dp[i + 1][next_time];
            const int next_hp = hp + pm2beams_[next_p][next_time] * D + 1;
            if (next_hp < next_data.hp) {
              next_data.hp = next_hp;
              next_data.prev_i = i;
              next_data.prev_j = t;
            }
          }

          // その場にとどまる
          {
            auto& next_data = dp[i][next_time];
            const int next_hp = hp + pm2beams_[p][next_time] * D + 1;
            if (next_hp < next_data.hp) {
              next_data.hp = next_hp;
              next_data.prev_i = i;
              next_data.prev_j = t;
            }
          }
        }
      }
    }

    int best_hp = INF;
    int best_i = (int)dp.size() - 1;
    int best_j = 0;

    rep(t, 60) {
      if (dp[best_i][t].hp < best_hp) {
        best_hp = dp[best_i][t].hp;
        best_j = t;
      }
    }

    if (best_hp > limit_hp) {
      return {{}, INF};
    }

    vector<Pos> ret;
    ret.reserve(poses.size() * 2);
    int i = best_i, j = best_j;
    while (i != t % 60 || j != 0) {
      ret.emplace_back(poses[i]);
      const int prev_i = dp[i][j].prev_i;
      const int prev_j = dp[i][j].prev_j;
      i = prev_i;
      j = prev_j;
    }
    ret.emplace_back(poses[i]);
    reverse(all(ret));
    return {ret, best_hp};
  }

  // checkpointを削るDP
  vector<vector<Pos>> DPReduceCheckPoints(
      const vector<Pos>& original_poses) const {
    // dp[i][j] :
    // 現在original_poses[i]にいて、j個のposをskipしているなかで、消費HPの期待値の最小値
    struct Data {
      float hp = INF;
      int prev_i;
      int prev_j;
    };

    int key_idx = 0;
    rep(i, original_poses.size()) {
      if (key_pos == original_poses[i]) {
        key_idx = i;
        break;
      }
    }

    const int max_skip_count = 200;
    vector<vector<Data>> dp(original_poses.size(),
                            vector<Data>(max_skip_count + 1));
    dp[0][0].hp = 0;

    rep(i, (int)original_poses.size() - 1) {
      rep(j, max_skip_count) {
        const auto current_hp = dp[i][j].hp;
        for (int k = 1;
             i + k < (int)original_poses.size() && j + k - 1 <= max_skip_count;
             ++k) {
          const int next_i = i + k;

          if (i < key_idx && key_idx < next_i) {
            break;
          }

          const int next_j = j + k - 1;
          const float next_hp =
              Dist(original_poses[i], original_poses[next_i]) + current_hp;

          auto& next_dp = dp[next_i][next_j];
          if (next_hp < next_dp.hp) {
            next_dp.hp = next_hp;
            next_dp.prev_i = i;
            next_dp.prev_j = j;
          }
        }
      }
    }

    vector<vector<Pos>> ret;
    ret.reserve(max_skip_count + 1);

    rep(skip_count, max_skip_count + 1) {
      int i = (int)original_poses.size() - 1;
      int j = skip_count;
      ret.emplace_back();
      while (i != 0 || j != 0) {
        ret.back().emplace_back(original_poses[i]);
        const int prev_i = dp[i][j].prev_i;
        const int prev_j = dp[i][j].prev_j;
        i = prev_i;
        j = prev_j;
      }
      ret.back().emplace_back(original_poses[i]);
      reverse(all(ret.back()));
    }

    return ret;
  }

  static vector<Pos> Merge(const vector<vector<Pos>>& keiros) {
    assert(keiros.size() > 0);
    vector<Pos> ret;
    for (const auto& kerio : keiros) {
      assert(kerio.size() > 0);
      ret.insert(ret.end(), kerio.begin(),
                 kerio.begin() + ((int)kerio.size() - 1));
    }
    ret.emplace_back(keiros.back().back());
    return ret;
  }

  // public

  int N, D, H, M;
  string S;

  Pos start_pos, goal_pos, key_pos;
  int jewel_count = 0;

  // private
  struct Tanchiki {
    Pos p;
    int d;
  };
  vector<int> enemy_ds_;
  vector<vector<float>> dists_;
  vector<vector<vector<Pos>>> keiros_;
  vector<Tanchiki> tanchikies_;
  vector<Pos> check_points;

  // [pos][mod]
  vector<vector<int>> pm2beams_;
};

ostream& operator<<(ostream& os, const vector<Pos> keiro) {
  rep(i, (int)keiro.size() - 1) {
    const Pos from = keiro[i];
    const Pos to = keiro[i + 1];
    if (from == to) {
      os << "S";
    } else if (from.Y() - 1 == to.Y()) {
      os << "M U";
    } else if (from.Y() + 1 == to.Y()) {
      os << "M D";
    } else if (from.X() - 1 == to.X()) {
      os << "M L";
    } else if (from.X() + 1 == to.X()) {
      os << "M R";
    }
    if (i != (int)keiro.size() - 2) {
      os << "\n";
    }
  }
  return os;
}

/* start */

enum ActionKind { kStart, kStay, kMove, kPut, kFire };

struct Action {
  Pos p;
  ActionKind kind;
};

ostream& operator<<(ostream& os, const vector<Action>& actions) {
  assert(actions.size() > 0);
  Pos from = actions.front().p;
  reps(i, (int)actions.size() - 1) {
    const auto kind = actions[i].kind;
    const auto to = actions[i].p;
    assert(kind != kStart);
    if (kind == kStay) {
      os << "S";
    } else if (kind == kMove) {
      if (from.Y() - 1 == to.Y()) {
        os << "M U";
      } else if (from.Y() + 1 == to.Y()) {
        os << "M D";
      } else if (from.X() - 1 == to.X()) {
        os << "M L";
      } else if (from.X() + 1 == to.X()) {
        os << "M R";
      }
      from = to;
    } else if (kind == kPut) {
      if (from.Y() - 1 == to.Y()) {
        os << "B U";
      } else if (from.Y() + 1 == to.Y()) {
        os << "B D";
      } else if (from.X() - 1 == to.X()) {
        os << "B L";
      } else if (from.X() + 1 == to.X()) {
        os << "B R";
      } else {
        assert(false);
      }
    } else if (kind == kFire) {
      if (from.Y() > to.Y()) {
        os << "F U";
      } else if (from.Y() < to.Y()) {
        os << "F D";
      } else if (from.X() > to.X()) {
        os << "F L";
      } else if (from.X() < to.X()) {
        os << "F R";
      } else {
        assert(false);
      }
    }

    if (i != (int)actions.size() - 1) {
      os << "\n";
    }
  }
  return os;
}

struct BlockOptimizer {
  // keiroはS,Gも含む
  BlockOptimizer(Board* const board, const vector<Pos> keiro)
      : board_(board), keiro_(keiro) {}

  pair<vector<Action>, int> Run(const int limit_hp) const {
    struct Data {
      int hp = INF;
      // 今後のdamage期待値のdiff
      // 減少量　正の値
      float expected_damage_diff = 0;
      int prev_i = -1;
      int prev_j = -1;
      int fire_count = 0;
      Action prev_action;
      // block, 壁, enemyがあるならtrue
      bitset<3600> bs = 0;
      // 何もないならtrue
      bitset<3600> empty_bs = 0;
    };

    // 消費したHPをDPで最小化
    // Stay, Move, Put

    // 各マスを通る回数を事前計算
    vector<int> move_counts(Pos::N2, 0);
    for (const auto& p : keiro_) {
      move_counts[p]++;
    }

    auto calc_expected_damage = [&](const Pos& base_p, const bitset<3600>& bs) {
      float sum = 0.0;
      for (const auto dir : {kU, kD, kL, kR}) {
        Pos p = base_p;
        bool is_no_dummy = true;
        while ((is_no_dummy = p.Move(dir)) && !bs[p]) {
        }

        if (!is_no_dummy) continue;

        if (!board_->IsEnemy(p)) continue;

        const int d = board_->GetEnemyD(p);
        sum += 1.0 / d;
      }

      return sum * board_->D;
    };

    auto calc_true_damage = [&](const Pos& base_p, const int t,
                                const bitset<3600>& bs) {
      int sum = 0;
      for (const auto dir : {kU, kD, kL, kR}) {
        Pos p = base_p;
        bool is_no_dummy = true;
        while ((is_no_dummy = p.Move(dir)) && !bs[p]) {
        }

        if (!is_no_dummy) continue;

        if (!board_->IsEnemy(p)) continue;

        const int d = board_->GetEnemyD(p);
        sum += (t % d == 0);
      }

      return sum * board_->D;
    };

    auto calc_block_value = [&](const Pos& base_p, const bitset<3600>& bs) {
      assert(move_counts[base_p] == 0);
      float sum = 0.0;
      vector<int> move_count_sums(4);
      vector<int> enemy_ds(4);
      int idx = -1;
      for (const auto dir : {kU, kD, kL, kR}) {
        idx++;
        Pos p = base_p;
        bool is_no_dummy = true;
        while ((is_no_dummy = p.Move(dir)) && !bs[p]) {
          move_count_sums[idx] += move_counts[p];
        }

        if (!is_no_dummy) continue;

        if (!board_->IsEnemy(p)) continue;

        enemy_ds[idx] = board_->GetEnemyD(p);
      }

      rep(i, 4) {
        if (enemy_ds[i] == 0) continue;
        sum += move_count_sums[i / 2 * 2 + (1 - i % 2)] * 1.0 / enemy_ds[i];
      }
      return sum * board_->D;
    };

    auto calc_fire_value = [&](const Pos& human_p, const Dir fire_dir,
                               const bitset<3600>& bs) {
      Pos base_p;
      int d = 0;
      {
        Pos p = human_p;
        bool is_no_dummy = true;
        while ((is_no_dummy = p.Move(fire_dir)) && !bs[p]) {
        }

        if (!is_no_dummy) return std::make_pair(Pos::Dummy(), (float)(-INF));

        if (!board_->IsEnemy(p))
          return std::make_pair(Pos::Dummy(), (float)(-INF));

        d = board_->GetEnemyD(p);
        assert(d > 0);
        base_p = p;
      }

      assert(move_counts[base_p] == 0);
      vector<int> move_count_sums(4);
      vector<int> enemy_ds(4);
      int idx = -1;
      for (const auto dir : {kU, kD, kL, kR}) {
        idx++;
        Pos p = base_p;
        bool is_no_dummy = true;
        while ((is_no_dummy = p.Move(dir)) && !bs[p]) {
          move_count_sums[idx] += move_counts[p];
        }

        if (!is_no_dummy || !board_->IsEnemy(p)) {
          continue;
        }

        // その先に火炎放射がもう一つある
        enemy_ds[idx] = board_->GetEnemyD(p);
      }

      float sum = 0.0f;
      rep(i, 4) {
        sum += move_count_sums[i / 2 * 2 + (1 - i % 2)] * 1.0 / d;
        if (enemy_ds[i] == 0) {
          // i方向に火炎放射がない場合には、~iのhp減少が無になる
        } else {
          //ある場合には、~iのhp減少はその火炎放射の分だけ減る
          sum -= move_count_sums[i / 2 * 2 + (1 - i % 2)] * 1.0 / enemy_ds[i];
        }
      }
      return std::make_pair(base_p, sum * board_->D);
    };

    // dp[i][j] : poses[i]の行動が終わっていて、t%60がj (次のt%60はj+1)
    vector<vector<Data>> dp(keiro_.size(), vector<Data>(120));
    dp[0][0].hp = 0;
    dp[0][0].bs = 0;
    dp[0][0].empty_bs = 0;
    rep(idx, Pos::N2) {
      const Pos p(idx);
      dp[0][0].bs[p] = !board_->CanMove(p);
      dp[0][0].empty_bs[p] = board_->IsDefaultEmpty(p);
    }

    rep(i, (int)keiro_.size() - 1) {
      const auto p = keiro_[i];
      const auto next_p = keiro_[i + 1];
      move_counts[p]--;

      // dpの更新
      // トーラス
      rep(t, 120) {
        const auto& current_data = dp[i][t];
        const int hp = current_data.hp;
        const float expected_damage_diff = current_data.expected_damage_diff;

        // 移動する
        {
          const int next_time = (t + 1) % 60;
          auto& next_data = dp[i + 1][next_time];
          const int next_hp =
              hp + calc_true_damage(next_p, next_time, current_data.bs) + 1;
          // 次のマスのdamage期待値
          // TODO:高速化？
          const float next_expected_damage =
              calc_expected_damage(next_p, current_data.bs);
          const float next_expected_damage_diff =
              expected_damage_diff - next_expected_damage;
          if (next_hp - next_expected_damage_diff <
              next_data.hp - next_data.expected_damage_diff) {
            next_data.hp = next_hp;
            next_data.expected_damage_diff = next_expected_damage_diff;
            next_data.prev_i = i;
            next_data.prev_j = t;
            next_data.prev_action = Action{next_p, kMove};
            // TODO:高速化
            next_data.bs = current_data.bs;
            next_data.empty_bs = current_data.empty_bs;
            next_data.empty_bs[next_p] = true;
            next_data.fire_count =
                current_data.fire_count +
                (board_->IsFire(next_p) && !current_data.empty_bs[next_p]);
          }
        }

        // その場にとどまる
        {
          const int next_time = (t + 1) % 120;
          auto& next_data = dp[i][next_time];
          const int next_hp =
              hp + calc_true_damage(p, next_time, current_data.bs) + 1;
          if (next_hp - expected_damage_diff <
              next_data.hp - next_data.expected_damage_diff) {
            next_data.hp = next_hp;
            next_data.expected_damage_diff = expected_damage_diff;
            next_data.prev_i = i;
            next_data.prev_j = t;
            next_data.prev_action = Action{p, kStay};
            // TODO:高速化
            next_data.bs = current_data.bs;
            next_data.empty_bs = current_data.empty_bs;
            next_data.fire_count = current_data.fire_count;
          }
        }

        // ブロックを置く
        if (true) {
          const int next_time = (t + 1) % 120;
          auto& next_data = dp[i][next_time];
          for (const auto dir : {kU, kD, kL, kR}) {
            Pos to = p;
            if (!to.Move(dir)) continue;
            if (!current_data.empty_bs[to]) continue;
            if (current_data.bs[to]) continue;
            if (move_counts[to] > 0) continue;

            auto bs = current_data.bs;
            // hoge 入れ替えるとAC
            bs[to] = true;
            const int next_hp = hp + calc_true_damage(p, next_time, bs) + 1;
            // ブロックを置いた場合のdamage減少量の期待値
            assert(!to.IsDummy());
            assert(move_counts[to] == 0);
            const auto next_expected_damage_diff =
                calc_block_value(to, current_data.bs) +
                current_data.expected_damage_diff;

            if (next_hp - next_expected_damage_diff <
                next_data.hp - next_data.expected_damage_diff) {
              next_data.hp = next_hp;
              next_data.expected_damage_diff = next_expected_damage_diff;
              next_data.prev_i = i;
              next_data.prev_j = t;
              next_data.prev_action = Action{to, kPut};
              assert(to.Manhattan(p) == 1);
              // TODO:高速化
              next_data.bs = bs;
              next_data.empty_bs = current_data.empty_bs;
              // empty_bsはFire取得済みかどうかのflagに使う
              // next_data.empty_bs[to] = false;
              next_data.fire_count = current_data.fire_count;
            }
          }
        }

        // 火炎放射
        if (true && current_data.fire_count > 0) {
          const int next_time = (t + 1) % 120;
          auto& next_data = dp[i][next_time];
          for (const auto dir : {kU, kD, kL, kR}) {
            const auto [fire_pos, reduced_damage] =
                calc_fire_value(p, dir, current_data.bs);
            if (fire_pos.IsDummy()) continue;
            auto bs = current_data.bs;
            bs[fire_pos] = false;
            const int next_hp = hp + calc_true_damage(p, next_time, bs) + 1;
            // ブロックを置いた場合のdamage減少量の期待値
            const auto next_expected_damage_diff =
                reduced_damage + current_data.expected_damage_diff;

            if (next_hp - next_expected_damage_diff <
                next_data.hp - next_data.expected_damage_diff) {
              next_data.hp = next_hp;
              next_data.expected_damage_diff = next_expected_damage_diff;
              next_data.prev_i = i;
              next_data.prev_j = t;
              next_data.prev_action = Action{fire_pos, kFire};
              // TODO:高速化
              next_data.bs = bs;
              next_data.empty_bs = current_data.empty_bs;
              next_data.fire_count = current_data.fire_count - 1;
            }
          }
        }
      }
    }

    int best_hp = INF;
    int best_i = (int)dp.size() - 1;
    int best_j = 0;

    rep(t, 120) {
      if (dp[best_i][t].hp < best_hp) {
        best_hp = dp[best_i][t].hp;
        best_j = t;
      }
    }

    if (best_hp > limit_hp) {
      return {{}, INF};
    }

    vector<Action> ret;
    ret.reserve(keiro_.size() * 3);
    int i = best_i, j = best_j;
    while (true) {
      const int prev_i = dp[i][j].prev_i;
      const int prev_j = dp[i][j].prev_j;
      if (prev_i == -1) break;
      const auto prev_action = dp[i][j].prev_action;
      ret.emplace_back(prev_action);
      i = prev_i;
      j = prev_j;
    }
    ret.emplace_back(Action{keiro_.front(), kStart});
    reverse(all(ret));
    return {ret, best_hp};
  }

  Board* const board_;
  vector<Pos> keiro_;
};


/* start */

Board global_board;

struct Solution {
  vector<Pos> points;
  float hp = INF;
  bitset<3600> exists = 0;

  static Solution CreateGreedy(const Board& board) {
    Solution sol;
    sol.points.emplace_back(board.start_pos);

    set<Pos> S(all(board.check_points));
    S.erase(board.start_pos);
    S.erase(board.goal_pos);

    Pos p = board.start_pos;
    while (S.size() > 0) {
      const auto itr =
          std::min_element(all(S), [&](const auto& l, const auto& r) {
            return board.Dist(p, l) < board.Dist(p, r);
          });
      if (board.Dist(p, *itr) > INF * 0.1) {
        break;
      }

      p = *itr;
      sol.points.emplace_back(p);
      S.erase(itr);
    }

    sol.points.emplace_back(board.goal_pos);

    sol.hp = 0;
    rep(i, (int)sol.points.size()) {
      sol.exists[sol.points[i]] = true;
      if (i + 1 < (int)(sol.points.size())) {
        sol.hp += board.Dist(sol.points[i], sol.points[i + 1]);
      }
    }

    return sol;
  }

  float DiffSwap(const Board& board, int l, int r) const {
    assert(l < r);
    assert(0 < l);
    assert(r < (int)points.size());

    const float prev_dist = board.Dist(points[l - 1], points[l]) +
                            board.Dist(points[r - 1], points[r]);
    // TODO: 無向辺に直す
    const float next_dist = board.Dist(points[l - 1], points[r - 1]) +
                            board.Dist(points[l], points[r]);

    return next_dist - prev_dist;
  }

  void Swap(const Board& board, int l, int r) {
    hp += DiffSwap(board, l, r);
    reverse(points.begin() + l, points.begin() + r);
  }
};

struct NBD {
  float Diff() const { return diff_; }
  virtual void Update(Solution*) const = 0;
  void Restore(Solution*) const {}

  float diff_;
};

struct NBD_swap : public NBD {
  NBD_swap() {}
  NBD_swap(Solution* const sol, const int l, const int r) {
    l_ = l;
    r_ = r;
    diff_ = sol->DiffSwap(global_board, l, r);
  }
  void Update(Solution* sol) const override { sol->Swap(global_board, l_, r_); }

  int l_;
  int r_;
};

struct NBDGenerator {
  NBDGenerator() {}
  NBD* Generate(Solution* const sol, const int g) {
    // swap
    const int r = rand(2, sol->points.size());
    const int l = rand(1, r);
    nbd_swap0 = NBD_swap(sol, l, r);
    return &nbd_swap0;
  }

  NBD_swap nbd_swap0;
};

class Solver {
 public:
  explicit Solver(istream& is) : board_(is) { global_board = board_; }
  vector<Action> Solve(int time_limit) {
    Timer timer;
    timer.start();

    NBDGenerator nbd_generator;
    time_limit -= timer.ms();

    SimulatedAnnealing<Solution, NBDGenerator> sa(time_limit - 2000, 0.3, 0.1);
    Solution initial_sol = Solution::CreateGreedy(board_);
    auto best_sol = sa.run(initial_sol, nbd_generator);

    const auto skip_count2check_points =
        board_.DPReduceCheckPoints(best_sol.points);

    int best_skip_count = INF;
    vector<Pos> best_easy_actions;
    vector<Action> best_actions;
    rep(skip_count, skip_count2check_points.size()) {
      const auto& check_points = skip_count2check_points[skip_count];
      vector<vector<Pos>> keiros;
      rep(j, (int)check_points.size() - 1) {
        auto keiro = board_.Keiro(check_points[j], check_points[j + 1]);
        assert(keiro.size() > 0);
        keiros.emplace_back(std::move(keiro));
      }

      const auto ans_no_dp = Board::Merge(keiros);

      BlockOptimizer optimizer(&board_, ans_no_dp);
      const auto& [ans, hp] = board_.DPSimulate(ans_no_dp, 0, board_.H - 1);
      if (hp != INF) {
        assert(ans.size() > 0);
        best_skip_count = skip_count;
        best_easy_actions = ans;
        cerr << "Jewel Count: " << (int)check_points.size() - 3 << "/"
             << board_.jewel_count << endl;
        break;
      }
    }

    for (const int delta : {5, 1}) {
      for (int skip_count = best_skip_count - delta; skip_count >= 0;
           skip_count -= delta) {
        if (timer.ms() >= time_limit) break;
        const auto& check_points = skip_count2check_points[skip_count];
        vector<vector<Pos>> keiros;
        rep(j, (int)check_points.size() - 1) {
          auto keiro = board_.Keiro(check_points[j], check_points[j + 1]);
          assert(keiro.size() > 0);
          keiros.emplace_back(std::move(keiro));
        }

        const auto ans_no_dp = Board::Merge(keiros);

        BlockOptimizer optimizer(&board_, ans_no_dp);
        const auto& [ans, hp] = optimizer.Run(board_.H - 1);
        if (hp != INF) {
          assert(ans.size() > 0);
          best_skip_count = skip_count;
          best_actions = ans;
        } else if (delta != 1) {
          break;
        }
      }
    }

    if (best_actions.size() == 0) {
      cout << best_easy_actions << endl;
      std::quick_exit(0);
    }

    assert(best_skip_count != INF);

    cerr << "Jewel Count: "
         << (int)skip_count2check_points[best_skip_count].size() - 3 << "/"
         << board_.jewel_count << endl;

#ifndef LOCAL
    cout << best_actions << endl;
    std::quick_exit(0);
#endif

    return best_actions;
  }

 private:
  Board board_;
};

int main(int argc, char* argv[]) {
  fast_io;

  if (argc >= 2) {
    // int idx = 0;
    // for (int i = 1; i < argc; ++i) {
    //   PARAMS[idx++] = std::stod(argv[i]);
    // }
  }

  Timer timer;
  timer.start();
  Solver solver(cin);
  const auto ans = solver.Solve(2850 - timer.ms());
  cout << ans << endl;

  cerr << "ms: " << timer.ms() << endl;

  return 0;
}