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

// Datacenter Imprisonment - apex-final hybrid agent.
//
// Main assumptions for finals: odd-grid perfect maze, room cells at odd/odd 1-indexed
// positions and corridor cells between rooms.  The safe scan mode queries room edges only.
// Low-agent large cases use a bidirectional trace search.  This version additionally uses
// 13-bit / 2-printable-char packing (base94, no tag bytes) and can choose a receiver-only
// streaming scan when communication is the bottleneck.

static int N, NUM_AGENTS, AGENT_ID, MAX_MSG_LEN;
static long long TOTAL_CELLS;
static int RM;
static long long ROOMS, H_EDGES, EDGE_COUNT;
static int PAYLOAD;
static int ACTIVE_AGENTS = 0;

[[noreturn]] static void quit_now() { exit(0); }

static string transact(const string &cmd) {
    cout << cmd << '\n' << flush;
    string reply;
    if (!getline(cin, reply)) quit_now();
    return reply;
}
static void send_msg(int to, const string &body) {
    (void)transact("> " + to_string(to) + " " + body);
}
static bool ask_cell_1idx(int r, int c) {
    string rep = transact("? " + to_string(r) + " " + to_string(c));
    return !rep.empty() && rep[0] == '1';
}
[[noreturn]] static void claim_path(const string &path) {
    cout << "! " << path << '\n' << flush;
    quit_now();
}
[[noreturn]] static void halt_agent() {
    cout << "halt\n" << flush;
    quit_now();
}

// Printable non-space alphabet: chars 33..126, base 94.  Since 94^2 > 2^13,
// each full pair stores 13 bits.  This is denser than base64 and keeps parsing simple.
static inline char enc94(int v) { return char(33 + v); }
static inline int dec94(char ch) {
    int v = (int)(unsigned char)ch - 33;
    return (0 <= v && v < 94) ? v : 0;
}
static inline long long encoded_len_for_bits(long long bits) {
    if (bits <= 0) return 0;
    long long q = bits / 13, r = bits % 13;
    return 2 * q + (r == 0 ? 0 : (r <= 6 ? 1 : 2));
}
static inline long long chunks_for_chars(long long chars) {
    if (chars <= 0) return 0;
    if (PAYLOAD <= 0) return (long long)4e18;
    return (chars + PAYLOAD - 1) / PAYLOAD;
}
static inline long long chunks_for_bits(long long bits) {
    return chunks_for_chars(encoded_len_for_bits(bits));
}

struct BitPacker {
    string s;
    int acc = 0, cnt = 0, bits = 0;
    void emit_pair(int v) {
        s.push_back(enc94(v % 94));
        s.push_back(enc94(v / 94));
    }
    void add(bool bit) {
        if (bit) acc |= (1 << cnt);
        ++bits;
        if (++cnt == 13) {
            emit_pair(acc);
            acc = 0;
            cnt = 0;
        }
    }
    string finish() {
        if (cnt) {
            if (cnt <= 6) s.push_back(enc94(acc));
            else emit_pair(acc);
        }
        string out = s;
        s.clear(); acc = cnt = bits = 0;
        return out;
    }
};

template<class F>
static void decode_bits_known(const string &enc, long long bit_count, F &&fn) {
    size_t pos = 0;
    long long done = 0;
    while (done < bit_count) {
        long long rem = bit_count - done;
        int take, v;
        if (rem >= 13) {
            v = dec94(pos < enc.size() ? enc[pos] : '!') + 94 * dec94(pos + 1 < enc.size() ? enc[pos + 1] : '!');
            pos += 2; take = 13;
        } else if (rem <= 6) {
            v = dec94(pos < enc.size() ? enc[pos] : '!');
            pos += 1; take = (int)rem;
        } else {
            v = dec94(pos < enc.size() ? enc[pos] : '!') + 94 * dec94(pos + 1 < enc.size() ? enc[pos + 1] : '!');
            pos += 2; take = (int)rem;
        }
        for (int b = 0; b < take; ++b) fn(((v >> b) & 1) != 0);
        done += take;
    }
}

template<class F>
static void decode_bits_full_pairs(const string &enc, F &&fn) {
    // Active traces are flushed only on 13-bit boundaries, so every message has an even length.
    size_t pos = 0;
    while (pos + 1 < enc.size()) {
        int v = dec94(enc[pos]) + 94 * dec94(enc[pos + 1]);
        pos += 2;
        for (int b = 0; b < 13; ++b) fn(((v >> b) & 1) != 0);
    }
}

static inline long long part_count(long long total, int parts, int id) {
    if (id < 0 || id >= parts || id >= total) return 0;
    return (total - 1 - id) / parts + 1;
}

static bool parse_any_message(const string &line, int &sender, string &body) {
    if (line == "- -") return false;
    size_t sp = line.find(' ');
    if (sp == string::npos || sp == 0) return false;
    int x = 0;
    for (size_t i = 0; i < sp; ++i) {
        if (!isdigit((unsigned char)line[i])) return false;
        x = x * 10 + (line[i] - '0');
    }
    sender = x;
    body = line.substr(sp + 1);
    return true;
}
static bool parse_message_from_zero(const string &line, string &body) {
    int sender = -1;
    if (!parse_any_message(line, sender, body)) return false;
    return sender == 0;
}

