#include <bits/stdc++.h>
using namespace std;

struct DSU {
    vector<int> p, sz;
    explicit DSU(int n = 0) { init(n); }
    void init(int n) {
        p.resize(n);
        sz.assign(n, 1);
        iota(p.begin(), p.end(), 0);
    }
    int find(int x) {
        while (p[x] != x) {
            p[x] = p[p[x]];
            x = p[x];
        }
        return x;
    }
    bool unite(int a, int b) {
        a = find(a);
        b = find(b);
        if (a == b) return false;
        if (sz[a] < sz[b]) swap(a, b);
        p[b] = a;
        sz[a] += sz[b];
        return true;
    }
    bool same(int a, int b) { return find(a) == find(b); }
};

void push13(string &out, int value) {
    out.push_back(char(32 + (value % 95)));
    out.push_back(char(32 + (value / 95)));
}

int val95(char ch) {
    return int((unsigned char)ch) - 32;
}

struct MazeModel {
    int n, m, hcnt, ecnt;
    DSU dsu;
    vector<vector<pair<int, char>>> adj;

    explicit MazeModel(int n_)
        : n(n_), m((n + 1) / 2), hcnt(m * max(0, m - 1)),
          ecnt(2 * m * max(0, m - 1)), dsu(m * m), adj(m * m) {}

    pair<int, int> edge_rooms(int id) const {
        if (id < hcnt) {
            int r = id / (m - 1);
            int c = id % (m - 1);
            int a = r * m + c;
            return {a, a + 1};
        }
        int k = id - hcnt;
        int r = k / m;
        int c = k % m;
        int a = r * m + c;
        return {a, a + m};
    }

    pair<int, int> edge_cell(int id) const {
        if (id < hcnt) {
            int r = id / (m - 1);
            int c = id % (m - 1);
            return {2 * r + 1, 2 * c + 2};
        }
        int k = id - hcnt;
        int r = k / m;
        int c = k % m;
        return {2 * r + 2, 2 * c + 1};
    }

    void add_edge(int id) {
        if (id < 0 || id >= ecnt) return;
        auto [a, b] = edge_rooms(id);
        char ab = id < hcnt ? 'R' : 'D';
        char ba = id < hcnt ? 'L' : 'U';
        adj[a].push_back({b, ab});
        adj[b].push_back({a, ba});
        dsu.unite(a, b);
    }

    bool connected() { return dsu.same(0, m * m - 1); }

    string build_path() const {
        int total = m * m;
        vector<int> parent(total, -1);
        vector<char> move_to(total, 0);
        queue<int> q;
        q.push(0);
        parent[0] = 0;
        while (!q.empty()) {
            int v = q.front();
            q.pop();
            if (v == total - 1) break;
            for (auto [to, ch] : adj[v]) {
                if (parent[to] == -1) {
                    parent[to] = v;
                    move_to[to] = ch;
                    q.push(to);
                }
            }
        }
        string rooms;
        for (int cur = total - 1; cur != 0; cur = parent[cur]) rooms.push_back(move_to[cur]);
        reverse(rooms.begin(), rooms.end());
        string path;
        path.reserve(rooms.size() * 2);
        for (char ch : rooms) {
            path.push_back(ch);
            path.push_back(ch);
        }
        return path;
    }
};

