// D. Datacenter Imprisonment — v3: hybrid frontier / banded-scan / full-map.
//
// Maze structure (merlin-source/src/maze.rs): N odd, rooms at odd (r,c) are
// always empty, both-even cells are always walls; the 2*m*(m-1) edge cells
// (m=(N+1)/2) are the unknowns, and open cells form a spanning tree of rooms.
// Dually, the walls form a spanning tree of the planar dual ((m-1)^2 faces
// plus the outer face), which yields a second free-inference rule (v06):
// an unknown edge whose two dual faces are already wall-connected would
// close a wall cycle, so it is forced OPEN — the mirror of the primal rule
// (endpoints room-connected => forced wall). The two rules together are the
// complete inference set for this generator (brute-verified at m=3).
//
// Dispatch (see pickMode): low K runs the leader-coordinated frontier search;
// past its serialization point, mid/high K on non-tiny mazes runs the v4
// banded scan (uncoordinated strided scan in ascending-|i-j| band order,
// receive-only leader claims on corner connection); tiny mazes and the
// remaining cases run the proven v2 full-map partition (each agent scans a
// static chunk with union-find cycle inference, leader collects bit-packed
// results, BFS, claim).
//
// Frontier mode — the path can be found after exploring ~0.3-0.5 of the
// edges instead of ~0.93:
//   - Workers grow depth-first trees from both corners (tag A = start corner,
//     tag B = goal corner), biased toward the opposite corner. Wall results
//     inferable from local acyclicity are skipped for free.
//   - When a worker descends past a room that still has unqueried edges (a
//     branch point), it keeps up to HOARD of them for its own backtracking and
//     donates the rest to the leader's seed pool.
//   - Results and donations are batched into printable-ASCII records and
//     reported to the leader; idle workers poll and the leader hands them the
//     globally most promising seeds (closest to the opposite corner).
//   - The leader merges all reports into a union-find + open-cell grid; when
//     the corner components connect, it BFS-es the unique path and claims.
//   - At small K the leader also runs its own DFS between receives, so its
//     turns are not wasted idling.
//
// v07 protocol tightenings (from the harness-mechanics study; score = the
// round index of the claim, and a receive pops exactly one queued message):
//   - Full-map high K is drain-bound: W workers all report to agent 0, which
//     pops 1/round while everyone else is halted. Workers now report through
//     ceil(sqrt(W)) group heads that concatenate their group's fixed-size
//     bit-reports in id order and forward, so the leader drains ~sqrt(W)
//     streams instead of W messages.
//   - Band workers used to flush on a shared cadence phase, so reports
//     arrive in synchronized bursts the leader pops one per round; their
//     flush phases are now staggered by ID.
//
// v08 adaptive band (from the competitor study of the K>=20 tail rounds):
// the band scan's cost is p*E/(K-1) where p is the band-order position of
// the last edge the corner path needs, and on mazes whose corner path makes
// a deep excursion off the diagonal p -> 1 while the best teams stay at
// ~0.55 on every maze. The fix is maze-adaptive pruning: band reports
// become typed (walls too), so the leader can keep a closed global picture
// (primal+dual closure) as it drains its queue anyway; every EPOCH turns
// it recomputes the set of rooms whose wall-aware distA+distB is within
// SLACK of the minimum (the A* ellipse the true path must cross) and
// broadcasts a 16x16-cell hot map down a binary relay tree over the
// workers. Workers scan their slice in two passes — hot edges first, the
// rest later — so coverage concentrates where the path can still be.
// Deferral is not dropping: every slice edge is still queried unless
// locally inferable, so the claim logic and worst case (~plain band)
// are unchanged.
//
// v09 gap-heuristic frontier (from the A*-family study): the leader's seed
// pools were keyed by static Manhattan distance to the opposite CORNER,
// which chases a target the tree geometry has often made irrelevant and
// never re-ranks as walls arrive. Keys are now the wall-aware BFS distance
// from the seed's frontier room to the opposite tree's current component
// (front-to-front gap) over the leader's picture, batch-refreshed every
// AREFRESH leader turns (D*-Lite reduced to a periodic full re-key —
// pop-time repair adds nothing at pool-consumption rates). Pure h: any
// g-term re-derives uniform-cost fattening for path-length guarantees the
// score never pays for. Gap keys carry no progress-balance signal, so
// leader self-assignment alternates trees instead of comparing pool tops
// (which degenerates and starves tree 1 at K=2).
//
// v10: the adaptive-band gate drops from K>=20 to K>=14 (m>=100 kept).
// The K>=20 bound was inherited from the competitor study's tail rounds,
// not from a measured boundary; live m 120-180 x K 14-19 rounds replay
// 0.86-0.95 with the ellipse forced on (relay duty amortizes fine over
// 13+ workers), while K=13 is flat and m<100 still loses.
//
// v11 priority map (from the IAPI study): the binary hot map wastes its
// budget in both directions — early it says "everything hot" (the
// unknown-pass gapSum is constant on unexplored terrain, so the ellipse
// cannot discriminate until ~0.25E is known), late it cannot tell the
// corridor shell from the slack fringe; 63% of what workers scan lies
// outside the final corridor ellipse. Same message slot, cadence and
// relay tree now carry 4 bits per coarse cell: the cell's min gapSum
// above the global minimum, in STEP-room shells clamped to 15 (16 shells
// ~ the old slack at STEP=15... level 4+ ~ beyond slack 60). Workers
// scan lowest-level-first, band order within a level, re-aiming at the
// corridor gradient as each map arrives instead of two-pass hot/cold.
// Nothing is dropped: an absent or uniform map degenerates to plain band
// order and the v08 worst-case guarantee is intact.
//
// v12: the priority map moved both boundaries, so the dispatch catches up.
// The binary-map-era rules (adaptive only at K>=14 && m>=100; frontier up
// to the {123,14},{179,15},{251,21} crossover curve) predate the map's
// corridor gradient: re-measured with the 4-bit map, adaptive band beats
// plain band at K>=8 from m=60 up (0.80-0.96 geomean, m 60-100 mid-K) and
// beats the frontier itself from K=10 at m 75-162 and K=13 beyond (0.75-
// 0.95 across the flipped cells) — the map does the aiming that
// previously needed the leader's per-seed dispatch. Frontier holds where
// scanner crews are too thin for the epoch cadence (K 10-11 flip back to
// 1.10-1.13 at m>=183, K=12 to 1.08 at m=251) and below m=60, where games
// end before the map discriminates: both unchanged.
//
// Frontier records (94-ary chars '!'..'~', 3 chars each):
//   worker->leader: v = edge*4 + t     (t: 0 wall, 1 open)
//                   v = room*4 + 2+tag (donation of room's unqueried edges)
//   leader->worker: v = edge*4 + orient*2 + tag  (seed; orient picks the
//                   frontier-side room of the edge to continue exploring from)
// Worker report header (2 chars): idle flag and dispatches-received mod 94,
// which lets the leader detect "idle AND has seen all my dispatches" exactly.

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

static void say(const string &s) {
    fputs(s.c_str(), stdout);
    fputc('\n', stdout);
    fflush(stdout);
}

static string ask(const string &cmd) {
    say(cmd);
    string line;
    if (!getline(cin, line)) exit(0);
    return line;
}

static long long N, K, ID, L, m, E;
static vector<pair<int, int>> edges;      // edge id -> grid cell (r,c)
static vector<pair<int, int>> eRooms;     // edge id -> (room u, room v)
static vector<pair<int, int>> eFaces;     // edge id -> dual faces (f1, f2)
static vector<array<int, 4>> eidOf;       // room -> edge id per dir U,D,L,R
static int FOUT;                          // dual outer face id = (m-1)^2

