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

// Datacenter Imprisonment - extreme low-turn hybrid agent.
//
// Safe baseline: odd-grid room-graph scan.  It queries only corridor cells between
// always-open room cells and reconstructs the unique room-tree path.
//
// Score-oriented addition: for the small-agent, large-maze cases where full scanning is
// expensive, run an active bidirectional trace search instead.  Agent 0 searches from
// the entrance, the other active agents search from the exit with different deterministic
// DFS priorities.  Workers periodically send packed query-result traces; agent 0 mirrors
// their searches and claims as soon as the explored entrance and exit components meet.
// Workers also claim directly if they reach the opposite corner first.

static int N, NUM_AGENTS, AGENT_ID, MAX_MSG_LEN;
static long long TOTAL_CELLS;
static int RM;                 // room rows/cols = (N+1)/2
static long long ROOMS;
static long long H_EDGES;
static long long EDGE_COUNT;
static int PAYLOAD;

static const string ALPH = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz+/";
static int VAL[128];

[[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();
}

static inline int val_of(char ch) {
    unsigned char u = (unsigned char)ch;
    return (u < 128 && VAL[u] >= 0) ? VAL[u] : 0;
}

struct BitPacker {
    string s;
    int acc = 0, cnt = 0, bits = 0;
    void add(bool bit) {
        if (bit) acc |= (1 << cnt);
        ++bits;
        if (++cnt == 6) {
            s.push_back(ALPH[acc]);
            acc = 0;
            cnt = 0;
        }
    }
    string finish() {
        if (cnt) s.push_back(ALPH[acc]);
        string out = s;
        s.clear();
        acc = cnt = bits = 0;
        return out;
    }
};

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 inline long long encoded_len_for_bits(long long bits) { return (bits + 5) / 6; }
static inline long long chunks_for_bits(long long bits) {
    if (bits <= 0) return 0;
    if (PAYLOAD <= 0) return (long long)4e18;
    long long chars = encoded_len_for_bits(bits);
    return (chars + PAYLOAD - 1) / PAYLOAD;
}


struct ScanPlan {
    int parts = 1;
    int direct = 0; // workers 1..direct send straight to coordinator in mixed aggregation mode
    int group = 1;  // 1 = everyone direct; >1 = remaining workers are aggregated in consecutive groups
    long long estimate = (long long)4e18;
};

static 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 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;
    size_t ptr = 0;
    long long queued = 0, consumed = 0, total = (long long)arrivals.size();
    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;
    arrivals.reserve((size_t)parts * 4);
    for (int id = 1; id < parts; ++id) {
        long long q = part_count(items, parts, id);
        long long 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);
        int 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_reading = 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_reading + k + 1);
    }
    return read_finish_time(q[0], final_arrivals);
}

static ScanPlan choose_scan_plan(long long items) {
    ScanPlan best;
    if (items <= 0 || MAX_MSG_LEN < 2) return best;
    int maxS = (int)min<long long>(NUM_AGENTS, items);
    for (int s = 1; s <= maxS; ++s) {
        long long direct_est = estimate_direct_scan(items, s);
        if (direct_est < best.estimate || (direct_est == best.estimate && s > best.parts)) {
            best.parts = s;
            best.direct = s - 1;
            best.group = 1;
            best.estimate = direct_est;
        }
        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 est = estimate_mixed_scan(items, s, direct, g);
                    if (est < best.estimate || (est == best.estimate && s > best.parts)) {
                        best.parts = s;
                        best.direct = direct;
                        best.group = g;
                        best.estimate = est;
                    }
                }
            }
        }
    }
    return best;
}