static void send_chunks_raw(int to, const string &enc) {
    if (PAYLOAD <= 0) halt_agent();
    for (size_t pos = 0; pos < enc.size(); pos += (size_t)PAYLOAD) {
        send_msg(to, enc.substr(pos, min<size_t>((size_t)PAYLOAD, enc.size() - pos)));
    }
}

// ---------------- Room-edge scan ----------------

static inline void edge_cell_1idx(long long ord, int &r, int &c) {
    if (ord < H_EDGES) {
        long long rr = ord / (RM - 1);
        long long cc = ord % (RM - 1);
        r = (int)(2 * rr + 1);
        c = (int)(2 * cc + 2);
    } else {
        long long t = ord - H_EDGES;
        long long rr = t / RM;
        long long cc = t % RM;
        r = (int)(2 * rr + 2);
        c = (int)(2 * cc + 1);
    }
}
static inline bool ask_edge_ord(long long ord) {
    int r, c; edge_cell_1idx(ord, r, c);
    return ask_cell_1idx(r, c);
}
static inline long long horiz_ord(int rr, int cc) { return 1LL * rr * (RM - 1) + cc; }
static inline long long vert_ord(int rr, int cc) { return H_EDGES + 1LL * rr * RM + cc; }

static string pack_edge_partition(int parts, int id, vector<unsigned char> *open_edges) {
    BitPacker bp;
    for (long long ord = id; ord < EDGE_COUNT; ord += parts) {
        bool open = ask_edge_ord(ord);
        if (open_edges) (*open_edges)[ord] = (unsigned char)open;
        else bp.add(open);
    }
    return open_edges ? string() : bp.finish();
}
static void decode_edge_partition(const string &enc, int parts, int id, vector<unsigned char> &open_edges) {
    long long bit = 0;
    decode_bits_known(enc, part_count(EDGE_COUNT, parts, id), [&](bool one) {
        long long ord = id + bit * parts;
        if (ord < EDGE_COUNT) open_edges[(size_t)ord] = (unsigned char)one;
        ++bit;
    });
}

static string solve_room_graph(const vector<unsigned char> &open_edges) {
    if (ROOMS == 1) return "";
    vector<int> parent((size_t)ROOMS, -1);
    queue<int> q;
    parent[0] = -2; q.push(0);
    while (!q.empty() && parent[(size_t)ROOMS - 1] == -1) {
        int u = q.front(); q.pop();
        int r = u / RM, c = u % RM;
        auto push = [&](int v, long long ord) {
            if (open_edges[(size_t)ord] && parent[v] == -1) {
                parent[v] = u; q.push(v);
            }
        };
        if (c + 1 < RM) push(u + 1, horiz_ord(r, c));
        if (c > 0)      push(u - 1, horiz_ord(r, c - 1));
        if (r + 1 < RM) push(u + RM, vert_ord(r, c));
        if (r > 0)      push(u - RM, vert_ord(r - 1, c));
    }
    if (parent[(size_t)ROOMS - 1] == -1) return string();
    string rp;
    for (int cur = (int)ROOMS - 1; cur != 0; cur = parent[cur]) {
        int p = parent[cur];
        if (cur == p + 1) rp.push_back('R');
        else if (cur == p - 1) rp.push_back('L');
        else if (cur == p + RM) rp.push_back('D');
        else if (cur == p - RM) rp.push_back('U');
        else return string();
    }
    reverse(rp.begin(), rp.end());
    string ans; ans.reserve(rp.size() * 2);
    for (char ch : rp) { ans.push_back(ch); ans.push_back(ch); }
    return ans;
}

// Rare generic full-grid fallback.  Not part of the fast finals path.
static inline bool forced_open_cell(long long idx) { return idx == 0 || idx == TOTAL_CELLS - 1; }
static string pack_full_partition(int parts, int id, vector<unsigned char> *grid) {
    BitPacker bp;
    for (long long idx = id; idx < TOTAL_CELLS; idx += parts) {
        bool open = forced_open_cell(idx) ? true : ask_cell_1idx((int)(idx / N) + 1, (int)(idx % N) + 1);
        if (grid) (*grid)[(size_t)idx] = (unsigned char)open;
        else bp.add(open);
    }
    return grid ? string() : bp.finish();
}
static void decode_full_partition(const string &enc, int parts, int id, vector<unsigned char> &grid) {
    long long bit = 0;
    decode_bits_known(enc, part_count(TOTAL_CELLS, parts, id), [&](bool one) {
        long long idx = id + bit * parts;
        if (idx < TOTAL_CELLS) grid[(size_t)idx] = (unsigned char)(forced_open_cell(idx) ? 1 : one);
        ++bit;
    });
}
static string solve_full_grid(const vector<unsigned char> &open) {
    if (N == 1) return "";
    vector<int> parent((size_t)TOTAL_CELLS, -1);
    vector<char> pdir((size_t)TOTAL_CELLS, 0);
    queue<int> q; parent[0] = -2; q.push(0);
    const int dr[4] = {-1,1,0,0}, dc[4] = {0,0,-1,1};
    const char ch[4] = {'U','D','L','R'};
    while (!q.empty() && parent[(size_t)TOTAL_CELLS - 1] == -1) {
        int u = q.front(); q.pop(); int r = u / N, c = u % N;
        for (int k = 0; k < 4; ++k) {
            int nr = r + dr[k], nc = c + dc[k];
            if (nr < 0 || nr >= N || nc < 0 || nc >= N) continue;
            int v = nr * N + nc;
            if (!open[(size_t)v] || parent[v] != -1) continue;
            parent[v] = u; pdir[v] = ch[k]; q.push(v);
            if (v == (int)TOTAL_CELLS - 1) break;
        }
    }
    if (parent[(size_t)TOTAL_CELLS - 1] == -1) return string();
    string ans;
    for (int cur = (int)TOTAL_CELLS - 1; cur != 0; cur = parent[cur]) ans.push_back(pdir[cur]);
    reverse(ans.begin(), ans.end());
    return ans;
}

