// 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.
//
// 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.
enum Mode { FRONTIER, BAND, FULLMAP };

static Mode pickMode() {
    int cut = 3;
    if (m >= 40) {
        static const int A[][2] = {{40, 7},  {54, 9},   {61, 10}, {75, 9},
                                   {123, 14}, {179, 12}, {251, 21}};
        const int n = (int)(sizeof(A) / sizeof(A[0]));
        cut = 21;
        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;
    auto seedPrio = [&](int f, int tag) {
        int i = f / (int)m, j = f % (int)m;
        return 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

    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;

        // 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 a seed from the lagging tree
                // (the one whose best frontier is furthest from its target).
                int t0 = 0;
                if (poolT[0].empty()) t0 = 1;
                else if (!poolT[1].empty() &&
                         get<0>(poolT[1].top()) > get<0>(poolT[0].top()))
                    t0 = 1;
                auto s = popSeed(t0);
                if (!s) s = popSeed(1 - t0);
                if (!s) break;
                auto [p, sq, e, orient, tg] = *s;
                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;
    long long nIds = 0, lastFlush = 0, 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;
        }
    }
}

// ---------------- 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];

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

    vector<char> bit(E, 0);
    for (long long i = 0; i < El; i++) bit[i] = (char)probe(i);
    vector<long long> nextBit(K, 0);
    long long remaining = 0;   // expected report chars, all workers
    for (long long a = 1; a < K; a++) {
        nextBit[a] = start[a];
        remaining += (cnt[a] + 5) / 6;
    }
    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();
    }

    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: ID == 0 ? bandLeader() : bandWorker(); break;
        case FULLMAP: fullmapRun(); break;
    }
    return 0;
}