vector<int> build_edge_order(const MazeModel &model, int agents) {
    vector<int> order(model.ecnt);
    iota(order.begin(), order.end(), 0);
    int hcnt = model.hcnt;
    int m = model.m;
    bool low_phased = model.n >= 101 && agents >= 14 && agents < 30;
    auto key = [&](int edge) {
        int rr2, cc2, orient;
        if (edge < hcnt) {
            int r = edge / (m - 1);
            int c = edge % (m - 1);
            rr2 = 2 * r;
            cc2 = 2 * c + 1;
            orient = 0;
        } else {
            int k = edge - hcnt;
            int r = k / m;
            int c = k % m;
            rr2 = 2 * r + 1;
            cc2 = 2 * c;
            orient = 1;
        }
        int ad = abs(rr2 - cc2);
        int sm = rr2 + cc2;
        if (agents == 7) {
            return tuple<int, int, int, int, int, int>(ad / 20, sm, ad, orient, edge, 0);
        }
        if (low_phased) {
            int q = (model.ecnt + agents - 1) / agents;
            if (agents == 17 || agents == 25) {
                return tuple<int, int, int, int, int, int>(ad, sm, ad, orient, edge, 0);
            }
            int bucket = agents == 28 ? ((q >= 130 && q <= 800) ? 32 : 60)
                                      : (agents == 19 ? 40 : 80);
            return tuple<int, int, int, int, int, int>(ad / bucket, sm, ad, orient, edge, 0);
        }
        return tuple<int, int, int, int, int, int>(ad, sm, orient, edge, 0, 0);
    };
    sort(order.begin(), order.end(), [&](int a, int b) { return key(a) < key(b); });
    return order;
}

string ask_line(const string &cmd) {
    cout << cmd << '\n' << flush;
    string reply;
    if (!getline(cin, reply)) exit(0);
    return reply;
}

void send_to_zero(const string &body) {
    string reply = ask_line("> 0 " + body);
    (void)reply;
}

void send_to_zero_no_wait(const string &body) {
    cout << "> 0 " << body << '\n' << flush;
}

string pack_bits(const vector<unsigned char> &bits) {
    string packed;
    int bit_pos = 0;
    int cur = 0;
    for (unsigned char bit : bits) {
        if (bit) cur |= 1 << (bit_pos % 13);
        ++bit_pos;
        if (bit_pos % 13 == 0) {
            push13(packed, cur);
            cur = 0;
        }
    }
    if (bit_pos % 13 != 0) push13(packed, cur);
    return packed;
}

int slice_len(int ecnt, int agents, int sender) {
    if (sender >= ecnt) return 0;
    return (ecnt + agents - 1 - sender) / agents;
}

int phased_block_size(int ecnt, int agents, int max_msg_len) {
    int q = (ecnt + agents - 1) / agents;
    int b;
    if (q >= 130 && q <= 800) {
        b = max(1, (q * 80 + 99) / 100);
        if (agents == 28) b = 272;
        if (agents == 25) b = 384;
    } else {
        int by_q = q / 2;
        int floor_b = agents <= 32 ? 550 : 650;
        if (agents >= 4 && agents < 14) {
            static const int tiny_blocks[14] = {
                0, 0, 0, 0, 512, 256, 256, 256, 1024, 256, 256, 1024, 512, 256};
            b = tiny_blocks[agents];
        } else if (agents >= 14 && agents < 30) {
            b = agents == 28 ? 512 : (agents == 20 ? 256 : (agents == 29 ? 1536 : 896));
            if (agents == 17) b = 1024;
        } else if (agents >= 33 && agents <= 36) {
            b = 600;
        } else if (agents == 48 && q >= 900 && q <= 1350) {
            b = 896;
        } else if (q >= 1800 && q <= 2500 && agents >= 40) {
            b = agents <= 45 ? 1360 : 1500;
        } else {
            b = min(1100, max(floor_b, by_q));
        }
        if (agents == 42 && q == 1535) b = 1360;
        if (agents == 45 && q > 2500) b = 1792;
    }
    int max_bits = max(13, (max_msg_len / 2) * 13);
    b = min(b, max_bits);
    return max(1, min(q, b));
}

void worker(int n, int agents, int id, int max_msg_len, const vector<int> &order) {
    MazeModel model(n);
    string packed;
    int bit_pos = 0;
    int cur = 0;
    for (int pos = id; pos < model.ecnt; pos += agents) {
        int edge = order[pos];
        auto [r, c] = model.edge_cell(edge);
        string reply = ask_line("? " + to_string(r) + " " + to_string(c));
        if (!reply.empty() && reply[0] == '1') cur |= 1 << (bit_pos % 13);
        ++bit_pos;
        if (bit_pos % 13 == 0) {
            push13(packed, cur);
            cur = 0;
        }
    }
    if (bit_pos % 13 != 0) push13(packed, cur);

    int chunk = max(2, (max_msg_len / 2) * 2);
    for (int pos = 0; pos < (int)packed.size(); pos += chunk) {
        string body = packed.substr(pos, chunk);
        if (pos + chunk >= (int)packed.size()) {
            send_to_zero_no_wait(body);
        } else {
            send_to_zero(body);
        }
    }
}

