#include using namespace std; using ll = long long; constexpr int N = 20; struct Graph { static constexpr ll INF = 1LL << 60; struct VertexQ { bool operator<(const VertexQ &o) const { return c > o.c; // 逆 } int i; ll c; }; struct Vertex { int n; int d; ll c; }; struct Edge { int i, n, c; }; Graph(int n, int m) : v(n, { -1, -1, INF }), e(m), n(n), m(0) {} void add_edge(int a, int b, int c) { e[m] = { b, v[a].n, c }; v[a].n = m; m++; } void dijkstra(int i, int j) { for (int i = 0; i < n; i++) v[i].c = INF; priority_queue q; q.push({ i, v[i].c = 0 }); while (!q.empty()) { auto p = q.top(); q.pop(); if (p.i == j) break; if (p.c > v[p.i].c) continue; for (int j = v[p.i].n; j >= 0; j = e[j].n) { Edge &o = e[j]; ll c = p.c + o.c; if (c < v[o.i].c) v[o.i].d = p.i, q.push({ o.i, v[o.i].c = c }); } } } vector v; vector e; int n, m; }; double c0[N][N]; double c1[N][N]; int main() { int h, w, p; cin >> h >> w >> p; for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { c0[i][j] = c1[i][j] = 0.2; } } while (1) { auto u = [&](double t) { t = t + (1 - t) * p / 100; t = 1 - t; t = -log(t) * 1e6; return (int)clamp(t, 0.0, 1e9); }; Graph g(N * N, N * N * 4); for (int i = 0; i < N; i++) { for (int j = 0; j < N - 1; j++) { int k = i * N + j; g.add_edge(k, k + 1, u(c0[i][j])); g.add_edge(k + 1, k, u(c0[i][j])); } } for (int i = 0; i < N - 1; i++) { for (int j = 0; j < N; j++) { int k = i * N + j; g.add_edge(k, k + N, u(c1[i][j])); g.add_edge(k + N, k, u(c1[i][j])); } } int k = N * N - 1; g.dijkstra(0, k); string s; vector t; t.push_back(k); while (1) { int k1 = g.v[k].d; int d = k - k1; char x; if (d == 1) x = 'R'; else if (d == -1) x = 'L'; else if (d == N) x = 'D'; else x = 'U'; s.push_back(x); t.push_back(k1); k = k1; if (k == 0) break; } reverse(s.begin(), s.end()); reverse(t.begin(), t.end()); cout << s << endl; int a; cin >> a; if (a == -1) break; auto f = [&](double &c, int y) { if (y == 0) { c = 0; } else { if (c > 0) c = c / ((1 - c) * p / 100 + c); } }; for (int b = 0; b <= a; b++) { int k0 = t[b], k1 = t[b + 1]; if (k0 > k1) swap(k0, k1); int i = k0 / N, j = k0 % N; if (abs(k0 - k1) == 1) { f(c0[i][j], b == a); } else { f(c1[i][j], b == a); } } //for (int i = 0; i < N; i++) { // for (int j = 0; j < N - 1; j++) { // cout << c0[i][j] << ' '; // } // cout << '\n'; //} //for (int i = 0; i < N - 1; i++) { // for (int j = 0; j < N; j++) { // cout << c1[i][j] << ' '; // } // cout << '\n'; //} } return 0; }