// Edge order used by the complete scan:
// [0,H_EDGES): horizontal edge (r,c)--(r,c+1)
// [H_EDGES,EDGE_COUNT): vertical edge (r,c)--(r+1,c)
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;
    for (long long ord = id; ord < EDGE_COUNT; ord += parts, ++bit) {
        size_t ci = (size_t)(bit / 6);
        int off = (int)(bit % 6);
        int v = (ci < enc.size()) ? val_of(enc[ci]) : 0;
        open_edges[ord] = (unsigned char)((v >> off) & 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) return false;
    int x = 0;
    if (sp == 0) return false;
    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(int to, char tag, const string &enc) {
    if (PAYLOAD <= 0) halt_agent();
    for (size_t pos = 0; pos < enc.size(); pos += (size_t)PAYLOAD) {
        string body;
        body.push_back(tag);
        body += enc.substr(pos, min<size_t>((size_t)PAYLOAD, enc.size() - pos));
        send_msg(to, body);
    }
}

static vector<string> receive_fixed_maps(int parts, long long total_items, char tag) {
    vector<string> enc(parts);
    vector<long long> need(parts, 0), got(parts, 0);
    long long remaining = 0;
    for (int id = 1; id < parts; ++id) {
        need[id] = chunks_for_bits(part_count(total_items, parts, id));
        remaining += need[id];
    }
    while (remaining > 0) {
        int sender = -1;
        string body;
        if (!parse_any_message(transact("< ?"), sender, body)) continue;
        if (sender <= 0 || sender >= parts || body.empty() || body[0] != tag) continue;
        if (got[sender] >= need[sender]) continue;
        enc[sender] += body.substr(1);
        ++got[sender];
        --remaining;
    }
    return enc;
}

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[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 room_path;
    for (int cur = (int)ROOMS - 1; cur != 0; cur = parent[cur]) {
        int p = parent[cur];
        if (cur == p + 1) room_path.push_back('R');
        else if (cur == p - 1) room_path.push_back('L');
        else if (cur == p + RM) room_path.push_back('D');
        else if (cur == p - RM) room_path.push_back('U');
        else return string();
    }
    reverse(room_path.begin(), room_path.end());
    string ans;
    ans.reserve(room_path.size() * 2);
    for (char ch : room_path) {
        ans.push_back(ch);
        ans.push_back(ch);
    }
    return ans;
}

// Generic full-grid fallback for unexpected non-odd-grid situations.
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)[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;
    for (long long idx = id; idx < TOTAL_CELLS; idx += parts, ++bit) {
        size_t ci = (size_t)(bit / 6);
        int off = (int)(bit % 6);
        int v = (ci < enc.size()) ? val_of(enc[ci]) : 0;
        grid[idx] = (unsigned char)(forced_open_cell(idx) ? 1 : ((v >> off) & 1));
    }
}

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};
    const int dc[4] = {0, 0, -1, 1};
    const char step[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[v] || parent[v] != -1) continue;
            parent[v] = u;
            pdir[v] = step[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 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(0, 'G', 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_maps(parts, TOTAL_CELLS, 'G');
    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();
}

static void coordinator_scan_and_claim(int parts) {
    vector<unsigned char> open_edges((size_t)EDGE_COUNT, 0);
    pack_edge_partition(parts, 0, &open_edges);
    vector<string> enc = receive_fixed_maps(parts, EDGE_COUNT, 'M');
    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(int parts) {
    string enc = pack_edge_partition(parts, AGENT_ID, nullptr);
    send_chunks(0, 'M', enc);
    worker_wait_or_fallback(parts);
}


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 || body.empty() || body[0] != 'M') continue;
        if (got[sender] >= need[sender]) continue;
        enc[sender] += body.substr(1);
        ++got[sender];
        --remaining;
    }
}

static void leader_scan_aggregate(int parts, int direct, int group) {
    int leader = AGENT_ID;
    int 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;
    for (int id = leader; id < en; ++id) aggregate += enc[id];
    send_chunks(0, 'A', 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(leader, 'M', 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);
    vector<long long> 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 || body.empty()) continue;
        if (body[0] == 'M' && sender <= direct) {
            if (got_direct[sender] >= need_direct[sender]) continue;
            enc[sender] += body.substr(1);
            ++got_direct[sender];
            --remaining;
        } else if (body[0] == 'A' && sender > direct) {
            if (group_start_for_worker(sender, direct, group) != sender) continue;
            if (got_agg[sender] >= need_agg[sender]) continue;
            aggregate[sender] += body.substr(1);
            ++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));
            if (pos < aggregate[st].size()) enc[id] = aggregate[st].substr(pos, len);
            else enc[id].clear();
            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 = 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 (AGENT_ID <= direct) {
        worker_scan(parts);
        return;
    }
    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);
}

// ---------------- 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;
    int 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);
    int tc = (side == 0 ? RM - 1 : 0);
    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;
    bool bit = false;
    int new_node = -1;
    bool found = false;
    bool exhausted = false;
};

struct SearchState {
    int aid = 0, side = 0, mode = 0;
    int root = 0, target = 0;
    vector<signed char> parent_dir;  // direction from node to its parent; -1 unknown; -2 root
    vector<unsigned char> next_idx;
    vector<int> st;

    SearchState() {}
    SearchState(int aid_, int side_, int mode_) { init(aid_, side_, mode_); }

    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) continue;
                if (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) continue;
                if (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 string room_path_root_to_node(const SearchState &s, int node) {
    string rev_dirs;
    int cur = node;
    int guard = 0;
    while (cur != s.root) {
        if (cur < 0 || cur >= (int)ROOMS || ++guard > (int)ROOMS) return string();
        int d = (int)s.parent_dir[cur];
        if (d < 0 || d > 3) return string();
        rev_dirs.push_back(DCH[OPP[d]]); // parent -> current
        cur = move_room(cur, d);
    }
    reverse(rev_dirs.begin(), rev_dirs.end());
    return rev_dirs;
}

static string reverse_invert_room_path(const string &p) {
    string out;
    out.reserve(p.size());
    for (int i = (int)p.size() - 1; i >= 0; --i) {
        char ch = p[i];
        if (ch == 'U') out.push_back('D');
        else if (ch == 'D') out.push_back('U');
        else if (ch == 'L') out.push_back('R');
        else if (ch == 'R') out.push_back('L');
    }
    return out;
}

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) {
    string p = room_path_root_to_node(s, s.target);
    if (s.side == 0) return expand_room_path(p);
    return expand_room_path(reverse_invert_room_path(p));
}