static vector<string> receive_fixed_raw(int parts, long long total_items, int first_sender = 1, int sender_count = -1) {
    if (sender_count < 0) sender_count = parts - first_sender;
    vector<string> enc(parts);
    vector<long long> need(parts, 0), got(parts, 0);
    long long remaining = 0;
    for (int s = first_sender; s < first_sender + sender_count && s < parts; ++s) {
        need[s] = chunks_for_bits(part_count(total_items, parts, s));
        remaining += need[s];
    }
    while (remaining > 0) {
        int sender = -1; string body;
        if (!parse_any_message(transact("< ?"), sender, body)) continue;
        if (sender < first_sender || sender >= first_sender + sender_count || sender >= parts) continue;
        if (got[sender] >= need[sender]) continue;
        enc[sender] += body;
        ++got[sender]; --remaining;
    }
    return enc;
}

static void worker_wait_or_fallback(int parts) {
    while (true) {
        string body;
        if (!parse_message_from_zero(transact("< 0"), body) || body.empty()) continue;
        if (body[0] == 'F') {
            string enc = pack_full_partition(parts, AGENT_ID, nullptr);
            send_chunks_raw(0, enc);
            halt_agent();
        } else if (body[0] == 'H') halt_agent();
    }
}
static void full_fallback_and_claim(int parts) {
    for (int id = 1; id < parts; ++id) send_msg(id, "F");
    vector<unsigned char> grid((size_t)TOTAL_CELLS, 0);
    pack_full_partition(parts, 0, &grid);
    vector<string> enc = receive_fixed_raw(parts, TOTAL_CELLS);
    for (int id = 1; id < parts; ++id) decode_full_partition(enc[id], parts, id, grid);
    string p = solve_full_grid(grid);
    if (!p.empty() || N == 1) claim_path(p);
    halt_agent();
}

struct ScanPlan {
    int parts = 1;
    int direct = 0;
    int group = 1;
    long long estimate = (long long)4e18;
};
static long long read_finish_time(long long start_after_turn, vector<long long> arrivals) {
    if (arrivals.empty()) return start_after_turn;
    sort(arrivals.begin(), arrivals.end());
    long long t = start_after_turn, queued = 0, consumed = 0, total = (long long)arrivals.size();
    size_t ptr = 0;
    while (consumed < total) {
        ++t;
        while (ptr < arrivals.size() && arrivals[ptr] <= t) { ++queued; ++ptr; }
        if (queued > 0) { --queued; ++consumed; }
    }
    return t;
}
static long long estimate_direct_scan(long long items, int parts) {
    vector<long long> arrivals;
    for (int id = 1; id < parts; ++id) {
        long long q = part_count(items, parts, id), ch = chunks_for_bits(q);
        for (long long k = 1; k <= ch; ++k) arrivals.push_back(q + k + 1);
    }
    return read_finish_time(part_count(items, parts, 0), arrivals);
}
static long long estimate_mixed_scan(long long items, int parts, int direct, int group) {
    vector<long long> q(parts), enc_len(parts), ch(parts);
    for (int id = 0; id < parts; ++id) {
        q[id] = part_count(items, parts, id);
        enc_len[id] = encoded_len_for_bits(q[id]);
        ch[id] = chunks_for_chars(enc_len[id]);
    }
    vector<long long> final_arrivals;
    for (int id = 1; id <= direct; ++id) {
        for (long long k = 1; k <= ch[id]; ++k) final_arrivals.push_back(q[id] + k + 1);
    }
    for (int st = direct + 1; st < parts; st += group) {
        int en = min(parts, st + group), leader = st;
        vector<long long> to_leader;
        long long aggregate_chars = 0;
        for (int id = st; id < en; ++id) {
            aggregate_chars += enc_len[id];
            if (id == leader) continue;
            for (long long k = 1; k <= ch[id]; ++k) to_leader.push_back(q[id] + k + 1);
        }
        long long leader_done = read_finish_time(q[leader], to_leader);
        long long out_chunks = chunks_for_chars(aggregate_chars);
        for (long long k = 1; k <= out_chunks; ++k) final_arrivals.push_back(leader_done + k + 1);
    }
    return read_finish_time(q[0], final_arrivals);
}
static ScanPlan choose_scan_plan(long long items) {
    ScanPlan best;
    if (items <= 0 || PAYLOAD <= 0) return best;
    int maxS = (int)min<long long>(NUM_AGENTS, items);
    for (int s = 1; s <= maxS; ++s) {
        long long e = estimate_direct_scan(items, s);
        if (e < best.estimate || (e == best.estimate && s > best.parts)) {
            best.parts = s; best.direct = s - 1; best.group = 1; best.estimate = e;
        }
        if (s >= 4) {
            for (int direct = 0; direct <= s - 3; ++direct) {
                int rem = s - 1 - direct;
                for (int g = 2; g <= rem; ++g) {
                    long long me = estimate_mixed_scan(items, s, direct, g);
                    if (me < best.estimate || (me == best.estimate && s > best.parts)) {
                        best.parts = s; best.direct = direct; best.group = g; best.estimate = me;
                    }
                }
            }
        }
    }
    return best;
}