static bool queryEdge(int e) {
    return ask("? " + to_string(edges[e].first) + " " +
               to_string(edges[e].second)) == "1";
}

struct UF {
    vector<int> p;
    explicit UF(int n) : p(n) { iota(p.begin(), p.end(), 0); }
    int find(int x) {
        while (p[x] != x) x = p[x] = p[p[x]];
        return x;
    }
    bool same(int a, int b) { return find(a) == find(b); }
    void unite(int a, int b) {
        a = find(a); b = find(b);
        if (a != b) p[a] = b;
    }
};

static void buildEdges() {
    edges.reserve(2 * m * (m - 1));
    eRooms.reserve(2 * m * (m - 1));
    eFaces.reserve(2 * m * (m - 1));
    eidOf.assign(m * m, {-1, -1, -1, -1});
    FOUT = (int)((m - 1) * (m - 1));
    for (long long i = 0; i < m; i++)
        for (long long j = 0; j < m; j++) {
            int id = (int)(i * m + j);
            if (i + 1 < m) {
                int e = (int)edges.size();
                edges.push_back({(int)(2 * i + 2), (int)(2 * j + 1)});
                eRooms.push_back({id, id + (int)m});
                // vertical room pair: faces left (i, j-1) and right (i, j)
                int f1 = (j - 1 < 0) ? FOUT : (int)(i * (m - 1) + (j - 1));
                int f2 = (j >= m - 1) ? FOUT : (int)(i * (m - 1) + j);
                eFaces.push_back({f1, f2});
                eidOf[id][1] = e; eidOf[id + m][0] = e;
            }
            if (j + 1 < m) {
                int e = (int)edges.size();
                edges.push_back({(int)(2 * i + 1), (int)(2 * j + 2)});
                eRooms.push_back({id, id + 1});
                // horizontal room pair: faces above (i-1, j) and below (i, j)
                int f1 = (i - 1 < 0) ? FOUT : (int)((i - 1) * (m - 1) + j);
                int f2 = (i >= m - 1) ? FOUT : (int)(i * (m - 1) + j);
                eFaces.push_back({f1, f2});
                eidOf[id][3] = e; eidOf[id + 1][2] = e;
            }
        }
    E = (long long)edges.size();
}

// Grid of known-open cells, rooms pre-marked (they are always empty).
static vector<char> roomGrid() {
    long long S = N + 2;
    vector<char> g(S * S, 0);
    for (long long i = 0; i < m; i++)
        for (long long j = 0; j < m; j++) g[(2 * i + 1) * S + (2 * j + 1)] = 1;
    return g;
}

// BFS (1,1)->(N,N) over known-open cells; claims and returns true if reached.
static bool claimPath(const vector<char> &open) {
    long long S = N + 2;
    vector<int> par(S * S, -1);
    vector<char> pmove(S * S, 0);
    deque<int> q;
    int startCell = (int)(S + 1), goal = (int)(N * S + N);
    par[startCell] = startCell;
    q.push_back(startCell);
    const int dr[4] = {-1, 1, 0, 0}, dc[4] = {0, 0, -1, 1};
    const char mv[4] = {'U', 'D', 'L', 'R'};
    while (!q.empty()) {
        int cur = q.front();
        q.pop_front();
        if (cur == goal) break;
        int r = cur / (int)S, c = cur % (int)S;
        for (int d = 0; d < 4; d++) {
            int nr = r + dr[d], nc = c + dc[d];
            if (nr < 1 || nc < 1 || nr > N || nc > N) continue;
            int nx = nr * (int)S + nc;
            if (!open[nx] || par[nx] != -1) continue;
            par[nx] = cur;
            pmove[nx] = mv[d];
            q.push_back(nx);
        }
    }
    if (par[goal] < 0) return false;
    string path;
    for (int cur = goal; cur != startCell; cur = par[cur]) path.push_back(pmove[cur]);
    reverse(path.begin(), path.end());
    say("! " + path);
    return true;
}

// Packs values MSB-first, 6 bits per printable char ('0' + v).
struct BitWriter {
    string buf;
    int acc = 0, n = 0;
    void push(unsigned val, int width) {
        for (int b = width - 1; b >= 0; b--) {
            acc = (acc << 1) | ((val >> b) & 1);
            if (++n == 6) {
                buf.push_back((char)('0' + acc));
                acc = n = 0;
            }
        }
    }
    void pad() {  // zero-fill the trailing partial char
        if (n) {
            buf.push_back((char)('0' + (acc << (6 - n))));
            acc = n = 0;
        }
    }
};

// ---------------- frontier mode ----------------

constexpr int RMAX = 44;       // records per report before forced flush
constexpr int CADENCE = 56;    // max turns between reports when active
// Branch points a worker keeps for itself. At high K subtrees die faster
// than the leader's serial dispatch loop can refuel them (the idle-tax
// dominates), so workers hoard more and self-serve; below that the pool's
// global prioritization is worth more than the saved round-trips.
// Real-judge A/B: -7..-19% at K=16-25, noisy-neutral below the gate.
static int hoardMax() {
    int h = (K >= 14) ? 8 : 4;
#ifdef V3TUNE
    if (const char *e = getenv("V3_HOARD")) h = atoi(e);
#endif
    return h;
}
constexpr int HOARD_L = 2;     // leader keeps fewer (it feeds the pool)
constexpr int BOOT_MSGS = 3;   // first reports flush fast to fill the pool
constexpr int BOOT_GAP = 4;
constexpr int B0 = 33;         // record alphabet base '!'

// Frontier pays off while workers stay query-bound; the leader's
// one-action-per-turn coordination serializes at a K that grows with maze
// size, and past that the uncoordinated banded scan takes over (it needs
// K>=5 and enough maze for the band prefix to beat a plain full scan;
// N=51 loses, N=79 wins 0.80x). Anchors below are the measured multi-seed
// frontier-vs-band crossovers (last K with frontier geomean <= band),
// interpolated linearly; small mazes flip much earlier. The priority-map
// band pulled the crossover curve down hard: K=9 through m~162 (band wins
// K>=10 at 0.80-0.95 there), back to 12 from m~178 on (thin scanner crews
// lose long corridors: K 10-11 flip to 1.10-1.13 at m>=183, K=12 to 1.08
// at m=251, while K=13 keeps winning at m=179/240 and K=16/19 at m=251).
enum Mode { FRONTIER, BAND, FULLMAP };

static Mode pickMode() {
    int cut = 3;
    if (m >= 40) {
        static const int A[][2] = {
            {40, 7}, {65, 7}, {75, 9}, {162, 9}, {178, 12}, {999, 12}};
        const int n = (int)(sizeof(A) / sizeof(A[0]));
        cut = 12;
        for (int i = 0; i + 1 < n; i++)
            if (m <= A[i + 1][0]) {
                cut = A[i][1] + (A[i + 1][1] - A[i][1]) * ((int)m - A[i][0]) /
                                    (A[i + 1][0] - A[i][0]);
                break;
            }
    }
#ifdef V3TUNE
    if (const char *e = getenv("V3_KCUT")) cut = atoi(e);
    if (const char *e = getenv("V3_MODE")) {
        if (!strcmp(e, "frontier")) return FRONTIER;
        if (!strcmp(e, "band")) return BAND;
        if (!strcmp(e, "full")) return FULLMAP;
    }
#endif
    if (m >= 8 && K <= cut) return FRONTIER;
    if (m >= 40 && K >= 5) return BAND;
    return FULLMAP;
}