static string meet_claim_path(const SearchState &start_state, const SearchState &goal_state, int meet) {
    string a = room_path_root_to_node(start_state, meet);       // start -> meet
    string b = room_path_root_to_node(goal_state, meet);        // goal -> meet
    if ((meet != start_state.root && a.empty()) || (meet != goal_state.root && b.empty())) return string();
    string room_path = a + reverse_invert_room_path(b);         // start -> meet -> goal
    return expand_room_path(room_path);
}

static int trace_flush_bits() {
    int cap = max(0, MAX_MSG_LEN - 1) * 6;
    int target = 384;
    if (NUM_AGENTS <= 3) target = (N <= 101 ? 256 : 320);
    int b = min(target, cap);
    b -= b % 6;
    if (b < 6) b = 6;
    return b;
}

static int active_side_for_agent(int id) {
    return (id == 0) ? 0 : 1; // agent 0 from entrance; all workers from exit
}
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};
    return modes[(id - 1) % (int)(sizeof(modes) / sizeof(modes[0]))];
}

static void active_worker() {
    SearchState s(AGENT_ID, active_side_for_agent(AGENT_ID), active_mode_for_agent(AGENT_ID));
    BitPacker bp;
    int flush_bits = trace_flush_bits();
    while (true) {
        if (bp.bits >= flush_bits) {
            send_msg(0, string("T") + 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) {
            // Connected perfect mazes should be found before exhaustion.  Send any trace, then bow out.
            if (bp.bits > 0) send_msg(0, string("T") + bp.finish());
            halt_agent();
        }
    }
}

static void active_coordinator() {
    vector<SearchState> states(NUM_AGENTS);
    for (int id = 0; id < NUM_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);
    first_start[0] = 0;
    for (int id = 1; id < NUM_AGENTS; ++id) 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[node] < 0) first_start[node] = who;
            return first_goal[node] >= 0;
        } else {
            if (first_goal[node] < 0) first_goal[node] = who;
            return first_start[node] >= 0;
        }
    };

    auto try_claim_meet = [&](int node) {
        int sw = first_start[node], gw = first_goal[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 RECV_EVERY_LOCAL_QUERIES = 256;
    int local_queries_since_recv = 0;
    int burst_left = 0;

    while (true) {
        bool do_recv = false;
        if (burst_left > 0) do_recv = true;
        else if (local_queries_since_recv >= RECV_EVERY_LOCAL_QUERIES) do_recv = true;

        if (do_recv) {
            int sender = -1;
            string body;
            bool got = parse_any_message(transact("< ?"), sender, body);
            local_queries_since_recv = 0;
            if (!got || sender <= 0 || sender >= NUM_AGENTS || body.empty() || body[0] != 'T') {
                burst_left = 0;
                continue;
            }
            if (burst_left == 0) burst_left = 3;
            else --burst_left;
            SearchState &st = states[sender];
            int side = active_side_for_agent(sender);
            for (size_t i = 1; i < body.size(); ++i) {
                int v = val_of(body[i]);
                for (int b = 0; b < 6; ++b) {
                    int node = st.apply_bit(((v >> b) & 1) != 0);
                    if (node >= 0) {
                        if (note_seen(side, node, sender)) try_claim_meet(node);
                    }
                }
            }
        } else {
            StepResult r = states[0].step_query();
            if (r.queried) {
                ++local_queries_since_recv;
                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) {
                // Very unlikely for a connected maze before reaching the target; fall back to waiting.
                (void)transact("< ?");
            }
        }
    }
}

static bool use_active_mode() {
    if ((N & 1) == 0 || MAX_MSG_LEN < 16 || NUM_AGENTS < 3 || N < 51) return false;
    if (NUM_AGENTS <= 3) return true;
    if (NUM_AGENTS == 4) return N >= 251;
    if (NUM_AGENTS <= 6) return N >= 301;
    if (NUM_AGENTS == 7) return N >= 451;
    return false;
}

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

    for (int i = 0; i < 128; ++i) VAL[i] = -1;
    for (int i = 0; i < (int)ALPH.size(); ++i) VAL[(int)ALPH[i]] = i;

    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_MSG_LEN - 1;

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

    if (use_active_mode()) {
        if (AGENT_ID == 0) active_coordinator();
        else active_worker();
    }

    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(0, 'G', enc);
            halt_agent();
        }
        halt_agent();
    }

    ScanPlan plan = choose_scan_plan(EDGE_COUNT);
    int scan_parts = plan.parts;
    if (AGENT_ID == 0) {
        if (plan.group <= 1) coordinator_scan_and_claim(scan_parts);
        else coordinator_scan_aggregate_and_claim(scan_parts, plan.direct, plan.group);
    } else if (AGENT_ID < scan_parts) {
        if (plan.group <= 1) worker_scan(scan_parts);
        else worker_scan_aggregate(scan_parts, plan.direct, plan.group);
    } else halt_agent();
    return 0;
}