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

// Datacenter Imprisonment - hybrid low-turn 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;
}

static int choose_scan_group(long long items) {
    if (items <= 0 || MAX_MSG_LEN < 2) return 1;
    int maxS = (int)min<long long>(NUM_AGENTS, items);
    int bestS = 1;
    long long best = items;
    for (int s = 1; s <= maxS; ++s) {
        long long maxq = (items + s - 1) / s;
        long long msgs = 0;
        for (int id = 1; id < s; ++id) msgs += chunks_for_bits(part_count(items, s, id));
        long long estimate = maxq + msgs;
        if (estimate < best || (estimate == best && s > bestS)) {
            best = estimate;
            bestS = s;
        }
    }
    return bestS;
}

// 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);
}

// ---------------- 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 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 b = min(384, 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, 4, 5, 1, 3, 0, 6, 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();
    }

    int scan_parts = choose_scan_group(EDGE_COUNT);
    if (AGENT_ID == 0) coordinator_scan_and_claim(scan_parts);
    else if (AGENT_ID < scan_parts) worker_scan(scan_parts);
    else halt_agent();
    return 0;
}