void worker_phased(int n, int agents, int id, int max_msg_len, const vector<int> &order, int block) {
    MazeModel model(n);
    int total = slice_len(model.ecnt, agents, id);
    for (int start = 0; start < total; start += block) {
        int take = min(block, total - start);
        vector<unsigned char> bits;
        bits.reserve(take);
        for (int off = 0; off < take; ++off) {
            int logical = id + (start + off) * agents;
            int edge = order[logical];
            auto [r, c] = model.edge_cell(edge);
            string reply = ask_line("? " + to_string(r) + " " + to_string(c));
            bits.push_back((!reply.empty() && reply[0] == '1') ? 1 : 0);
        }
        string body = pack_bits(bits);
        if (start + take >= total) send_to_zero_no_wait(body);
        else send_to_zero(body);
    }
}

void coordinator(int n, int agents, int id, int max_msg_len, const vector<int> &order) {
    MazeModel model(n);
    vector<int> bit_index(agents, 0);
    vector<int> chunks_left(agents, 0);
    int pending_chunks = 0;
    int chunk = max(2, (max_msg_len / 2) * 2);
    for (int sender = 1; sender < agents; ++sender) {
        int q = (model.ecnt + agents - 1 - sender) / agents;
        int chars = 2 * ((q + 12) / 13);
        chunks_left[sender] = (chars + chunk - 1) / chunk;
        pending_chunks += chunks_left[sender];
    }

    auto claim_if_ready = [&]() -> bool {
        if (!model.connected()) return false;
        cout << "! " << model.build_path() << '\n' << flush;
        return true;
    };

    if (n == 1) {
        cout << "! " << '\n' << flush;
        return;
    }

    for (int pos = id; pos < model.ecnt; pos += agents) {
        int edge = order[pos];
        auto [r, c] = model.edge_cell(edge);
        string reply = ask_line("? " + to_string(r) + " " + to_string(c));
        if (!reply.empty() && reply[0] == '1') {
            model.add_edge(edge);
            if (claim_if_ready()) return;
        }
    }

    while (pending_chunks > 0) {
        string reply = ask_line("< ?");
        if (reply == "- -") continue;
        size_t sp = reply.find(' ');
        if (sp == string::npos) continue;
        int sender = stoi(reply.substr(0, sp));
        string body = reply.substr(sp + 1);
        if (sender <= 0 || sender >= agents || chunks_left[sender] <= 0) continue;
        --chunks_left[sender];
        --pending_chunks;
        for (int pos = 0; pos + 1 < (int)body.size(); pos += 2) {
            int bits = val95(body[pos]) + 95 * val95(body[pos + 1]);
            for (int b = 0; b < 13; ++b) {
                int logical = sender + bit_index[sender] * agents;
                int edge = logical < model.ecnt ? order[logical] : model.ecnt;
                ++bit_index[sender];
                if (edge >= model.ecnt) continue;
                if (bits & (1 << b)) model.add_edge(edge);
            }
        }
        if (claim_if_ready()) return;
    }

    if (claim_if_ready()) return;
    while (true) ask_line(".");
}