static inline int group_start_for_worker(int id, int direct, int group) {
    if (id <= direct) return 0;
    return direct + 1 + ((id - direct - 1) / group) * group;
}
static inline int group_end_for_start(int st, int parts, int group) { return min(parts, st + group); }

static void receive_worker_group_maps(int parts, int group, int leader, vector<string> &enc) {
    int en = group_end_for_start(leader, parts, group);
    vector<long long> need(parts, 0), got(parts, 0);
    long long remaining = 0;
    for (int id = leader + 1; id < en; ++id) { need[id] = chunks_for_bits(part_count(EDGE_COUNT, parts, id)); remaining += need[id]; }
    while (remaining > 0) {
        int sender = -1; string body;
        if (!parse_any_message(transact("< ?"), sender, body)) continue;
        if (sender <= leader || sender >= en) continue;
        if (got[sender] >= need[sender]) continue;
        enc[sender] += body; ++got[sender]; --remaining;
    }
}
static void worker_scan_direct(int parts) {
    string enc = pack_edge_partition(parts, AGENT_ID, nullptr);
    send_chunks_raw(0, enc);
    worker_wait_or_fallback(parts);
}
static void leader_scan_aggregate(int parts, int direct, int group) {
    int leader = AGENT_ID, en = group_end_for_start(leader, parts, group);
    vector<string> enc(parts);
    enc[leader] = pack_edge_partition(parts, leader, nullptr);
    receive_worker_group_maps(parts, group, leader, enc);
    string aggregate;
    size_t reserve = 0;
    for (int id = leader; id < en; ++id) reserve += (size_t)encoded_len_for_bits(part_count(EDGE_COUNT, parts, id));
    aggregate.reserve(reserve);
    for (int id = leader; id < en; ++id) aggregate += enc[id];
    send_chunks_raw(0, aggregate);
    worker_wait_or_fallback(parts);
}
static void nonleader_scan_to_group(int parts, int direct, int group) {
    int leader = group_start_for_worker(AGENT_ID, direct, group);
    string enc = pack_edge_partition(parts, AGENT_ID, nullptr);
    send_chunks_raw(leader, enc);
    worker_wait_or_fallback(parts);
}
static vector<string> receive_aggregated_maps(int parts, int direct, int group) {
    vector<string> enc(parts), aggregate(parts);
    vector<long long> need_direct(parts, 0), got_direct(parts, 0), need_agg(parts, 0), got_agg(parts, 0);
    long long remaining = 0;
    for (int id = 1; id <= direct; ++id) { need_direct[id] = chunks_for_bits(part_count(EDGE_COUNT, parts, id)); remaining += need_direct[id]; }
    for (int st = direct + 1; st < parts; st += group) {
        int en = group_end_for_start(st, parts, group);
        long long chars = 0;
        for (int id = st; id < en; ++id) chars += encoded_len_for_bits(part_count(EDGE_COUNT, parts, id));
        need_agg[st] = chunks_for_chars(chars); remaining += need_agg[st];
    }
    while (remaining > 0) {
        int sender = -1; string body;
        if (!parse_any_message(transact("< ?"), sender, body)) continue;
        if (sender <= 0 || sender >= parts) continue;
        if (sender <= direct) {
            if (got_direct[sender] >= need_direct[sender]) continue;
            enc[sender] += body; ++got_direct[sender]; --remaining;
        } else if (group_start_for_worker(sender, direct, group) == sender) {
            if (got_agg[sender] >= need_agg[sender]) continue;
            aggregate[sender] += body; ++got_agg[sender]; --remaining;
        }
    }
    for (int st = direct + 1; st < parts; st += group) {
        int en = group_end_for_start(st, parts, group);
        size_t pos = 0;
        for (int id = st; id < en; ++id) {
            size_t len = (size_t)encoded_len_for_bits(part_count(EDGE_COUNT, parts, id));
            enc[id] = (pos < aggregate[st].size()) ? aggregate[st].substr(pos, len) : string();
            pos += len;
        }
    }
    return enc;
}
static void coordinator_scan_aggregate_and_claim(int parts, int direct, int group) {
    vector<unsigned char> open_edges((size_t)EDGE_COUNT, 0);
    pack_edge_partition(parts, 0, &open_edges);
    vector<string> enc = (group <= 1) ? receive_fixed_raw(parts, EDGE_COUNT) : receive_aggregated_maps(parts, direct, group);
    for (int id = 1; id < parts; ++id) decode_edge_partition(enc[id], parts, id, open_edges);
    string path = solve_room_graph(open_edges);
    if (!path.empty() || ROOMS == 1) claim_path(path);
    full_fallback_and_claim(parts);
}
static void worker_scan_aggregate(int parts, int direct, int group) {
    if (group <= 1 || AGENT_ID <= direct) worker_scan_direct(parts);
    else {
        int leader = group_start_for_worker(AGENT_ID, direct, group);
        if (AGENT_ID == leader) leader_scan_aggregate(parts, direct, group);
        else nonleader_scan_to_group(parts, direct, group);
    }
}