static void enc3(string &s, uint32_t v) {
    s.push_back((char)(B0 + v % 94)); v /= 94;
    s.push_back((char)(B0 + v % 94)); v /= 94;
    s.push_back((char)(B0 + v));
}
static uint32_t dec3(const char *c) {
    return (uint32_t)(c[0] - B0) + 94u * (uint32_t)(c[1] - B0) +
           8836u * (uint32_t)(c[2] - B0);
}

// Direction preference: head for the opposite corner, longest axis first.
static array<int, 4> prefs(int room, int tag) {
    int i = room / (int)m, j = room % (int)m;
    if (tag == 0)
        return (m - 1 - i >= m - 1 - j) ? array<int, 4>{1, 3, 0, 2}
                                        : array<int, 4>{3, 1, 2, 0};
    return (i >= j) ? array<int, 4>{0, 2, 1, 3} : array<int, 4>{2, 0, 3, 1};
}

struct StackEntry {
    int room;
    int8_t tag;
    bool counted;   // holds one of our hoarded branch points
    bool donated;   // leftovers given away; skip on backtrack
};

// Shared DFS scaffolding for workers and the leader's own exploration.
struct Explorer {
    vector<int8_t> est;            // 0 unknown, 1 open, 2 wall (local view)
    UF uf;
    UF duf;                        // dual faces; walls unite them
    vector<char> visited;
    vector<StackEntry> st;
    deque<array<int, 3>> seeds;    // {edge, orient, tag}
    int hoard = 0;
    // Workers point this at their outbuf: locally-inferred walls and dropped
    // seeds must still reach the leader or its frontier accounting leaks
    // (an edge assigned to a worker that resolves it silently stays
    // "assigned" forever and the search can deadlock with work outstanding).
    vector<uint32_t> *log = nullptr;
    function<void(int)> onOpen;    // leader: mirror opens into the cell grid

    Explorer() : est(E, 0), uf((int)(m * m)), duf(FOUT + 1),
                 visited(m * m, 0) {}

    void noteWall(int e) {  // record wall knowledge in the dual
        duf.unite(eFaces[e].first, eFaces[e].second);
    }

    void inferWall(int e) {
        est[e] = 2;
        noteWall(e);
        if (log) log->push_back((uint32_t)e * 4u);
    }

    void inferOpen(int e) {  // bridge rule fired: edge is open for free
        est[e] = 1;
        uf.unite(eRooms[e].first, eRooms[e].second);
        if (log) log->push_back((uint32_t)e * 4u + 1u);
        if (onOpen) onOpen(e);
    }

    // Pops exhausted/donated entries and locally-inferable edges until a
    // queryable edge is found. Returns {edge, tag, frontierRoom, curRoom} or
    // edge=-1 when out of work. Pure computation, consumes no turn.
    array<int, 4> nextQuery() {
        for (;;) {
            if (!st.empty()) {
                int room = st.back().room;
                int8_t tag = st.back().tag;
                if (st.back().donated) { st.pop_back(); continue; }
                int found = -1, freeF = -1;
                for (int d : prefs(room, tag)) {
                    int e = eidOf[room][d];
                    if (e < 0 || est[e] != 0) continue;
                    auto [u, v] = eRooms[e];
                    if (uf.same(u, v)) { inferWall(e); continue; }
                    if (duf.same(eFaces[e].first, eFaces[e].second)) {
                        inferOpen(e);
                        int f = (u == room) ? v : u;
                        if (!visited[f]) { freeF = f; break; }
                        continue;
                    }
                    found = e; break;
                }
                if (freeF >= 0) {  // walk through the free open, no turn spent
                    visited[freeF] = 1;
                    st.push_back({freeF, tag, false, false});
                    continue;
                }
                if (found < 0) {
                    if (st.back().counted) hoard--;
                    st.pop_back();
                    continue;
                }
                auto [u, v] = eRooms[found];
                int f = (u == room) ? v : u;
                return {found, tag, f, room};
            }
            if (!seeds.empty()) {
                auto sd = seeds.front(); seeds.pop_front();
                int e = sd[0];
                if (est[e] != 0) {
                    // Already resolved locally; echo so the assignment clears.
                    if (log) log->push_back((uint32_t)e * 4u +
                                            (est[e] == 1 ? 1u : 0u));
                    continue;
                }
                auto [u, v] = eRooms[e];
                if (uf.same(u, v)) { inferWall(e); continue; }
                if (duf.same(eFaces[e].first, eFaces[e].second)) {
                    inferOpen(e);
                    int f = sd[1] ? v : u;
                    if (!visited[f]) {
                        visited[f] = 1;
                        st.push_back({f, (int8_t)sd[2], false, false});
                    }
                    continue;
                }
                return {e, sd[2], sd[1] ? v : u, -1};
            }
            return {-1, 0, -1, -1};
        }
    }

    // Integrate a query result; returns donated room or -1. Donation happens
    // when we descend past a branch point beyond our hoard budget.
    int applyResult(int e, int tag, int f, int curRoom, bool open, int hoardMax) {
        est[e] = open ? 1 : 2;
        if (!open) { noteWall(e); return -1; }
        auto [u, v] = eRooms[e];
        uf.unite(u, v);
        if (visited[f]) return -1;
        visited[f] = 1;
        int donated = -1;
        if (curRoom >= 0) {
            StackEntry &top = st.back();
            bool more = false;
            for (int d = 0; d < 4; d++) {
                int e2 = eidOf[curRoom][d];
                if (e2 >= 0 && est[e2] == 0) { more = true; break; }
            }
            if (more && !top.counted) {
                if (hoard < hoardMax) { top.counted = true; hoard++; }
                else { top.donated = true; donated = curRoom; }
            }
        }
        st.push_back({f, (int8_t)tag, false, false});
        return donated;
    }
};

static void frontierWorker() {
    Explorer ex;
    vector<uint32_t> outbuf;
    ex.log = &outbuf;
    // Leader knows every worker starts idle, so no initial idle report.
    bool hasDon = false, idleReported = true;
    long long sinceSend = 0, sentMsgs = 0;
    uint32_t dispRecv = 0;
    const int cap = (int)((L - 2) / 3);

    auto sendReport = [&](bool idleFlag) {
        int n = min((int)outbuf.size(), cap);
        string body;
        body.push_back((char)(B0 + (idleFlag ? 1 : 0)));
        body.push_back((char)(B0 + (int)(dispRecv % 94)));
        for (int i = 0; i < n; i++) enc3(body, outbuf[i]);
        outbuf.erase(outbuf.begin(), outbuf.begin() + n);
        ask("> 0 " + body);
        sinceSend = 0;
        sentMsgs++;
        if (outbuf.empty()) hasDon = false;
    };

    for (;;) {
        sinceSend++;
        // Flush BEFORE pulling the next query: nextQuery destructively pops
        // seeds, so bailing out between it and the actual query would leak
        // the assignment (the leader would wait on the edge forever).
        bool flush = (int)outbuf.size() >= RMAX ||
                     (hasDon && sentMsgs < BOOT_MSGS && sinceSend >= BOOT_GAP) ||
                     (!outbuf.empty() && sinceSend >= CADENCE);
        if (flush) { sendReport(false); continue; }
        auto [qe, qtag, qf, qcur] = ex.nextQuery();
        if (qe >= 0) {
            idleReported = false;
            bool open = queryEdge(qe);
            outbuf.push_back((uint32_t)qe * 4u + (open ? 1u : 0u));
            int don = ex.applyResult(qe, qtag, qf, qcur, open, hoardMax());
            if (don >= 0) {
                outbuf.push_back((uint32_t)don * 4u + 2u + (uint32_t)qtag);
                hasDon = true;
            }
            continue;
        }
        if (!outbuf.empty() || !idleReported) {
            sendReport(true);
            if (outbuf.empty()) idleReported = true;
            continue;
        }
        string r = ask("< 0");
        if (r != "- -") {
            size_t sp = r.find(' ');
            string body = r.substr(sp + 1);
            dispRecv++;
            for (size_t i = 0; i + 2 < body.size(); i += 3) {
                uint32_t v = dec3(body.data() + i);
                if (v >= 4u * (uint32_t)E) {
                    // Info record piggybacked after the seeds: an edge the
                    // leader already knows resolved, near our new frontier.
                    uint32_t vv = v - 4u * (uint32_t)E;
                    int e = (int)(vv >> 1);
                    if (ex.est[e] == 0) {
                        ex.est[e] = (vv & 1) ? 1 : 2;
                        if (vv & 1) {
                            auto [u, v2] = eRooms[e];
                            ex.uf.unite(u, v2);
                        } else {
                            ex.noteWall(e);
                        }
                    }
                } else {
                    ex.seeds.push_back({(int)(v >> 2), (int)((v >> 1) & 1),
                                        (int)(v & 1)});
                }
            }
        }
    }
}