void coordinator_phased(int n, int agents, int id, int max_msg_len, const vector<int> &order, int block) {
    MazeModel model(n);
    vector<int> chunk_seen(agents, 0);

    auto claim_if_ready = [&]() -> bool {
        if (!model.connected()) return false;
        cout << "! " << model.build_path() << '\n' << flush;
        return true;
    };

    if (n == 1) {
        cout << "! " << '\n' << flush;
        return;
    }

    int my_total = slice_len(model.ecnt, agents, 0);
    int max_blocks = 0;
    for (int sender = 1; sender < agents; ++sender) {
        int q = slice_len(model.ecnt, agents, sender);
        max_blocks = max(max_blocks, (q + block - 1) / block);
    }
    max_blocks = max(max_blocks, (my_total + block - 1) / block);

    for (int blk = 0; blk < max_blocks; ++blk) {
        int start = blk * block;
        int take = min(block, max(0, my_total - start));
        for (int off = 0; off < take; ++off) {
            int logical = (start + off) * agents;
            int edge = order[logical];
            auto [r, c] = model.edge_cell(edge);
            string reply = ask_line("? " + to_string(r) + " " + to_string(c));
            if (!reply.empty() && reply[0] == '1') {
                model.add_edge(edge);
                if (claim_if_ready()) return;
            }
        }

        int pending = 0;
        for (int sender = 1; sender < agents; ++sender) {
            if (blk * block < slice_len(model.ecnt, agents, sender)) ++pending;
        }
        while (pending > 0) {
            string reply = ask_line("< ?");
            if (reply == "- -") continue;
            size_t sp = reply.find(' ');
            if (sp == string::npos) continue;
            int sender = stoi(reply.substr(0, sp));
            if (sender <= 0 || sender >= agents) continue;
            int msg_block = chunk_seen[sender]++;
            if (msg_block != blk) {
                // B is large enough that this should not happen, but keep decoding
                // by the actual sender sequence if scheduling ever gets ahead.
            }
            --pending;
            string body = reply.substr(sp + 1);
            int base = msg_block * block;
            int local = 0;
            for (int pos = 0; pos + 1 < (int)body.size(); pos += 2) {
                int bits = val95(body[pos]) + 95 * val95(body[pos + 1]);
                for (int b = 0; b < 13; ++b) {
                    int idx = base + local++;
                    if (idx >= slice_len(model.ecnt, agents, sender)) continue;
                    int logical = sender + idx * agents;
                    int edge = order[logical];
                    if (bits & (1 << b)) model.add_edge(edge);
                }
            }
            if (claim_if_ready()) return;
        }
    }

    if (claim_if_ready()) return;
    while (true) ask_line(".");
}

struct RaceDir {
    int dr, dc;
    char ch;
};

uint64_t splitmix64(uint64_t x) {
    x += 0x9e3779b97f4a7c15ULL;
    x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9ULL;
    x = (x ^ (x >> 27)) * 0x94d049bb133111ebULL;
    return x ^ (x >> 31);
}

vector<RaceDir> race_ordered_dirs(int r, int c, int m, int id) {
    static const array<RaceDir, 4> base = {
        {{1, 0, 'D'}, {0, 1, 'R'}, {-1, 0, 'U'}, {0, -1, 'L'}}};
    vector<pair<int, RaceDir>> scored;
    scored.reserve(4);

    int variant = id % 16;
    for (int i = 0; i < 4; ++i) {
        RaceDir d = base[i];
        int nr = r + d.dr;
        int nc = c + d.dc;
        if (nr < 0 || nr >= m || nc < 0 || nc >= m) continue;
        int dist = (m - 1 - nr) + (m - 1 - nc);
        int tie = i;
        if (variant == 1) tie = (d.ch == 'R' ? 0 : d.ch == 'D' ? 1 : d.ch == 'L' ? 2 : 3);
        else if (variant == 2) tie = (d.ch == 'D' ? 0 : d.ch == 'R' ? 1 : d.ch == 'L' ? 2 : 3);
        else if (variant == 3) tie = (d.ch == 'R' ? 0 : d.ch == 'D' ? 1 : d.ch == 'U' ? 2 : 3);
        else if (variant == 4) tie = (d.ch == 'D' ? 0 : d.ch == 'L' ? 1 : d.ch == 'R' ? 2 : 3);
        else if (variant == 5) tie = (d.ch == 'R' ? 0 : d.ch == 'U' ? 1 : d.ch == 'D' ? 2 : 3);

        int key;
        if (variant < 6) {
            key = dist * 16 + tie;
        } else {
            int bias = (variant < 10) ? 96 : (variant < 13 ? 48 : 16);
            uint64_t h = splitmix64(((uint64_t)id << 42) ^ ((uint64_t)r << 21) ^
                                    (uint64_t)c ^ ((uint64_t)i << 58));
            int noise = (int)(h % 256);
            key = dist * bias + noise;
        }
        scored.push_back({key, d});
    }
    sort(scored.begin(), scored.end(), [](const auto &a, const auto &b) {
        if (a.first != b.first) return a.first < b.first;
        return a.second.ch < b.second.ch;
    });
    vector<RaceDir> out;
    out.reserve(scored.size());
    for (auto &x : scored) out.push_back(x.second);
    return out;
}