// Receiver-only streaming scan: agent 0 only reads; workers 1..W cover all edges and
// stream chunks as they go.  Usually wins when many agents make communication dominant.
static long long estimate_receiver_scan(int workers, long long items) {
    if (workers <= 0 || items <= 0) return (long long)4e18;
    int pair_payload = max(1, PAYLOAD / 2);
    long long flush_bits = 13LL * pair_payload;
    vector<long long> release;
    long long max_worker = 0;
    for (int id = 0; id < workers; ++id) {
        long long bits = part_count(items, workers, id);
        long long ch = chunks_for_bits(bits);
        max_worker = max(max_worker, bits + ch);
        for (long long j = 1; j <= ch; ++j) {
            long long queried = min(bits, j * flush_bits);
            long long send_turn = queried + j;
            release.push_back(send_turn + 1);
        }
    }
    sort(release.begin(), release.end());
    long long t = 0;
    for (long long r : release) {
        if (t < r) t = r;
        else ++t;
    }
    return max(t, max_worker);
}
static int choose_receiver_workers(long long items, int max_workers, long long &best_est) {
    best_est = (long long)4e18;
    if (items <= 0 || max_workers <= 0) return 0;
    max_workers = (int)min<long long>(max_workers, items);
    int bestW = 1;
    for (int w = 1; w <= max_workers; ++w) {
        long long e = estimate_receiver_scan(w, items);
        if (e < best_est || (e == best_est && w > bestW)) { best_est = e; bestW = w; }
    }
    return bestW;
}
static void worker_scan_stream_to(int coord, int workers, int part_id) {
    BitPacker bp;
    int flush_bits = max(13, (PAYLOAD / 2) * 13);
    for (long long ord = part_id; ord < EDGE_COUNT; ord += workers) {
        bp.add(ask_edge_ord(ord));
        if (bp.bits >= flush_bits) send_msg(coord, bp.finish());
    }
    if (bp.bits > 0) send_msg(coord, bp.finish());
    halt_agent();
}
static void coordinator_scan_receiver_and_claim(int workers, int first_worker) {
    vector<string> enc(workers);
    vector<long long> need(workers, 0), got(workers, 0);
    long long remaining = 0;
    for (int id = 0; id < workers; ++id) { need[id] = chunks_for_bits(part_count(EDGE_COUNT, workers, id)); remaining += need[id]; }
    while (remaining > 0) {
        int sender = -1; string body;
        if (!parse_any_message(transact("< ?"), sender, body)) continue;
        int pid = sender - first_worker;
        if (pid < 0 || pid >= workers) continue;
        if (got[pid] >= need[pid]) continue;
        enc[pid] += body; ++got[pid]; --remaining;
    }
    vector<unsigned char> open_edges((size_t)EDGE_COUNT, 0);
    for (int id = 0; id < workers; ++id) decode_edge_partition(enc[id], workers, id, open_edges);
    string path = solve_room_graph(open_edges);
    if (!path.empty() || ROOMS == 1) claim_path(path);
    halt_agent();
}

// ---------------- Active bidirectional trace search ----------------