static void frontierLeader() {
    Explorer ex;                    // leader's own exploration + global view
    long long S = N + 2;
    vector<char> open = roomGrid();

    // est extends Explorer semantics at the leader: 3 = pooled, 4 = assigned.
    // Per-tag pools: a single shared pool collapses into winner-takes-all
    // (one tree's fresher seeds shadow the other's, every agent drifts to one
    // corner and the abandoned tree stalls until the maze is nearly covered).
    using Seed = tuple<int, int, int, int, int>;  // prio, seq, edge, orient, tag
    priority_queue<Seed, vector<Seed>, greater<Seed>> poolT[2];
    deque<array<int, 3>> hotQ;    // meet-test edges: frontier in opposite comp
    const int roomA = 0, roomB = (int)(m * m - 1);
    int seq = 0;
    // Seed priority = wall-aware BFS distance from the seed's frontier room
    // to the opposite tree's current component (front-to-front gap), over
    // the leader's picture: known walls block, unknown edges pass. Pure h —
    // the certificate race wants greedy-on-h; any g-term fattens both trees
    // uniformly for path-length guarantees the scoring never pays for. Keys
    // are batch-refreshed (D*-Lite reduced to a periodic full re-key).
    const int UNREACHED = 1 << 26;
    const int AREFRESH = m >= 200 ? 64 : 32;
    vector<int> dTo[2];           // dTo[tag][room]: distance to opposite comp
    auto seedPrio = [&](int f, int tag) {
        if (!dTo[tag].empty() && dTo[tag][f] < UNREACHED) return dTo[tag][f];
        int i = f / (int)m, j = f % (int)m;   // pre-flood / beyond-flood
        return UNREACHED + (tag == 0 ? (int)(2 * (m - 1)) - i - j : i + j);
    };
    // function (not auto): inferred opens extend the frontier past the edge,
    // so poolRoom recurses through free walk-throughs.
    function<void(int, int)> poolRoom = [&](int room, int tag) {
        int other = ex.uf.find(tag == 0 ? roomB : roomA);
        for (int d = 0; d < 4; d++) {
            int e = eidOf[room][d];
            if (e < 0 || ex.est[e] != 0) continue;
            auto [u, v] = eRooms[e];
            if (ex.uf.same(u, v)) { ex.est[e] = 2; ex.noteWall(e); continue; }
            int f = (u == room) ? v : u;
            if (ex.duf.same(eFaces[e].first, eFaces[e].second)) {
                ex.inferOpen(e);      // bridge rule: open for free
                poolRoom(f, tag);     // keep the frontier moving past it
                continue;
            }
            if (ex.uf.find(f) == other) {
                ex.est[e] = 4;
                hotQ.push_back({e, (f == v) ? 1 : 0, tag});
            } else {
                ex.est[e] = 3;
                poolT[tag].push({seedPrio(f, tag), seq++, e, (f == v) ? 1 : 0,
                                 tag});
            }
        }
    };
    // Pop the best valid seed of a tag; cycle edges become inferred walls and
    // seeds whose frontier joined the opposite component divert to hotQ.
    auto popSeed = [&](int tag) -> optional<Seed> {
        auto &pq = poolT[tag];
        while (!pq.empty()) {
            Seed s = pq.top();
            pq.pop();
            auto [p, sq, e, orient, tg] = s;
            if (ex.est[e] != 3) continue;
            auto [u, v] = eRooms[e];
            if (ex.uf.same(u, v)) { ex.est[e] = 2; ex.noteWall(e); continue; }
            int f = orient ? v : u;
            if (ex.duf.same(eFaces[e].first, eFaces[e].second)) {
                ex.est[e] = 0;        // let inferOpen set it
                ex.inferOpen(e);
                poolRoom(f, tg);
                continue;
            }
            if (ex.uf.find(f) == ex.uf.find(tg == 0 ? roomB : roomA)) {
                ex.est[e] = 4;
                hotQ.push_back({e, orient, tg});
                continue;
            }
            return s;
        }
        return nullopt;
    };
    auto addOpen = [&](int e) {
        open[(long long)edges[e].first * S + edges[e].second] = 1;
    };
    ex.onOpen = addOpen;  // inferred opens must reach the claim-path grid

    // Recompute both gap fields (multi-source BFS from each tree's current
    // component) and rebuild the pools with fresh keys; dead entries drop.
    auto gapRefresh = [&]() {
        for (int tag = 0; tag < 2; tag++) {
            auto &dist = dTo[tag];
            dist.assign(m * m, UNREACHED);
            deque<int> q;
            int other = ex.uf.find(tag == 0 ? roomB : roomA);
            for (int r = 0; r < (int)(m * m); r++)
                if (ex.uf.find(r) == other) { dist[r] = 0; q.push_back(r); }
            while (!q.empty()) {
                int c = q.front();
                q.pop_front();
                for (int d = 0; d < 4; d++) {
                    int e = eidOf[c][d];
                    if (e < 0 || ex.est[e] == 2) continue;
                    auto [u, v] = eRooms[e];
                    int nc = (u == c) ? v : u;
                    if (dist[nc] > dist[c] + 1) {
                        dist[nc] = dist[c] + 1;
                        q.push_back(nc);
                    }
                }
            }
        }
        for (auto &pq : poolT) {
            vector<Seed> tmp;
            while (!pq.empty()) { tmp.push_back(pq.top()); pq.pop(); }
            for (auto &[p, sq, e, orient, tg] : tmp) {
                if (ex.est[e] != 3) continue;
                int f = orient ? eRooms[e].second : eRooms[e].first;
                pq.push({seedPrio(f, tg), sq, e, orient, tg});
            }
        }
    };
    gapRefresh();
    int sinceKey = 0, altTag = 0;

    poolRoom(roomA, 0);
    poolRoom(roomB, 1);
    // Piggyback scratch: lazily-stamped visited marks for the per-dispatch
    // BFS that collects resolved edges around handed-off frontiers.
    vector<int> pgE(E, 0), pgR(m * m, 0);
    int pgStamp = 0;
    vector<int> pgQ;
    deque<int> idleQ;
    vector<char> inIdle(K, 0);
    for (int w = 1; w < K; w++) { idleQ.push_back(w); inIdle[w] = 1; }
    vector<long long> dispCount(K, 0);
    const int rcv = max(1, min(16, (int)(45 / max(1LL, K - 1))));
    long long sinceRecv = 0;
    bool lastHit = false;

    for (;;) {
        if (ex.uf.same(roomA, roomB) && claimPath(open)) return;
        if (++sinceKey >= AREFRESH) { gapRefresh(); sinceKey = 0; }

        // 1) Meet-test edges first: their frontier room is already in the
        //    opposite component, so an open result immediately connects the
        //    corner trees. Query inline — never worth a worker round-trip.
        {
            bool did = false;
            while (!hotQ.empty()) {
                auto [e, orient, tag] = hotQ.front();
                hotQ.pop_front();
                if (ex.est[e] != 4) continue;
                auto [u, v] = eRooms[e];
                if (ex.uf.same(u, v)) { ex.est[e] = 2; ex.noteWall(e); continue; }
                if (ex.duf.same(eFaces[e].first, eFaces[e].second)) {
                    ex.est[e] = 0;    // bridge rule: meet edge open for free
                    ex.inferOpen(e);
                    continue;         // connect check at loop top fires
                }
                if (queryEdge(e)) {
                    ex.est[e] = 1;
                    ex.uf.unite(u, v);
                    addOpen(e);
                } else {
                    ex.est[e] = 2;
                    ex.noteWall(e);
                }
                did = true;
                break;
            }
            if (did) continue;
        }

        // 2) Activate idle workers (fully stalled) with the best pooled seeds
        //    of their own tag (falling back to the other tree only when
        //    theirs is empty), so both corner trees always keep growing.
        if (!idleQ.empty() && (!poolT[0].empty() || !poolT[1].empty())) {
            int w = idleQ.front();
            size_t psz = poolT[0].size() + poolT[1].size();
            int bs = max(1, min(6, (int)(psz / idleQ.size())));
            int wt = w % 2 == 1 ? 0 : 1;  // fixed tag affinity by parity
            string body;
            int n = 0;
            pgStamp++;
            pgQ.clear();
            for (int pass = 0; pass < 2 && n < bs; pass++) {
                int t = pass == 0 ? wt : 1 - wt;
                while (n < bs) {
                    auto s = popSeed(t);
                    if (!s) break;
                    auto [p, sq, e, orient, tg] = *s;
                    ex.est[e] = 4;
                    enc3(body, ((uint32_t)e << 2) | ((uint32_t)orient << 1) |
                                   (uint32_t)tg);
                    int f = orient ? eRooms[e].second : eRooms[e].first;
                    if (pgR[f] != pgStamp) { pgR[f] = pgStamp; pgQ.push_back(f); }
                    n++;
                }
            }
            if (n > 0) {
                // Piggyback known results around the seeds' frontier rooms:
                // the worker's est is stale exactly there, and each record it
                // absorbs is a duplicate query it won't spend a turn on. BFS
                // outward through leader-known opens (locality beats global
                // recency — measured), emitting resolved edges; workers
                // decode them via the >=4E info branch. Only past the
                // dup-tax regime: at low K free wall-skips let each DFS run
                // deeper per turn and the trees fatten (2.6x blowup measured
                // at N=151/K=3), so pre-knowledge costs more than it saves.
                int budget = K >= 8 ? min((int)((L - 4) / 3) - n, 78) : 0;
                for (size_t h = 0; h < pgQ.size() && budget > 0; h++) {
                    int room = pgQ[h];
                    for (int d = 0; d < 4 && budget > 0; d++) {
                        int e2 = eidOf[room][d];
                        if (e2 < 0 || pgE[e2] == pgStamp) continue;
                        pgE[e2] = pgStamp;
                        int8_t s2 = ex.est[e2];
                        if (s2 == 1 || s2 == 2) {
                            enc3(body, 4u * (uint32_t)E + (uint32_t)e2 * 2u +
                                           (s2 == 1 ? 1u : 0u));
                            budget--;
                        }
                        if (s2 == 1) {
                            auto [u2, v2] = eRooms[e2];
                            int far = (u2 == room) ? v2 : u2;
                            if (pgR[far] != pgStamp) {
                                pgR[far] = pgStamp;
                                pgQ.push_back(far);
                            }
                        }
                    }
                }
                idleQ.pop_front();
                inIdle[w] = 0;
                dispCount[w]++;
                ask("> " + to_string(w) + " " + body);
                continue;
            }
        }

        // 3) Receive reports (always when they may be queued; periodically
        //    otherwise), else 4) advance the leader's own DFS.
        sinceRecv++;
        bool doRecv = lastHit || sinceRecv >= rcv;
        if (!doRecv) {
            int qe = -1, qtag = 0, qf = -1, qcur = -1;
            for (;;) {
                auto nq = ex.nextQuery();
                if (nq[0] >= 0) {
                    qe = nq[0]; qtag = nq[1]; qf = nq[2]; qcur = nq[3];
                    break;
                }
                // Out of own work: self-assign alternating trees. Gap keys
                // carry no progress-balance signal (both pool tops share the
                // same front-to-front distance), so the old lagging-tree
                // comparison degenerates and one tree starves at K=2.
                auto s = popSeed(altTag);
                if (!s) s = popSeed(1 - altTag);
                if (!s) break;
                auto [p, sq, e, orient, tg] = *s;
                altTag = 1 - tg;
                ex.est[e] = 0;  // back to unknown; nextQuery will take it
                ex.seeds.push_back({e, orient, tg});
            }
            if (qe >= 0) {
                bool op = queryEdge(qe);
                int don = ex.applyResult(qe, qtag, qf, qcur, op, HOARD_L);
                if (op) addOpen(qe);
                if (don >= 0) poolRoom(don, qtag);
                continue;
            }
            doRecv = true;  // nothing else useful this turn
        }

        string r = ask("< ?");
        sinceRecv = 0;
        if (r == "- -") {
            lastHit = false;
            continue;
        }
        lastHit = true;
        size_t sp = r.find(' ');
        int s = (int)stoll(r.substr(0, sp));
        string body = r.substr(sp + 1);
        if (body.size() < 2) continue;
        int flags = body[0] - B0;
        int drecv = body[1] - B0;
        for (size_t i = 2; i + 2 < body.size(); i += 3) {
            uint32_t v = dec3(body.data() + i);
            uint32_t t = v & 3u;
            int code = (int)(v >> 2);
            if (t == 0) {
                if (ex.est[code] != 1) { ex.est[code] = 2; ex.noteWall(code); }
            } else if (t == 1) {
                if (ex.est[code] != 1) {
                    ex.est[code] = 1;
                    auto [u, v2] = eRooms[code];
                    ex.uf.unite(u, v2);
                    addOpen(code);
                }
            } else {
                poolRoom(code, (int)(t - 2));
            }
        }
        bool seenAll = drecv == (int)(dispCount[s] % 94);
        if ((flags & 1) && seenAll && !inIdle[s]) {
            idleQ.push_back(s);
            inIdle[s] = 1;
        }
    }
}