bool race_query_edge(int room_r, int room_c, const RaceDir &d) {
    int cr = 2 * room_r + 1 + d.dr;
    int cc = 2 * room_c + 1 + d.dc;
    string reply = ask_line("? " + to_string(cr) + " " + to_string(cc));
    return !reply.empty() && reply[0] == '1';
}

string race_find_path_dfs(int n, int id) {
    int m = (n + 1) / 2;
    vector<unsigned char> seen(m * m, 0);
    vector<int> next_idx(m * m, 0);
    vector<vector<RaceDir>> orders(m * m);
    vector<pair<int, int>> st;
    string room_path;

    auto idx = [m](int r, int c) { return r * m + c; };
    st.push_back({0, 0});
    seen[0] = 1;

    while (!st.empty()) {
        auto [r, c] = st.back();
        if (r == m - 1 && c == m - 1) {
            string path;
            path.reserve(room_path.size() * 2);
            for (char ch : room_path) {
                path.push_back(ch);
                path.push_back(ch);
            }
            return path;
        }

        int v = idx(r, c);
        if (orders[v].empty()) orders[v] = race_ordered_dirs(r, c, m, id);

        bool advanced = false;
        while (next_idx[v] < (int)orders[v].size()) {
            RaceDir d = orders[v][next_idx[v]++];
            int nr = r + d.dr;
            int nc = c + d.dc;
            int u = idx(nr, nc);
            if (seen[u]) continue;
            if (!race_query_edge(r, c, d)) continue;
            seen[u] = 1;
            st.push_back({nr, nc});
            room_path.push_back(d.ch);
            advanced = true;
            break;
        }

        if (!advanced) {
            st.pop_back();
            if (!room_path.empty()) room_path.pop_back();
        }
    }
    return "";
}

struct RaceStepper {
    int n, m, id;
    vector<unsigned char> seen;
    vector<int> next_idx;
    vector<vector<RaceDir>> orders;
    vector<pair<int, int>> st;
    string room_path;
    string final_path;
    bool finished = false;

    RaceStepper(int n_, int id_)
        : n(n_), m((n + 1) / 2), id(id_), seen(m * m, 0), next_idx(m * m, 0),
          orders(m * m) {
        st.push_back({0, 0});
        seen[0] = 1;
    }

    int idx(int r, int c) const { return r * m + c; }

    bool finish_if_goal(int r, int c) {
        if (r != m - 1 || c != m - 1) return false;
        final_path.clear();
        final_path.reserve(room_path.size() * 2);
        for (char ch : room_path) {
            final_path.push_back(ch);
            final_path.push_back(ch);
        }
        finished = true;
        return true;
    }

    bool step() {
        if (finished) return true;
        while (!st.empty()) {
            auto [r, c] = st.back();
            if (finish_if_goal(r, c)) return true;

            int v = idx(r, c);
            if (orders[v].empty()) orders[v] = race_ordered_dirs(r, c, m, id);

            while (next_idx[v] < (int)orders[v].size()) {
                RaceDir d = orders[v][next_idx[v]++];
                int nr = r + d.dr;
                int nc = c + d.dc;
                int u = idx(nr, nc);
                if (seen[u]) continue;
                bool open = race_query_edge(r, c, d);
                if (open) {
                    seen[u] = 1;
                    st.push_back({nr, nc});
                    room_path.push_back(d.ch);
                    finish_if_goal(nr, nc);
                }
                return finished;
            }

            st.pop_back();
            if (!room_path.empty()) room_path.pop_back();
        }
        finished = true;
        final_path.clear();
        return true;
    }
};