static const int DR[4] = {-1, 1, 0, 0};
static const int DC[4] = {0, 0, -1, 1};
static const char DCH[4] = {'U', 'D', 'L', 'R'};
static const int OPP[4] = {1, 0, 3, 2};
static const int PREFS[8][4] = {
    {1,3,2,0}, {3,1,0,2}, {1,3,0,2}, {3,1,2,0},
    {0,2,1,3}, {2,0,3,1}, {1,0,3,2}, {3,2,1,0}
};
static inline int move_room(int u, int dir) {
    int r = u / RM, c = u % RM;
    r += DR[dir]; c += DC[dir];
    if (r < 0 || r >= RM || c < 0 || c >= RM) return -1;
    return r * RM + c;
}
static inline long long edge_between_rooms(int u, int v) {
    int ur = u / RM, uc = u % RM, vr = v / RM, vc = v % RM;
    if (ur == vr) return horiz_ord(ur, min(uc, vc));
    return vert_ord(min(ur, vr), uc);
}
static inline unsigned hash_edge_tie(int a, int b, int aid) {
    if (a > b) swap(a, b);
    unsigned x = (unsigned)a * 1000003u + (unsigned)b * 9176u + (unsigned)aid * 19260817u;
    x ^= x >> 16; x *= 0x7feb352du; x ^= x >> 15;
    return x;
}
static array<int,4> ordered_dirs_for(int u, int side, int mode, int aid) {
    int r = u / RM, c = u % RM;
    int tr = (side == 0 ? RM - 1 : 0), tc = tr;
    int prank[4]; for (int i = 0; i < 4; ++i) prank[PREFS[aid & 7][i]] = i;
    array<pair<long long,int>,4> arr;
    for (int d = 0; d < 4; ++d) {
        int nr = r + DR[d], nc = c + DC[d];
        long long score;
        if (nr < 0 || nr >= RM || nc < 0 || nc >= RM) score = (long long)4e18 + d;
        else {
            long long man = llabs(nr - tr) + llabs(nc - tc);
            long long diag = llabs((nr - nc) - (tr - tc));
            long long anti = llabs((nr + nc) - (tr + tc));
            if (mode == 1) score = man * 1000000LL + diag * 10000LL + prank[d];
            else if (mode == 2) score = man * 1000000LL + anti * 10000LL + prank[d];
            else if (mode == 3) score = max(llabs(nr - tr), llabs(nc - tc)) * 1000000LL + man * 1000LL + prank[d];
            else if (mode == 4) score = man * 1000000LL + (hash_edge_tie(u, nr * RM + nc, aid) % 997u);
            else if (mode == 5) score = man * 1000000LL + diag * 50000LL + (hash_edge_tie(u, nr * RM + nc, aid + 17) % 251u);
            else if (mode == 6) score = prank[d];
            else if (mode == 7) score = -man * 1000000LL + prank[d];
            else if (mode == 8) score = diag * 1000000LL + man * 1000LL + prank[d];
            else if (mode == 9) score = anti * 1000000LL + man * 1000LL + prank[d];
            else if (mode == 10) score = (hash_edge_tie(u, nr * RM + nc, aid + 101) % 1000003u);
            else if (mode == 11) score = -man * 1000000LL + (hash_edge_tie(u, nr * RM + nc, aid + 211) % 1000003u);
            else if (mode == 12) score = diag * 1000000LL + (hash_edge_tie(u, nr * RM + nc, aid + 307) % 1000003u);
            else if (mode == 13) score = anti * 1000000LL + (hash_edge_tie(u, nr * RM + nc, aid + 401) % 1000003u);
            else score = man * 1000000LL + prank[d];
        }
        arr[d] = {score, d};
    }
    sort(arr.begin(), arr.end());
    array<int,4> out{}; for (int i = 0; i < 4; ++i) out[i] = arr[i].second;
    return out;
}
struct StepResult { bool queried=false, bit=false; int new_node=-1; bool found=false, exhausted=false; };
struct SearchState {
    int aid=0, side=0, mode=0, root=0, target=0;
    vector<signed char> parent_dir;
    vector<unsigned char> next_idx;
    vector<int> st;
    void init(int aid_, int side_, int mode_) {
        aid=aid_; side=side_; mode=mode_;
        root = (side==0 ? 0 : (int)ROOMS-1);
        target = (side==0 ? (int)ROOMS-1 : 0);
        parent_dir.assign((size_t)ROOMS, (signed char)-1);
        next_idx.assign((size_t)ROOMS, 0);
        st.clear(); st.push_back(root); parent_dir[root] = (signed char)-2;
    }
    StepResult step_query() {
        StepResult res;
        while (!st.empty()) {
            int u = st.back();
            if (u == target) { res.found = true; return res; }
            auto ord = ordered_dirs_for(u, side, mode, aid);
            while (next_idx[u] < 4) {
                int dir = ord[next_idx[u]++];
                int v = move_room(u, dir);
                if (v < 0 || parent_dir[v] != (signed char)-1) continue;
                bool open = ask_edge_ord(edge_between_rooms(u, v));
                res.queried = true; res.bit = open;
                if (open) {
                    parent_dir[v] = (signed char)OPP[dir]; st.push_back(v); res.new_node = v;
                    if (v == target) res.found = true;
                }
                return res;
            }
            st.pop_back();
        }
        res.exhausted = true; return res;
    }
    int apply_bit(bool open) {
        while (!st.empty()) {
            int u = st.back();
            auto ord = ordered_dirs_for(u, side, mode, aid);
            while (next_idx[u] < 4) {
                int dir = ord[next_idx[u]++];
                int v = move_room(u, dir);
                if (v < 0 || parent_dir[v] != (signed char)-1) continue;
                if (open) { parent_dir[v] = (signed char)OPP[dir]; st.push_back(v); return v; }
                return -1;
            }
            st.pop_back();
        }
        return -1;
    }
};
static vector<int> room_nodes_root_to_node(const SearchState &s, int node) {
    vector<int> rev; int cur = node, guard = 0;
    while (true) {
        if (cur < 0 || cur >= (int)ROOMS || ++guard > (int)ROOMS + 1) return {};
        rev.push_back(cur);
        if (cur == s.root) break;
        int d = (int)s.parent_dir[cur];
        if (d < 0 || d > 3) return {};
        cur = move_room(cur, d);
    }
    reverse(rev.begin(), rev.end());
    return rev;
}
static char dir_between_room_nodes(int a, int b) {
    if (b == a - RM) return 'U';
    if (b == a + RM) return 'D';
    if (b == a - 1) return 'L';
    if (b == a + 1) return 'R';
    return '?';
}
static string expand_room_path(const string &room_path) {
    string full; full.reserve(room_path.size() * 2);
    for (char ch : room_path) { full.push_back(ch); full.push_back(ch); }
    return full;
}
static string direct_claim_path_from_state(const SearchState &s) {
    vector<int> a = room_nodes_root_to_node(s, s.target);
    if (a.empty()) return string();
    string rp;
    if (s.side == 0) {
        for (size_t i = 1; i < a.size(); ++i) rp.push_back(dir_between_room_nodes(a[i-1], a[i]));
    } else {
        for (int i = (int)a.size() - 1; i >= 1; --i) rp.push_back(dir_between_room_nodes(a[i], a[i-1]));
    }
    return expand_room_path(rp);
}
static string meet_claim_path(const SearchState &start_state, const SearchState &goal_state, int meet) {
    vector<int> a = room_nodes_root_to_node(start_state, meet); // start -> meet
    vector<int> b = room_nodes_root_to_node(goal_state, meet);  // goal -> meet
    if (a.empty() || b.empty()) return string();
    int i = (int)a.size() - 1, j = (int)b.size() - 1;
    while (i > 0 && j > 0 && a[i - 1] == b[j - 1]) { --i; --j; }
    if (a[i] != b[j]) return string();
    string rp;
    for (int k = 1; k <= i; ++k) {
        char ch = dir_between_room_nodes(a[k - 1], a[k]); if (ch == '?') return string(); rp.push_back(ch);
    }
    for (int k = j; k >= 1; --k) {
        char ch = dir_between_room_nodes(b[k], b[k - 1]); if (ch == '?') return string(); rp.push_back(ch);
    }
    return expand_room_path(rp);
}