// ---------------- banded-scan mode (v4) ----------------
// The true corner-corner path stays near the main diagonal (max |i-j|
// deviation ~0.45m on the generator's USTs), so scanning edge cells in
// ascending-|i-j| band order connects the corners after ~0.69E cells on
// average instead of E. All agents compute the same band-sorted order;
// worker w scans the strided slice w-1, w-1+(K-1), ... so total coverage
// is always a prefix of the band order, with zero coordination messages
// and zero duplicate queries. Workers stream OPEN cell ids (fixed-width
// bit packing, 6 bits/char); the leader is receive-only (a scanning
// leader saturates its 1-action/turn budget and delays the claim) and
// claims the instant its union-find connects (1,1)-(N,N). Expected turns
// ~ f*E/(K-1) + flush lag, worst case ~ E/(K-1)+75, vs E/K full scan.

static int idBits() {
    int b = 1;
    while ((1LL << b) < E) b++;
    return b;
}

static void bandWorker() {
    vector<int> order(E);
    iota(order.begin(), order.end(), 0);
    vector<int> key(E);
    for (long long i = 0; i < E; i++) {
        auto [u, v] = eRooms[i];
        int bu = abs(u / (int)m - u % (int)m);
        int bv = abs(v / (int)m - v % (int)m);
        int band = min(bu, bv);
        int prog = u / (int)m + u % (int)m;
        key[i] = (band << 20) | prog;   // prog < 2m <= 502, ample headroom
    }
    stable_sort(order.begin(), order.end(),
                [&](int a, int b) { return key[a] < key[b]; });

    UF uf((int)(m * m));
    const int bits = idBits();
    const long long W = K - 1;
    const long long maxIds = (6 * L) / bits;
    // Cadence trade-off: each send costs the worker a query turn, so long
    // cadences maximize coverage; the leader's claim lags by ~cadence/2.
    // 64 also keeps the aggregate message rate (W/64 <= 0.77) under the
    // leader's 1 receive/turn budget. Measured better than shorter values.
    // Endgame: the corner connection lands at 0.47-0.90E of the band order,
    // so once the strided scan enters that window a shorter cadence (still
    // under the receive budget) cuts the claim lag; before it, long is free.
    const long long flushSlow = 64;
    const long long flushFast = max(W + 10, (long long)24);
    const long long hotPos = (E * 2) / 5;
    BitWriter bw;
    // Stagger flush phases across workers so reports trickle in instead of
    // arriving in synchronized bursts against the leader's 1 receive/turn.
    long long nIds = 0, lastFlush = -(((ID - 1) * flushSlow) / W), turn = 0;
    auto flushMsg = [&]() {
        if (nIds == 0) return;
        bw.pad();
        ask("> 0 " + bw.buf);
        turn++;
        bw.buf.clear();
        nIds = 0;
        lastFlush = turn;
    };

    for (long long t = ID - 1; t < E; t += W) {
        long long flushEvery = (t >= hotPos && flushFast < flushSlow)
                                   ? flushFast : flushSlow;
        if (nIds >= maxIds || (nIds > 0 && turn - lastFlush >= flushEvery))
            flushMsg();
        int id = order[t];
        auto [u, v] = eRooms[id];
        if (uf.same(u, v)) continue;    // acyclicity: must be a wall, skip
        turn++;
        if (queryEdge(id)) {
            uf.unite(u, v);
            bw.push((unsigned)id, bits);
            nIds++;
        }
    }
    flushMsg();
    say("halt");
}