void race_send_path_to_zero(const string &path, int max_msg_len) {
    int chunk = max(1, max_msg_len - 1);
    for (int pos = 0; pos < (int)path.size(); pos += chunk) {
        int take = min(chunk, (int)path.size() - pos);
        bool last = pos + take == (int)path.size();
        string body;
        body.reserve(1 + take);
        body.push_back(last ? 'Z' : 'P');
        body.append(path, pos, take);
        string reply = ask_line("> 0 " + body);
        (void)reply;
    }
    if (path.empty()) {
        string reply = ask_line("> 0 Z");
        (void)reply;
    }
    cout << "halt" << '\n' << flush;
}

void race_coordinator(int n) {
    if (n == 1) {
        cout << "! " << '\n' << flush;
        return;
    }

    if (n >= 351) {
        constexpr int poll_interval = 128;
        RaceStepper stepper(n, 0);
        int since_poll = 0;
        int step_locked_sender = -1;
        string step_path;
        auto consume_step_msg = [&](const string &reply) -> bool {
            if (reply == "- -") return false;
            size_t sp = reply.find(' ');
            if (sp == string::npos) return false;
            int sender = stoi(reply.substr(0, sp));
            string body = reply.substr(sp + 1);
            if (body.empty() || (body[0] != 'P' && body[0] != 'Z')) return false;
            if (step_locked_sender < 0) {
                step_locked_sender = sender;
                step_path.clear();
            }
            if (sender != step_locked_sender) return false;
            step_path.append(body.begin() + 1, body.end());
            if (body[0] == 'Z') {
                cout << "! " << step_path << '\n' << flush;
                return true;
            }
            return false;
        };

        while (true) {
            if (step_locked_sender >= 0) {
                if (consume_step_msg(ask_line("< " + to_string(step_locked_sender)))) return;
                continue;
            }
            if (stepper.step()) {
                cout << "! " << stepper.final_path << '\n' << flush;
                return;
            }
            ++since_poll;
            if (since_poll >= poll_interval) {
                since_poll = 0;
                if (consume_step_msg(ask_line("< ?"))) return;
            }
        }
    }

    int locked_sender = -1;
    string path;
    while (true) {
        string cmd = locked_sender < 0 ? "< ?" : "< " + to_string(locked_sender);
        string reply = ask_line(cmd);
        if (reply == "- -") continue;
        size_t sp = reply.find(' ');
        if (sp == string::npos) continue;
        int sender = stoi(reply.substr(0, sp));
        string body = reply.substr(sp + 1);
        if (body.empty() || (body[0] != 'P' && body[0] != 'Z')) continue;
        if (locked_sender < 0) {
            locked_sender = sender;
            path.clear();
        }
        if (sender != locked_sender) continue;
        path.append(body.begin() + 1, body.end());
        if (body[0] == 'Z') {
            cout << "! " << path << '\n' << flush;
            return;
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, agents, id, max_msg_len;
    if (!(cin >> n >> agents >> id >> max_msg_len)) return 0;
    string rest;
    getline(cin, rest);

    if (agents < 4) {
        if (id == 0) race_coordinator(n);
        else race_send_path_to_zero(race_find_path_dfs(n, id), max_msg_len);
        return 0;
    }

    MazeModel tmp(n);
    vector<int> order = build_edge_order(tmp, agents);
    bool phased = agents >= 4 && n >= 101;
    int block = phased_block_size(tmp.ecnt, agents, max_msg_len);
    if (phased) {
        if (id == 0) coordinator_phased(n, agents, id, max_msg_len, order, block);
        else worker_phased(n, agents, id, max_msg_len, order, block);
    } else {
        if (id == 0) coordinator(n, agents, id, max_msg_len, order);
        else worker(n, agents, id, max_msg_len, order);
    }
    return 0;
}