static int active_side_for_agent(int id) {
    if (id == 0) return 0;
    // Balance both frontiers for 4+ active agents; for exactly 3, keep two exit racers.
    if (ACTIVE_AGENTS <= 3) return 1;
    return (id & 1) ? 1 : 0;
}
static int active_mode_for_agent(int id) {
    if (id == 0) return 0;
    static const int modes[] = {8, 6, 10, 11, 4, 5, 12, 13, 1, 3, 0, 2, 9, 7};
    int side = active_side_for_agent(id), rank = 0;
    for (int j = 1; j < id; ++j) if (active_side_for_agent(j) == side) ++rank;
    return modes[rank % (int)(sizeof(modes)/sizeof(modes[0]))];
}
static int trace_flush_bits() {
    int cap = max(13, (PAYLOAD / 2) * 13);
    int target;
    if (RM <= 60) target = 104;
    else if (RM <= 120) target = (ACTIVE_AGENTS <= 3 ? 208 : 208);
    else if (RM <= 180) target = 390;
    else if (RM <= 230) target = 390;
    else target = 780;
    int b = min(target, cap);
    b = max(13, (b / 13) * 13);
    return b;
}
static int active_recv_every() {
    if (RM <= 60) return 32;
    if (RM <= 120) return (ACTIVE_AGENTS <= 3 ? 64 : 128);
    if (RM <= 180) return 128;
    if (RM <= 230) return 128;
    return (ACTIVE_AGENTS <= 4 ? 512 : 256);
}
static void active_worker() {
    SearchState s; s.init(AGENT_ID, active_side_for_agent(AGENT_ID), active_mode_for_agent(AGENT_ID));
    BitPacker bp;
    const int flush_bits = trace_flush_bits();
    while (true) {
        if (bp.bits >= flush_bits) { send_msg(0, bp.finish()); continue; }
        StepResult r = s.step_query();
        if (r.queried) {
            bp.add(r.bit);
            if (r.found) claim_path(direct_claim_path_from_state(s));
        } else if (r.found) claim_path(direct_claim_path_from_state(s));
        else if (r.exhausted) halt_agent();
    }
}
static void active_coordinator() {
    vector<SearchState> states(ACTIVE_AGENTS);
    for (int id = 0; id < ACTIVE_AGENTS; ++id) states[id].init(id, active_side_for_agent(id), active_mode_for_agent(id));
    vector<int> first_start((size_t)ROOMS, -1), first_goal((size_t)ROOMS, -1);
    for (int id = 0; id < ACTIVE_AGENTS; ++id) {
        if (active_side_for_agent(id) == 0) { if (first_start[0] < 0) first_start[0] = id; }
        else { if (first_goal[(size_t)ROOMS - 1] < 0) first_goal[(size_t)ROOMS - 1] = id; }
    }
    auto note_seen = [&](int side, int node, int who) -> bool {
        if (node < 0) return false;
        if (side == 0) { if (first_start[(size_t)node] < 0) first_start[(size_t)node] = who; return first_goal[(size_t)node] >= 0; }
        else { if (first_goal[(size_t)node] < 0) first_goal[(size_t)node] = who; return first_start[(size_t)node] >= 0; }
    };
    auto try_claim_meet = [&](int node) {
        int sw = first_start[(size_t)node], gw = first_goal[(size_t)node];
        if (sw < 0 || gw < 0) return;
        string path = meet_claim_path(states[sw], states[gw], node);
        if (!path.empty() || node == 0 || node == (int)ROOMS - 1) claim_path(path);
    };
    const int TRACE_FLUSH = trace_flush_bits();
    long long turn = 0;
    long long next_recv_turn = (long long)TRACE_FLUSH + 2;
    int burst_left = 0;
    while (true) {
        ++turn;
        bool do_recv = (burst_left > 0) || (turn >= next_recv_turn);
        if (do_recv) {
            int sender = -1; string body;
            bool got = parse_any_message(transact("< ?"), sender, body);
            if (!got || sender <= 0 || sender >= ACTIVE_AGENTS || body.empty()) {
                burst_left = 0;
                while (next_recv_turn <= turn) next_recv_turn += (long long)TRACE_FLUSH + 1;
                continue;
            }
            if (burst_left == 0) burst_left = max(0, ACTIVE_AGENTS - 2);
            else --burst_left;
            SearchState &st = states[sender]; int side = active_side_for_agent(sender);
            decode_bits_full_pairs(body, [&](bool bit) {
                int node = st.apply_bit(bit);
                if (node >= 0) { if (note_seen(side, node, sender)) try_claim_meet(node); }
            });
        } else {
            StepResult r = states[0].step_query();
            if (r.queried) {
                if (r.new_node >= 0) { if (note_seen(0, r.new_node, 0)) try_claim_meet(r.new_node); }
                if (r.found) claim_path(direct_claim_path_from_state(states[0]));
            } else if (r.found) claim_path(direct_claim_path_from_state(states[0]));
            else if (r.exhausted) (void)transact("< ?");
        }
    }
}
static int choose_active_agents() {
    if ((N & 1) == 0 || MAX_MSG_LEN < 16 || NUM_AGENTS < 3 || N < 51) return 0;
    // Conservative thresholds from local DFS-maze testing.  Above this, complete scan is steadier.
    if (NUM_AGENTS <= 4) return NUM_AGENTS;
    if (NUM_AGENTS == 5) return NUM_AGENTS;
    if (NUM_AGENTS == 6) return (N >= 301 ? NUM_AGENTS : 0);
    if (NUM_AGENTS == 7) return (N >= 451 ? NUM_AGENTS : 0);
    return 0;
}
static long long active_turn_estimate(int k) {
    if (k < 3) return (long long)4e18;
    if (NUM_AGENTS <= 3) return 1;
    if (NUM_AGENTS <= 5) return (N >= 101 ? 1 : 260);
    if (NUM_AGENTS == 6) return (N >= 301 ? 1 : (long long)4e18);
    if (NUM_AGENTS == 7) return (N >= 451 ? 1 : (long long)4e18);
    return (long long)4e18;
}

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

    if (!(cin >> N >> NUM_AGENTS >> AGENT_ID >> MAX_MSG_LEN)) return 0;
    string dummy; getline(cin, dummy);

    TOTAL_CELLS = 1LL * N * N;
    RM = (N + 1) / 2;
    ROOMS = 1LL * RM * RM;
    H_EDGES = (RM >= 1) ? 1LL * RM * (RM - 1) : 0;
    EDGE_COUNT = 2 * H_EDGES;
    PAYLOAD = max(1, MAX_MSG_LEN);

    if (N == 1) {
        if (AGENT_ID == 0) claim_path("");
        halt_agent();
    }

    if ((N & 1) == 0 || MAX_MSG_LEN < 2) {
        int parts = (MAX_MSG_LEN < 2) ? 1 : (int)min<long long>(NUM_AGENTS, max(1LL, TOTAL_CELLS));
        if (AGENT_ID == 0) full_fallback_and_claim(parts);
        if (AGENT_ID < parts) {
            string body;
            while (!parse_message_from_zero(transact("< 0"), body) || body.empty() || body[0] != 'F') {}
            string enc = pack_full_partition(parts, AGENT_ID, nullptr);
            send_chunks_raw(0, enc);
            halt_agent();
        }
        halt_agent();
    }

    ScanPlan plan = choose_scan_plan(EDGE_COUNT);
    long long recv_est = (long long)4e18;
    int recv_workers = choose_receiver_workers(EDGE_COUNT, NUM_AGENTS - 1, recv_est);
    long long best_scan_est = min(plan.estimate, recv_est);

    int ak = choose_active_agents();
    long long aest = active_turn_estimate(ak);
    if (ak >= 3 && aest < best_scan_est) {
        ACTIVE_AGENTS = ak;
        if (AGENT_ID < ACTIVE_AGENTS) {
            if (AGENT_ID == 0) active_coordinator();
            else active_worker();
        } else halt_agent();
    }

    if (recv_workers > 0 && recv_est < plan.estimate) {
        if (AGENT_ID == 0) coordinator_scan_receiver_and_claim(recv_workers, 1);
        else if (AGENT_ID >= 1 && AGENT_ID <= recv_workers) worker_scan_stream_to(0, recv_workers, AGENT_ID - 1);
        else halt_agent();
    } else {
        if (AGENT_ID == 0) coordinator_scan_aggregate_and_claim(plan.parts, plan.direct, plan.group);
        else if (AGENT_ID < plan.parts) worker_scan_aggregate(plan.parts, plan.direct, plan.group);
        else halt_agent();
    }
    return 0;
}