static void bandLeader() {
    UF uf((int)(m * m));
    const int bits = idBits();
    long long S = N + 2;
    vector<char> open = roomGrid();

    const int cornerA = 0, cornerB = (int)(m * m - 1);
    while (true) {
        string r = ask("< ?");
        if (r == "- -") continue;
        size_t sp = r.find(' ');
        string body = r.substr(sp + 1);
        int acc = 0, accn = 0;
        long long got = 0, total = (long long)(6 * body.size()) / bits;
        for (char ch : body) {
            int v = ch - '0';
            for (int b = 5; b >= 0; b--) {
                acc = (acc << 1) | ((v >> b) & 1);
                if (++accn == bits) {
                    if (got < total) {
                        int id = acc;
                        open[(long long)edges[id].first * S + edges[id].second] = 1;
                        uf.unite(eRooms[id].first, eRooms[id].second);
                        got++;
                    }
                    acc = accn = 0;
                }
            }
        }
        if (uf.same(cornerA, cornerB)) {
            claimPath(open);
            return;
        }
    }
}

// ---------------- adaptive band (v08): ellipse-pruned scan ----------------
// Gate: enough scanners to amortize the relay duty, enough maze that the
// hot map arrives while most of the scan remains. The 4-bit map pays from
// K=8 and m=60 up; below m=60 games end before the map discriminates.
static bool bandAdaptive() {
#ifdef V3TUNE
    if (getenv("V8_OFF")) return false;
#endif
    return K >= 8 && m >= 60;
}

constexpr int HGRID = 16;        // priority-map cells per side
constexpr int HLVL = 16;         // gapSum shell levels (4 bits/cell)
static long long epochParam() {  // map recompute/broadcast cadence (turns)
#ifdef V3TUNE
    if (const char *e = getenv("V8_EPOCH")) return atoll(e);
#endif
    return 96;
}
static int stepParam() {
#ifdef V3TUNE
    if (const char *e = getenv("V11_STEP")) return atoi(e);
#endif
    return 15;                   // gapSum shell width, in BFS steps
}

// Broadcast tree over scanner indices s = ID-1: the leader feeds s=0 and
// s=1; children of s are 2s+2 and 2s+3. A depth-d node polls at phase
// 6d-4, two turns after its parent's forwards land, so its one poll per
// epoch always hits (leader sends at phases 0,1; forwards at hit+1, +2).
static int scanDepth(int s) {
    int d = 1;
    while (s >= 2) { s = (s - 2) / 2; d++; }
    return d;
}

static int coarseCell(int room) {
    int i = room / (int)m, j = room % (int)m;
    return (int)((long long)i * HGRID / m) * HGRID +
           (int)((long long)j * HGRID / m);
}

// Leader (agent 0). As in plain band it drains reports and claims on
// corner connection, but reports now carry typed records (walls too), so
// it can maintain the closed global picture and broadcast, every EPOCH
// turns, each coarse cell's min wall-aware distA+distB above the global
// minimum in STEP-room shells — the gradient of the ellipse the corner
// path must stay inside.
static void bandLeaderAdaptive() {
    const int rbits = idBits() + 1;
    long long S = N + 2;
    vector<char> open = roomGrid();
    vector<int8_t> pst(E, 0);      // 0 unknown, 1 open, 2 wall
    UF uf((int)(m * m)), duf(FOUT + 1);
    bool dirty = true;
    const int step = stepParam();
    const int cornerA = 0, cornerB = (int)(m * m - 1);

    auto closure = [&]() {
        bool ch = true;
        while (ch) {
            ch = false;
            for (int e = 0; e < E; e++)
                if (!pst[e]) {
                    auto [u, v] = eRooms[e];
                    if (uf.same(u, v)) {
                        pst[e] = 2;
                        duf.unite(eFaces[e].first, eFaces[e].second);
                        ch = true;
                    } else if (duf.same(eFaces[e].first, eFaces[e].second)) {
                        pst[e] = 1;
                        uf.unite(u, v);
                        open[(long long)edges[e].first * S + edges[e].second] = 1;
                        ch = true;
                    }
                }
        }
    };

    const int INF = 1 << 29;
    vector<int> dA, dB;
    // BFS from the corner's open component; picture walls block, unknown
    // edges pass. Inferred walls are sound, so the true path's rooms are
    // never excluded from the ellipse.
    auto bfs = [&](int corner, vector<int> &dist) {
        dist.assign(m * m, INF);
        deque<int> q;
        for (int r = 0; r < (int)(m * m); r++)
            if (uf.same(r, corner)) { dist[r] = 0; q.push_back(r); }
        while (!q.empty()) {
            int c = q.front(); q.pop_front();
            for (int d = 0; d < 4; d++) {
                int e = eidOf[c][d];
                if (e < 0 || pst[e] == 2) continue;
                auto [u, v] = eRooms[e];
                int nc = (u == c) ? v : u;
                if (dist[nc] > dist[c] + 1) { dist[nc] = dist[c] + 1; q.push_back(nc); }
            }
        }
    };

    auto buildMap = [&]() {
        bfs(cornerA, dA); bfs(cornerB, dB);
        int minSum = INF;
        vector<int> cellMin(HGRID * HGRID, INF);
        for (int r = 0; r < (int)(m * m); r++)
            if (dA[r] < INF && dB[r] < INF) {
                int s = dA[r] + dB[r];
                minSum = min(minSum, s);
                int c = coarseCell(r);
                cellMin[c] = min(cellMin[c], s);
            }
        BitWriter bw;
        for (int c = 0; c < HGRID * HGRID; c++) {
            int lvl = HLVL - 1;
            if (minSum < INF && cellMin[c] < INF)
                lvl = min(HLVL - 1, (cellMin[c] - minSum) / step);
            bw.push((unsigned)lvl, 4);
        }
        bw.pad();
        return bw.buf;
    };

    long long turn = 0;
    const long long EPOCH = epochParam();
    string mapMsg;
    for (;;) {
        long long ph = turn % EPOCH;
        if (ph == 0) {
            if (dirty) { closure(); dirty = false; }
            mapMsg = buildMap();
        }
        if (ph <= 1) {
            ask("> " + to_string(ph + 1) + " " + mapMsg);  // agents 1, 2
            turn++;
            continue;
        }
        string r = ask("< ?");
        turn++;
        if (r == "- -") continue;
        size_t sp = r.find(' ');
        string body = r.substr(sp + 1);
        int acc = 0, accn = 0;
        long long got = 0, total = (long long)(6 * body.size()) / rbits;
        for (char ch : body) {
            int v = ch - '0';
            for (int b = 5; b >= 0; b--) {
                acc = (acc << 1) | ((v >> b) & 1);
                if (++accn == rbits) {
                    if (got < total) {
                        int id = acc >> 1;
                        if (!pst[id]) {
                            pst[id] = (acc & 1) ? 1 : 2;
                            if (acc & 1) {
                                uf.unite(eRooms[id].first, eRooms[id].second);
                                open[(long long)edges[id].first * S +
                                     edges[id].second] = 1;
                            } else {
                                duf.unite(eFaces[id].first, eFaces[id].second);
                            }
                            dirty = true;
                        }
                        got++;
                    }
                    acc = accn = 0;
                }
            }
        }
        if (uf.same(cornerA, cornerB)) {
            // The connecting edge may be dual-inferred rather than reported,
            // so close the picture before extracting the path.
            closure();
            claimPath(open);
            return;
        }
    }
}

// Workers (agents 1..K-1). The v07 band worker plus: typed records (walls
// too) in the reports, one poll per epoch for the priority map, forwarding
// it to two tree children, and lowest-level-first slice order (band order
// within a level). Higher levels are deferred, never dropped, so coverage
// and the claim stay exactly as sound as plain band; with an absent or
// uniform map this degenerates to v07 order.
static void bandScanner() {
    vector<int> order(E);
    iota(order.begin(), order.end(), 0);
    vector<int> key(E);
    for (long long i = 0; i < E; i++) {
        auto [u, v] = eRooms[i];
        int bu = abs(u / (int)m - u % (int)m);
        int bv = abs(v / (int)m - v % (int)m);
        int band = min(bu, bv);
        int prog = u / (int)m + u % (int)m;
        key[i] = (band << 20) | prog;
    }
    stable_sort(order.begin(), order.end(),
                [&](int a, int b) { return key[a] < key[b]; });

    const long long W2 = K - 1;
    const int sid = (int)ID - 1;
    vector<int> slice;
    for (long long t = sid; t < E; t += W2) slice.push_back(order[t]);

    UF uf((int)(m * m));
    const int rbits = idBits() + 1;
    const long long maxRec = (6 * L) / rbits;
    const long long flushSlow = 64;
    const long long flushFast = max(W2 + 10, (long long)24);
    const long long hotPos = (E * 2) / 5;
    const int c1 = 2 * sid + 3, c2 = 2 * sid + 4;  // tree children (agent ids)
    const long long EPOCH = epochParam();
    const int pollPhase = (int)((6 * scanDepth(sid) - 4) % EPOCH);

    vector<char> lvl(HGRID * HGRID, 0);  // all-hottest until a map arrives
    auto edgeLvl = [&](int e) {
        return min(lvl[coarseCell(eRooms[e].first)],
                   lvl[coarseCell(eRooms[e].second)]);
    };

    BitWriter bw;
    long long nRec = 0, nOpen = 0, lastFlush = -((sid * flushSlow) / W2), turn = 0;
    string fwdMsg;
    int fwdPend = 0;
    size_t cursor = 0;
    long long nDone = 0;

    auto flushMsg = [&]() {
        if (nRec == 0) return;
        bw.pad();
        ask("> 0 " + bw.buf);
        turn++;
        bw.buf.clear();
        nRec = nOpen = 0;
        lastFlush = turn;
    };

    for (;;) {
        while (cursor < slice.size()) {
            int e = slice[cursor];
            if (e >= 0) {
                auto [u, v] = eRooms[e];
                if (!uf.same(u, v)) break;
                nDone++;               // acyclicity: must be a wall, skip
            }
            cursor++;
        }
        if (cursor >= slice.size()) break;

        if (turn % EPOCH == pollPhase) {
            string r = ask("< ?");
            turn++;
            if (r != "- -") {
                size_t sp = r.find(' ');
                fwdMsg = r.substr(sp + 1);
                int acc = 0, accn = 0, bi = 0;
                for (char ch : fwdMsg) {
                    int v = ch - '0';
                    for (int b = 5; b >= 0 && bi < HGRID * HGRID; b--) {
                        acc = (acc << 1) | ((v >> b) & 1);
                        if (++accn == 4) {
                            lvl[bi++] = (char)acc;
                            acc = accn = 0;
                        }
                    }
                }
                fwdPend = 2;
            }
            continue;
        }
        if (fwdPend) {
            int child = (fwdPend == 2) ? c1 : c2;
            fwdPend--;
            if (child < (int)K) {
                ask("> " + to_string(child) + " " + fwdMsg);
                turn++;
            }
            continue;
        }
        // Endgame fast cadence keys on opens: only opens can complete the
        // leader's claim, and wall-only messages would just deepen its
        // endgame queue behind the open that ends the game.
        bool due = (nDone * W2 >= hotPos && flushFast < flushSlow)
                       ? (nOpen > 0 && turn - lastFlush >= flushFast)
                       : (nRec > 0 && turn - lastFlush >= flushSlow);
        if (nRec >= maxRec || due) {
            flushMsg();
            continue;
        }
        int pick = -1, pickLvl = HLVL;
        size_t pickIdx = 0;
        for (size_t i = cursor; i < slice.size(); i++) {
            int e = slice[i];
            if (e < 0) continue;
            auto [u, v] = eRooms[e];
            if (uf.same(u, v)) { slice[i] = -1; nDone++; continue; }
            int l = edgeLvl(e);
            if (l < pickLvl) {
                pick = e; pickIdx = i; pickLvl = l;
                if (l == 0) break;
            }
        }
        if (pick < 0) break;
        turn++;
        bool op = queryEdge(pick);
        slice[pickIdx] = -1;
        nDone++;
        bw.push((unsigned)((pick << 1) | (op ? 1 : 0)), rbits);
        nRec++;
        if (op) {
            nOpen++;
            uf.unite(eRooms[pick].first, eRooms[pick].second);
        }
    }
    flushMsg();
    say("halt");
}

// ---------------- full-map mode (v2) ----------------

static void fullmapRun() {
    // Partition: leader (agent 0) takes a reduced share to offset the turns
    // it spends receiving worker messages; balanced iteratively.
    const long long bitsPerMsg = 6 * L;
    const long long W = K - 1;
    long long El = E;
    vector<long long> cnt(K, 0);
    if (W > 0) {
        long long M = (E + bitsPerMsg - 1) / bitsPerMsg;
        long long Ew = 0;
        for (int iter = 0; iter < 4; iter++) {
            Ew = (E + M + K - 1) / K;
            El = E - W * Ew;
            if (El < 0) El = 0;
            long long rest = E - El, base = rest / W, rem = rest % W;
            M = 0;
            for (long long w = 0; w < W; w++) {
                long long c = base + (w < rem ? 1 : 0);
                M += (c + bitsPerMsg - 1) / bitsPerMsg;
            }
        }
        cnt[0] = El;
        long long rest = E - El, base = rest / W, rem = rest % W;
        for (long long w = 0; w < W; w++) cnt[w + 1] = base + (w < rem ? 1 : 0);
    } else {
        cnt[0] = E;
    }
    vector<long long> start(K + 1, 0);
    for (long long a = 0; a < K; a++) start[a + 1] = start[a] + cnt[a];

    // Aggregation tree (W >= 16): workers report to ceil(sqrt(W)) group
    // heads (contiguous id blocks, head = lowest id); each head forwards
    // its group's reports concatenated in id order. The leader's serial
    // 1-receive/turn drain shrinks from W messages to ~sqrt(W) streams;
    // below the gate the drain is short and the extra hop costs more.
    const long long W2 = K - 1;
    const bool aggr = W2 >= 16;
    long long G = 0;
    vector<long long> gLo, gHi;        // group g = worker ids [gLo, gHi)
    vector<long long> grpOf(K, -1);
    if (aggr) {
        while (G * G < W2) G++;
        long long base = W2 / G, rem = W2 % G, id = 1;
        for (long long g = 0; g < G; g++) {
            long long sz = base + (g < rem ? 1 : 0);
            gLo.push_back(id);
            gHi.push_back(id + sz);
            for (long long i = id; i < id + sz; i++) grpOf[i] = g;
            id += sz;
        }
    }
    auto rptChars = [&](long long a) { return (cnt[a] + 5) / 6; };

    UF uf((int)(m * m));
    auto probe = [&](long long i) -> int {
        auto [u, v] = eRooms[i];
        if (uf.same(u, v)) return 0;  // would form a cycle -> must be wall
        if (queryEdge((int)i)) {
            uf.unite(u, v);
            return 1;
        }
        return 0;
    };

    if (ID != 0) {
        long long lo = start[ID], hi = start[ID + 1];
        BitWriter bw;
        if (!aggr) {
            for (long long i = lo; i < hi; i++) {
                bw.push((unsigned)probe(i), 1);
                if ((long long)bw.buf.size() == L) {
                    ask("> 0 " + bw.buf);
                    bw.buf.clear();
                }
            }
            bw.pad();
            if (!bw.buf.empty()) ask("> 0 " + bw.buf);
            say("halt");
            return;
        }
        for (long long i = lo; i < hi; i++) bw.push((unsigned)probe(i), 1);
        bw.pad();
        long long g = grpOf[ID], head = gLo[g];
        if (ID != head) {
            for (size_t p = 0; p < bw.buf.size(); p += (size_t)L)
                ask("> " + to_string(head) + " " + bw.buf.substr(p, (size_t)L));
            say("halt");
            return;
        }
        vector<string> got(gHi[g] - gLo[g]);
        got[0] = bw.buf;
        long long need = 0, have = 0;
        for (long long a = gLo[g] + 1; a < gHi[g]; a++) need += rptChars(a);
        while (have < need) {
            string r = ask("< ?");
            if (r == "- -") continue;
            size_t sp = r.find(' ');
            long long s = stoll(r.substr(0, sp));
            string body = r.substr(sp + 1);
            got[s - gLo[g]] += body;
            have += (long long)body.size();
        }
        string all;
        for (auto &x : got) all += x;
        for (size_t p = 0; p < all.size(); p += (size_t)L)
            ask("> 0 " + all.substr(p, (size_t)L));
        say("halt");
        return;
    }

    vector<char> bit(E, 0);
    for (long long i = 0; i < El; i++) bit[i] = (char)probe(i);
    long long remaining = 0;   // expected report chars, all workers
    for (long long a = 1; a < K; a++) remaining += rptChars(a);
    if (!aggr) {
        vector<long long> nextBit(K, 0);
        for (long long a = 1; a < K; a++) nextBit[a] = start[a];
        while (remaining > 0) {
            string r = ask("< ?");
            if (r == "- -") continue;
            size_t sp = r.find(' ');
            long long s = stoll(r.substr(0, sp));
            string body = r.substr(sp + 1);
            for (char ch : body) {
                int v = ch - '0';
                for (int k = 5; k >= 0; k--) {
                    if (nextBit[s] < start[s + 1]) bit[nextBit[s]++] = (v >> k) & 1;
                }
            }
            remaining -= (long long)body.size();
        }
    } else {
        // Each head's stream is its group's reports concatenated in id
        // order (its own first); decode positionally with per-head cursors.
        vector<long long> curMem(G), curChar(G, 0);
        for (long long g = 0; g < G; g++) curMem[g] = gLo[g];
        while (remaining > 0) {
            string r = ask("< ?");
            if (r == "- -") continue;
            size_t sp = r.find(' ');
            long long s = stoll(r.substr(0, sp));
            long long g = grpOf[s];
            string body = r.substr(sp + 1);
            for (char ch : body) {
                while (curChar[g] >= rptChars(curMem[g])) {
                    curMem[g]++;
                    curChar[g] = 0;
                }
                long long a = curMem[g];
                long long bp = start[a] + curChar[g] * 6;
                int v = ch - '0';
                for (int k = 5; k >= 0; k--) {
                    long long idx = bp + (5 - k);
                    if (idx < start[a + 1]) bit[idx] = (char)((v >> k) & 1);
                }
                curChar[g]++;
            }
            remaining -= (long long)body.size();
        }
    }

    long long S = N + 2;
    vector<char> open = roomGrid();
    for (long long i = 0; i < E; i++)
        if (bit[i]) open[(long long)edges[i].first * S + edges[i].second] = 1;
    claimPath(open);
}

int main() {
    if (!(cin >> N >> K >> ID >> L)) return 0;
    cin.ignore(numeric_limits<streamsize>::max(), '\n');

    if (N == 1) {
        say(ID == 0 ? "!" : "halt");
        return 0;
    }

    m = (N + 1) / 2;
    buildEdges();

    switch (pickMode()) {
        case FRONTIER: ID == 0 ? frontierLeader() : frontierWorker(); break;
        case BAND:
            if (!bandAdaptive()) ID == 0 ? bandLeader() : bandWorker();
            else ID == 0 ? bandLeaderAdaptive() : bandScanner();
            break;
        case FULLMAP: fullmapRun(); break;
    }
    return 0;
}