// MCC 2026 D. Datacenter Imprisonment — agent v2 "adaptive bidirectional frontier".
//
// Generator facts exploited (see merlin-source/src/maze.rs):
//   * Rooms at odd/odd cells are ALWAYS empty; even/even cells are ALWAYS walls.
//     Only door cells (one even coordinate) are unknown: D = 2*m*(m-1), m=(N+1)/2.
//   * Empty cells form a tree => any simple path over confirmed-open doors is THE
//     unique path; claim the moment the corner rooms connect.
//   * Tree inference: an unknown door inside one known component is CLOSED (cycle
//     rule); a room with no open door and exactly one unknown door forces it OPEN
//     (room rule, cascades along corridors).
//   * Lockstep timing is fully deterministic: every agent derives the same epoch
//     schedule, so gossip reads never miss.
//
// Protocol (all K agents symmetric, replicated state S):
//   Repeat epochs until the corners connect:
//     boundary: apply everyone's bits, run inference closure, recompute the door
//       ordering L = bidirectional A* potential (min over orientations of
//       ds[a]+dg[b]+1, BFS through non-closed doors from both corner components;
//       tie-break: distance to the nearest component, then door id).
//     work phase (W_e rounds): agent j queries L[j], L[j+K], ... — its slice of
//       the hottest doors; the speculative tail doubles as prefetch. An agent
//       whose own bit connects the corners claims IMMEDIATELY mid-epoch.
//     sync phase: allgather of everyone's result bits (positions map to doors
//       deterministically, so only raw bits travel): full mesh for K in {2,3,5},
//       fold + recursive-doubling hypercube + unfold otherwise; multi-message
//       transfers when a payload exceeds MAX_MSG_LEN.
//   Fallback: any protocol anomaly (missed gossip read, bad header) drops the
//   agent into SOLO mode — self-scan by potential order, still correct.

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cstdint>
#include <climits>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;
typedef long long ll;

// ---------------- problem geometry ----------------
static int N, K, ID;
static ll MSGLEN;
static int m;      // rooms per side
static int D;      // doors = 2*m*(m-1)
static int HD;     // horizontal doors = m*(m-1)
static int LAMBDA = 2;        // frontier-nearness weight in the door ordering
static int UNKW = 1;          // step cost through an unknown door (open door = 1)
static int BLOCKS = 1;        // 1: agent gets a contiguous slice of L; 0: round-robin
static int RACE_POT = 0;      // endgame race disabled: duplicated walkers lose to epochs
static int SPARES = 1;        // walk into the spare tail after own block is decided
static int MU = 0;            // Bayesian prior weight in the ordering (0 = off)
static int TERRM = 1;         // territory mode master switch (K in [3,7], D <= TERR_DMAX)
static int TERR_KMAX = 7;     // max team size for territory mode
static int TERR_DMAX = 32000; // CPU cap: per-query reorder is O(cone+D); also D <= 6200*K
static int TERR_W = 0;        // own adaptive queries per epoch (0 = auto: 48 at K=3, else 32)
static int CHAIN = 0;         // 1: depth-speculation L (corridor chains before band)
static int CH_POT = 1 << 30;  // build chains only when g_potMin <= CH_POT
static int CH_FRAC = 50;      // % of takeMax the chain part may fill
static int CH_GEN = 9;        // max branch generation (0 = main chain only)
static int CH_HEDGE = 0;      // 1: branch only where the passed door is unknown
static int CH_CAPX = 0;       // >0: absolute chain cap = CH_CAPX * (potMin + 8)
static int CH_EW = 0;         // >0: endgame epoch width cap (when potMin <= CH_POT)
static int CH_STRIKES = 2;    // chain epochs without potMin progress before kill
static ll g_chLastPot = -1;   // potMin recorded at the last chain epoch
static int g_chStrikes = 0, g_chFiredLast = 0;
// P(open)*256 per local door pattern (learned offline from generator mazes);
// index: canonical pair of room codes ((deg-2)*25 + open*5 + closed)
#define NPAT (75 * 75)
static unsigned char PRI[NPAT]; // filled by initPri(); 128 = no information
// learned from 1.15M queries over 18 generator mazes (see NOTES.md)
static void initPriLearned();
static void initPri() { for (int i = 0; i < NPAT; i++) PRI[i] = 128; initPriLearned(); }

static ll g_candTotal = 0;    // candidates seen by the last order() call
static ll g_potMin = 0;       // optimistic start-goal gap after the last order()
static ll g_chainLen = 0;     // chain doors in the last orderChain() L
static int WCAP_OVERRIDE = 0; // simulator knob

static inline void doorCell(int d, int& r, int& c) {
    if (d < HD) { int i = d / (m - 1), j = d % (m - 1); r = 2 * i + 1; c = 2 * j + 2; }
    else        { int v = d - HD; int i = v / m, j = v % m; r = 2 * i + 2; c = 2 * j + 1; }
}
static inline void doorRooms(int d, int& a, int& b) {
    if (d < HD) { int i = d / (m - 1), j = d % (m - 1); a = i * m + j; b = a + 1; }
    else        { int v = d - HD; int i = v / m, j = v % m; a = i * m + j; b = a + m; }
}
static inline int roomDoors(int room, int out[4]) {
    int i = room / m, j = room % m, n = 0;
    if (j + 1 < m) out[n++] = i * (m - 1) + j;
    if (j > 0)     out[n++] = i * (m - 1) + j - 1;
    if (i + 1 < m) out[n++] = HD + i * m + j;
    if (i > 0)     out[n++] = HD + (i - 1) * m + j;
    return n;
}

// ---------------- knowledge core (same logic in agent and simulator) ----------------
struct Core {
    vector<uint8_t> st;                  // 0 unknown, 1 closed, 2 open
    vector<int> dsu;
    vector<uint8_t> openCnt, unknownCnt; // per room
    vector<int> cascade;                 // rooms to recheck for the forced-open rule
    int s0 = 0, g0 = 0;

    void init() {
        st.assign(D > 0 ? D : 1, 0);
        dsu.resize(m * m);
        for (int i = 0; i < m * m; i++) dsu[i] = i;
        openCnt.assign(m * m, 0);
        unknownCnt.assign(m * m, 0);
        for (int r = 0; r < m * m; r++) {
            int dd[4]; unknownCnt[r] = (uint8_t)roomDoors(r, dd);
        }
        s0 = 0; g0 = m * m - 1;
    }
    int find(int x) { while (dsu[x] != x) { dsu[x] = dsu[dsu[x]]; x = dsu[x]; } return x; }
    void unite(int a, int b) { a = find(a); b = find(b); if (a != b) dsu[a] = b; }
    bool connected() { return find(s0) == find(g0); }

    void apply(int d, bool open) {
        if (st[d]) return;
        st[d] = open ? 2 : 1;
        int a, b; doorRooms(d, a, b);
        unknownCnt[a]--; unknownCnt[b]--;
        if (open) { openCnt[a]++; openCnt[b]++; unite(a, b); }
        else { cascade.push_back(a); cascade.push_back(b); }
    }
    // forced-open rule: a room with 0 open doors and exactly 1 unknown door
    void drainCascade() {
        while (!cascade.empty()) {
            int r = cascade.back(); cascade.pop_back();
            if (openCnt[r] != 0 || unknownCnt[r] != 1) continue;
            int dd[4], n = roomDoors(r, dd);
            for (int i = 0; i < n; i++)
                if (!st[dd[i]]) { apply(dd[i], true); break; }
        }
    }
    // inference closure: forced-open cascade (the cycle rule is applied lazily
    // to candidate doors inside order(), which is where it matters)
    void closure() { drainCascade(); }

    // local evidence pattern of an unknown door: states of both endpoint rooms
    int patId(int d) {
        int a, b; doorRooms(d, a, b);
        int dd[4];
        int degA = roomDoors(a, dd), degB = roomDoors(b, dd);
        int ca = degA - openCnt[a] - unknownCnt[a], cb = degB - openCnt[b] - unknownCnt[b];
        int codeA = (degA - 2) * 25 + openCnt[a] * 5 + ca;
        int codeB = (degB - 2) * 25 + openCnt[b] * 5 + cb;
        if (codeA > codeB) { int t = codeA; codeA = codeB; codeB = t; }
        return codeA * 75 + codeB;
    }

    // bidirectional-A* ordering of unknown doors; top `takeMax` door ids.
    // Also applies the cycle rule lazily to every candidate it inspects.
    vector<int> ds, dg, seeds;
    ll lastPotMin = -1;
    void order(size_t takeMax, vector<int>& L) {
        orderInner(takeMax, L,
                   lastPotMin >= 0 ? (int)min((ll)INT_MAX / 8, 2 * lastPotMin + 32) : INT_MAX / 4);
        if (L.empty()) orderInner(takeMax, L, INT_MAX / 4); // over-pruned: redo full
        lastPotMin = g_potMin;
    }
    // dijkstra fields only (for territory-mode wedge scoring between full
    // reorders); L, potMin and the lazy cycle sweep are left untouched
    void orderFields() {
        dijCap = lastPotMin >= 0 ? (int)min((ll)INT_MAX / 8, 2 * lastPotMin + 32) : INT_MAX / 4;
        const int INF = INT_MAX / 4;
        ds.assign(m * m, INF); dg.assign(m * m, INF);
        seeds.clear();
        int rootS = find(s0);
        for (int r = 0; r < m * m; r++) if (find(r) == rootS) seeds.push_back(r);
        dijkstra(ds, seeds);
        seeds.clear();
        int rootG = find(g0);
        for (int r = 0; r < m * m; r++) if (find(r) == rootG) seeds.push_back(r);
        dijkstra(dg, seeds);
    }
    void orderInner(size_t takeMax, vector<int>& L, int cap) {
        L.clear();
        dijCap = cap;
        const int INF = INT_MAX / 4;
        ds.assign(m * m, INF); dg.assign(m * m, INF);
        seeds.clear();
        int rootS = find(s0), rootG = find(g0);
        for (int r = 0; r < m * m; r++) if (find(r) == rootS) seeds.push_back(r);
        dijkstra(ds, seeds);
        seeds.clear();
        for (int r = 0; r < m * m; r++) if (find(r) == rootG) seeds.push_back(r);
        dijkstra(dg, seeds);

        struct Cand { ll score; int d; };
        static vector<Cand> cand;
        cand.clear();
        g_potMin = LLONG_MAX;
        for (int d = 0; d < D; d++) {
            if (st[d]) continue;
            int a, b; doorRooms(d, a, b);
            int ra = find(a), rb = find(b);
            if (ra == rb) { apply(d, false); continue; } // lazy cycle rule
            ll p1 = (ll)ds[a] + dg[b], p2 = (ll)ds[b] + dg[a];
            ll pot = min(p1, p2) + UNKW;
            if (pot >= INF) continue; // cannot lie on any start-goal path
            if (pot < g_potMin) g_potMin = pot;
            int nr = min(min(ds[a], ds[b]), min(dg[a], dg[b]));
            ll sc = (pot + (ll)LAMBDA * nr) * 1024;
            if (MU) sc -= (ll)MU * PRI[patId(d)];
            cand.push_back({ sc, d });
        }
        drainCascade(); // lazy closures may force opens
        g_candTotal = (ll)cand.size();
        auto cmp = [](const Cand& x, const Cand& y) {
            if (x.score != y.score) return x.score < y.score;
            return x.d < y.d;
        };
        size_t take = min(takeMax, cand.size());
        if (take < cand.size())
            nth_element(cand.begin(), cand.begin() + take, cand.end(), cmp);
        sort(cand.begin(), cand.begin() + take, cmp);
        for (size_t i = 0; i < take; i++) {
            if (st[cand[i].d]) continue; // may have been forced open by the cascade
            L.push_back(cand[i].d);
        }
    }
    // depth-speculation ordering: front of L = unknown doors of the best
    // optimistic corridor (greedy dg-descent from the start component) plus
    // branch corridors (BFS over equal-progress descent alternatives), then
    // the usual band as filler. Fully deterministic — replicated on all agents.
    void orderChain(size_t takeMax, vector<int>& L) {
        order(takeMax, L);
        g_chainLen = 0;
        if (g_chFiredLast) { // false-lead detector: chains must move potMin down
            if (g_potMin >= g_chLastPot) g_chStrikes++;
            else g_chStrikes = 0;
            g_chFiredLast = 0;
        }
        if (!CHAIN || L.empty()) return;
        if (g_potMin > (ll)CH_POT || g_potMin >= INT_MAX / 8) return;
        if (g_chStrikes >= CH_STRIKES) return; // corridor bets keep dying: stay band
        static vector<uint8_t> taken;
        taken.assign(D, 0);
        size_t budget = takeMax * (size_t)CH_FRAC / 100;
        if (CH_CAPX > 0) budget = min(budget, (size_t)CH_CAPX * ((size_t)g_potMin + 8));
        if (budget < 1) budget = 1;
        vector<int> CL;
        struct Br { int room, door, gen; };
        vector<Br> q;
        size_t qh = 0;
        ll steps = 0, stepCap = 32 * (ll)takeMax + 4096;
        auto stepDoor = [&](int v, int d) -> int {
            int a, b; doorRooms(d, a, b);
            if (!st[d] && !taken[d] && CL.size() < budget) { taken[d] = 1; CL.push_back(d); }
            return a == v ? b : a;
        };
        auto descend = [&](int v, int gen) {
            while (dg[v] > 0 && CL.size() < budget && steps < stepCap) {
                steps++;
                int dd[4], n = roomDoors(v, dd);
                int best = -1;
                for (int i = 0; i < n; i++) {
                    int d = dd[i];
                    if (st[d] == 1) continue;
                    int a, b; doorRooms(d, a, b);
                    int o = (a == v) ? b : a;
                    int w = (st[d] == 2) ? 1 : UNKW;
                    if (dg[o] != dg[v] - w) continue; // not an optimal continuation
                    if (best < 0) best = d;
                    else if (gen < CH_GEN && q.size() < 8 * budget + 64)
                        q.push_back({ v, d, gen + 1 });
                }
                if (best < 0) break; // field went stale (lazy closures): stop trace
                if (CH_HEDGE && st[best] == 2) { // known-open step: drop its siblings
                    while (!q.empty() && q.back().room == v) q.pop_back();
                }
                v = stepDoor(v, best);
            }
        };
        int rootS = find(s0), x = -1, bestDg = INT_MAX / 8;
        for (int r = 0; r < m * m; r++)
            if (dg[r] < bestDg && find(r) == rootS) { bestDg = dg[r]; x = r; }
        if (x < 0) return;
        descend(x, 0);
        while (qh < q.size() && qh < 4 * budget && CL.size() < budget && steps < stepCap) {
            Br b = q[qh++];
            descend(stepDoor(b.room, b.door), b.gen);
        }
        if (CL.empty()) return;
        g_chainLen = (ll)CL.size();
        g_chFiredLast = 1;
        g_chLastPot = g_potMin;
        vector<int> out;
        out.reserve(min(takeMax, CL.size() + L.size()));
        for (int d : CL) out.push_back(d);
        for (int d : L) {
            if (out.size() >= takeMax) break;
            if (!taken[d]) out.push_back(d);
        }
        L.swap(out);
    }

    // multi-source dijkstra; open doors cost 1, unknown doors cost UNKW;
    // expansion is pruned at `cap` (the active-cone bound)
    int dijCap = INT_MAX / 4;
    void dijkstra(vector<int>& dist, const vector<int>& sd) {
        // dial's buckets: max edge weight is UNKW
        static vector<vector<int>> buck;
        for (auto& b : buck) b.clear();
        if (buck.empty()) buck.resize(1);
        for (int r : sd) { dist[r] = 0; buck[0].push_back(r); }
        for (size_t cur = 0; cur < buck.size() && (int)cur <= dijCap; cur++) {
            for (size_t h = 0; h < buck[cur].size(); h++) {
                int r = buck[cur][h];
                if (dist[r] != (int)cur) continue;
                int dd[4], n = roomDoors(r, dd);
                for (int i = 0; i < n; i++) {
                    int s = st[dd[i]];
                    if (s == 1) continue; // closed doors block
                    int w = (s == 2) ? 1 : UNKW;
                    int a, b; doorRooms(dd[i], a, b);
                    int o = a == r ? b : a;
                    int nd = (int)cur + w;
                    if (dist[o] > nd) {
                        dist[o] = nd;
                        while ((int)buck.size() <= nd) buck.push_back({});
                        buck[(size_t)nd].push_back(o);
                    }
                }
            }
        }
    }
};

// ---------------- allgather plan (identical on every agent) ----------------
struct Transfer { int from, to; vector<int> set; }; // set: agent ids whose bits move
struct Phase { vector<Transfer> tr; int qmax = 0; bool bidir = false; int rounds = 0; };
struct SyncPlan { vector<Phase> phases; int rounds = 0; };

static int msgsFor(ll bits) { // messages for a payload (1 header char per message)
    ll chars = (bits + 5) / 6;
    ll cap = MSGLEN - 1;
    if (cap < 1) cap = 1;
    ll q = (chars + cap - 1) / cap;
    return (int)(q < 1 ? 1 : q);
}

static SyncPlan buildSyncPlan(const vector<int>& cnt) {
    SyncPlan sp;
    if (K <= 1) return sp;
    auto bitsOf = [&](const vector<int>& s) { ll b = 0; for (int a : s) b += cnt[a]; return b; };
    // Bruck allgather: ceil(log2 K) bidirectional stages for any K.
    // Before stage `step`, agent a holds the cyclic block run [a, a+step);
    // it sends the first min(step, K-step) blocks of its run to (a - step) mod K.
    for (int step = 1; step < K; step *= 2) {
        Phase ph; ph.bidir = true;
        int nb = min(step, K - step);
        for (int a = 0; a < K; a++) {
            Transfer t; t.from = a; t.to = (a - step + K) % K;
            for (int i = 0; i < nb; i++) t.set.push_back((a + i) % K);
            ph.qmax = max(ph.qmax, msgsFor(bitsOf(t.set)));
            ph.tr.push_back(t);
        }
        ph.rounds = 2 * ph.qmax;
        sp.phases.push_back(ph);
    }
    for (auto& ph : sp.phases) sp.rounds += ph.rounds;
    return sp;
}

// work-phase length cap: adaptivity vs sync-overhead trade-off
static int workCap() {
    if (WCAP_OVERRIDE > 0) return WCAP_OVERRIDE;
    if (K == 5 && D > 100000) return 32; // new 30:30 class: W64 was stale on very large low-K maze
    if (K <= 6) return D > 50000 ? 64 : 24; // small team: fresh epochs unless CPU-bound
    if (K >= 7 && K <= 13) return (K == 13 && D > 50000) ? 48 : 24; // low-K losses prefer fresher epochs; K=13 huge regresses
    if (K == 15) return 36; // improves new K=15 rows without score-row regressions
    if (K == 19 && D > 100000) return 20; // light huge maze: avoid stale 48-wide epochs
    if (K == 27) return 64; // 29:20/30:40 prefer fewer epoch boundaries
    if (K == 38 && D > 50000) return 36; // hard huge maze: measured better sync/adaptivity balance
    if (D > 50000) return 48; // huge maze: fewer epoch boundaries (CPU budget)
    if (D < 160 * K) return 48; // tiny maze: ~2 fat epochs beat 3 thin ones
    int w = 256 / K;
    if (w < 32) w = 32;
    return w;
}

// territory mode: door -> owner agent, equal-door anti-diagonal bands
static void terrWedges(vector<int>& wedge) {
    wedge.assign(D, 0);
    vector<pair<int, int>> lv((size_t)D);
    for (int d = 0; d < D; d++) {
        int a, b; doorRooms(d, a, b);
        lv[(size_t)d] = { a / m + a % m + b / m + b % m, d };
    }
    sort(lv.begin(), lv.end());
    for (int i = 0; i < D; i++) wedge[lv[(size_t)i].second] = (int)((ll)i * K / D);
}

// pick the best unknown door of agent `who` inside its wedge (scored exactly
// like order(), on the ds/dg fields of the freshest order() call over `C`);
// falls back to the nearest-wedge entry of the global list L, so agents with
// dry wedges spread out instead of piling onto one global-best door.
static int terrPick(Core& C, const vector<int>& myDoors, int who, const vector<int>& L) {
    const int INF = INT_MAX / 4;
    ll bestSc = LLONG_MAX; int pick = -1;
    for (int d : myDoors) {
        if (C.st[d]) continue;
        int a, b; doorRooms(d, a, b);
        if (C.find(a) == C.find(b)) continue; // cycle rule will kill it
        ll p1 = (ll)C.ds[a] + C.dg[b], p2 = (ll)C.ds[b] + C.dg[a];
        ll pot = min(p1, p2) + UNKW;
        if (pot >= INF) continue;
        int nr = min(min(C.ds[a], C.ds[b]), min(C.dg[a], C.dg[b]));
        ll sc = (pot + (ll)LAMBDA * nr) * 1024;
        if (sc < bestSc) { bestSc = sc; pick = d; }
    }
    if (pick >= 0) return pick;
    // wedge dry: work the global band, offset by agent id so dry agents spread
    for (size_t i = 0; i < L.size(); i++) {
        int d = L[(size_t)who + i < L.size() ? (size_t)who + i : (size_t)who + i - L.size()];
        if (!C.st[d]) return d;
    }
    return -1;
}

static void encodeBits(const vector<uint8_t>& bits, string& chars) {
    size_t n = (bits.size() + 5) / 6;
    size_t base = chars.size();
    chars.resize(base + n, '0');
    for (size_t k = 0; k < bits.size(); k++)
        if (bits[k]) chars[base + k / 6] += (char)(1 << (k % 6));
}

#ifndef LOCAL_SIM
// =====================================================================
// ==============             REAL AGENT MODE            ==============
// =====================================================================
static string g_out;
static void emitLine(const string& s) { g_out += s; g_out += '\n'; }
static void flushOut() {
    if (!g_out.empty()) {
        fwrite(g_out.data(), 1, g_out.size(), stdout);
        fflush(stdout);
        g_out.clear();
    }
}
static bool readLine(string& out) {
    flushOut();
    out.clear();
    char buf[4096];
    while (fgets(buf, sizeof buf, stdin)) {
        out += buf;
        if (!out.empty() && out.back() == '\n') break;
    }
    if (out.empty()) return false;
    while (!out.empty() && (out.back() == '\n' || out.back() == '\r')) out.pop_back();
    return true;
}
#ifdef CPUDBG
#include <sys/resource.h>
static void reportCpu() {
    rusage ru; getrusage(RUSAGE_SELF, &ru);
    fprintf(stderr, "[agent %d] cpu=%.3fs\n", ID,
            ru.ru_utime.tv_sec + ru.ru_utime.tv_usec / 1e6 +
            ru.ru_stime.tv_sec + ru.ru_stime.tv_usec / 1e6);
}
#else
static void reportCpu() {}
#endif
static void dieQuietly() { flushOut(); reportCpu(); exit(0); }

static Core core;

static void claimAndExit() {
    int G = N + 2;
    vector<uint8_t> emp((size_t)G * G, 0);
    for (int i = 0; i < m; i++)
        for (int j = 0; j < m; j++) emp[(size_t)(2 * i + 1) * G + (2 * j + 1)] = 1;
    for (int d = 0; d < D; d++)
        if (core.st[d] == 2) { int r, c; doorCell(d, r, c); emp[(size_t)r * G + c] = 1; }
    int start = 1 * G + 1, goal = N * G + N;
    string path;
    if (start != goal) {
        static const int drr[4] = { -1, 0, 1, 0 }, dcc[4] = { 0, -1, 0, 1 };
        static const char mv[4] = { 'U', 'L', 'D', 'R' };
        vector<int8_t> pdir((size_t)G * G, -1);
        vector<uint8_t> seen((size_t)G * G, 0);
        vector<int> q; q.reserve((size_t)G * G / 2);
        q.push_back(start); seen[start] = 1;
        for (size_t h = 0; h < q.size(); h++) {
            int cur = q[h];
            if (cur == goal) break;
            for (int k = 0; k < 4; k++) {
                int nxt = cur + drr[k] * G + dcc[k];
                if (!seen[nxt] && emp[nxt]) { seen[nxt] = 1; pdir[nxt] = (int8_t)k; q.push_back(nxt); }
            }
        }
        if (!seen[goal]) dieQuietly();
        for (int cur = goal; cur != start;) {
            int k = pdir[cur];
            path += mv[k];
            cur -= drr[k] * G + dcc[k];
        }
        reverse(path.begin(), path.end());
    }
    emitLine("! " + path);
    flushOut();
    reportCpu();
    exit(0);
}

static bool queryDoor(int d) {
    int r, c; doorCell(d, r, c);
    char buf[40]; snprintf(buf, sizeof buf, "? %d %d", r, c);
    emitLine(buf);
    string rep; if (!readLine(rep)) dieQuietly();
    return !rep.empty() && rep[0] == '1';
}
static void idleRound() {
    emitLine(".");
    string rep; if (!readLine(rep)) dieQuietly();
}

// endgame race: every agent walks its own best corridor with instant local
// adaptivity; the rank offset on the first step forces divergence
static void raceRun() {
    vector<int> L;
    bool first = true;
    while (true) {
        if (core.connected()) claimAndExit();
        core.order(first ? (size_t)K + 1 : 1, L);
        if (L.empty()) { idleRound(); continue; }
        int pick = first ? (int)min((size_t)ID, L.size() - 1) : 0;
        first = false;
        int d = L[pick];
        core.apply(d, queryDoor(d));
        core.drainCascade();
    }
}

// last-resort mode: self-scan by potential order, no communication
static void soloRun() {
    vector<int> L;
    while (true) {
        core.closure();
        if (core.connected()) claimAndExit();
        core.order(96, L);
        if (L.empty()) { idleRound(); continue; } // unreachable in a valid maze
        for (int d : L) {
            if (core.st[d]) continue;
            core.apply(d, queryDoor(d));
            core.drainCascade();
            if (core.connected()) claimAndExit();
        }
    }
}

// ============ funnel protocol (v1): static scan shipped to agent 0 ============
// Wins over the epoch machinery when the maze is small relative to the team
// (full scan is only ~D/K rounds; gossip overhead would dominate) and when
// MAX_MSG_LEN is too small for headered gossip messages.
namespace funnel {

static ll B; // payload bits per message = 6*MSGLEN

struct Plan {
    ll S0 = 0;
    vector<ll> share, off;
    vector<ll> arrivals;
};

static void collectArrivals(const vector<ll>& S, int W, vector<ll>& arr) {
    arr.clear();
    for (int w = 1; w <= W; w++) {
        ll Sw = w < (int)S.size() ? S[w] : 0;
        if (Sw <= 0) continue;
        ll C = (Sw + B - 1) / B;
        for (ll c = 1; c <= C; c++) arr.push_back(min(c * B, Sw) + c + 1);
    }
    sort(arr.begin(), arr.end());
}
static ll makespan(ll S0, const vector<ll>& arr) {
    ll M = (ll)arr.size();
    ll t = 0, scanned = 0, ptr = 0;
    while (ptr < M || scanned < S0) {
        if (ptr < M && arr[ptr] <= t + 1) { ptr++; t++; continue; }
        if (scanned < S0) {
            ll lim = (ptr < M) ? (arr[ptr] - 1 - t) : (S0 - scanned);
            ll take = min(S0 - scanned, max(1LL, lim));
            scanned += take; t += take; continue;
        }
        t = arr[ptr]; ptr++;
    }
    return t + 1;
}
static ll smax(ll X) { // max s with s + ceil(s/B) <= X
    if (X <= 1) return 0;
    ll q = X / (B + 1), rem = X % (B + 1);
    return q * B + (rem > 0 ? rem - 1 : 0);
}
static bool tryPlanT(ll T, int Wact, vector<ll>& shares, ll& S0, vector<ll>& arr) {
    shares.assign(Wact + 1, 0);
    ll sum = 0;
    for (int i = 1; i <= Wact; i++) { shares[i] = smax(T - i - 1); sum += shares[i]; }
    if (sum > D) {
        ll excess = sum - D;
        for (int i = 1; i <= Wact && excess > 0; i++) {
            ll cut = min(excess, shares[i]);
            shares[i] -= cut; excess -= cut;
        }
        sum = D;
    }
    S0 = D - sum;
    collectArrivals(shares, Wact, arr);
    return makespan(S0, arr) <= T;
}
static Plan makePlan() {
    Plan p;
    int W = K - 1;
    if (W == 0 || B < 6 || D == 0) {
        p.S0 = D;
        p.share.assign(K, 0); p.share[0] = D;
        p.off.assign(K, D); p.off[0] = 0;
        return p;
    }
    ll bestT = D + 1;
    int bestW = 0;
    vector<ll> shares, arr;
    ll s0tmp;
    for (int Wact = 1; Wact <= W; Wact++) {
        ll lo = 1, hi = bestT - 1, found = -1;
        while (lo <= hi) {
            ll mid = (lo + hi) / 2;
            if (tryPlanT(mid, Wact, shares, s0tmp, arr)) { found = mid; hi = mid - 1; }
            else lo = mid + 1;
        }
        if (found > 0 && found < bestT) { bestT = found; bestW = Wact; }
    }
    p.share.assign(K, 0);
    p.off.assign(K, 0);
    if (bestW == 0) {
        p.S0 = D; p.share[0] = D;
        for (int w = 1; w < K; w++) p.off[w] = D;
    } else {
        tryPlanT(bestT, bestW, shares, p.S0, p.arrivals);
        p.share[0] = p.S0;
        ll o = p.S0;
        for (int w = 1; w < K; w++) {
            ll s = (w <= bestW) ? shares[w] : 0;
            p.share[w] = s; p.off[w] = o; o += s;
        }
    }
    return p;
}

static void runWorker(const Plan& plan) {
    ll lo = plan.off[ID], hi = lo + plan.share[ID];
    vector<uint8_t> bits;
    ll chunkBase = lo;
    const ll WIN = 64;
    while (chunkBase < hi) {
        ll chunkEnd = min(hi, chunkBase + B);
        ll len = chunkEnd - chunkBase;
        bits.assign((size_t)len, 0);
        ll issued = 0, got = 0;
        while (got < len) {
            while (issued < len && issued - got < WIN) {
                int r, c; doorCell((int)(chunkBase + issued), r, c);
                char buf[40]; snprintf(buf, sizeof buf, "? %d %d", r, c);
                emitLine(buf);
                issued++;
            }
            string rep; if (!readLine(rep)) dieQuietly();
            bits[(size_t)got++] = (!rep.empty() && rep[0] == '1');
        }
        string payload((size_t)((len + 5) / 6), '0');
        for (ll k = 0; k < len; k++)
            if (bits[(size_t)k]) payload[(size_t)(k / 6)] += (char)(1 << (k % 6));
        string cmd = "> 0 ";
        cmd += payload;
        emitLine(cmd);
        string ok; if (!readLine(ok)) dieQuietly();
        chunkBase = chunkEnd;
    }
    emitLine("halt");
    flushOut();
    exit(0);
}

static void runSolver(const Plan& plan) {
    const ll Mtotal = (ll)plan.arrivals.size();
    const ll S0 = plan.S0;
    vector<ll> nextChunk(K, 0);
    vector<pair<int, ll>> pend; size_t pendHead = 0; // 0 query, 1 recv-sure, 2 idle
    ll t = 0, scanned = 0, recvd = 0, inFlight = 0;
    int anomalies = 0;
    const size_t WIN = 16;

    auto processOne = [&]() {
        string rep;
        if (!readLine(rep)) dieQuietly();
        auto op = pend[pendHead++];
        if (op.first == 2) return;
        if (op.first == 0) {
            core.apply((int)op.second, !rep.empty() && rep[0] == '1');
            core.drainCascade();
        } else {
            inFlight--;
            if (rep.empty() || rep[0] == '-') { anomalies++; return; }
            size_t sp = rep.find(' ');
            if (sp == string::npos) { anomalies++; return; }
            int w = atoi(rep.c_str());
            if (w <= 0 || w >= K) { anomalies++; return; }
            const char* body = rep.c_str() + sp + 1;
            ll blen = (ll)(rep.size() - sp - 1);
            ll ci = nextChunk[w]++;
            ll base = plan.off[w] + ci * B;
            ll cnt2 = min(B, plan.off[w] + plan.share[w] - base);
            if (cnt2 <= 0 || blen < (cnt2 + 5) / 6) { anomalies = 1000; return; }
            for (ll k = 0; k < cnt2; k++) {
                int v = body[k / 6] - '0';
                core.apply((int)(base + k), (v >> (k % 6)) & 1);
            }
            core.drainCascade();
            recvd++;
        }
        if (core.connected()) claimAndExit();
    };

    while (anomalies < 5) {
        int type;
        ll door = -1;
        ll slot = recvd + inFlight;
        if (slot < Mtotal && plan.arrivals[(size_t)slot] <= t + 1) type = 1;
        else if (scanned < S0) { type = 0; door = scanned++; }
        else if (slot < Mtotal) type = 2;
        else break;
        if (type == 0) {
            int r, c; doorCell((int)door, r, c);
            char buf[40]; snprintf(buf, sizeof buf, "? %d %d", r, c);
            emitLine(buf);
        } else if (type == 1) { emitLine("< ?"); inFlight++; }
        else emitLine(".");
        pend.push_back({ type, door });
        t++;
        while (pend.size() - pendHead >= WIN) processOne();
    }
    while (pendHead < pend.size()) processOne();
    core.closure();
    if (core.connected()) claimAndExit();
    soloRun(); // worker died or malformed chunk: recover alone
}

static void run() {
    Plan plan = makePlan();
    if (ID == 0) runSolver(plan);
    else if (plan.share[ID] > 0) runWorker(plan);
    else { emitLine("halt"); flushOut(); exit(0); }
}
} // namespace funnel

// Apply a sender's positional bit stream: bit k = door L[a*W_e + k].
static vector<uint8_t> replayed; // sender already applied this epoch?

static void replayAgent(int a, int W_e, size_t Lmain, const vector<int>& L,
                        const vector<uint8_t>& bits) {
    if (replayed[a]) return;
    replayed[a] = 1;
    for (int k = 0; k < (int)bits.size(); k++) {
        size_t pos = (size_t)a * W_e + k;
        if (pos < Lmain) core.apply(L[pos], bits[k] != 0);
    }
    core.drainCascade();
}

// ============ territory mode (low K): sequential search per wedge ============
// Each agent runs a fully adaptive width-1 search restricted to its own wedge
// (steals the global best when the wedge is dry); the allgather ships explicit
// 18-bit (door,bit) records — no shared list needed, so picks may be adaptive.
static void terrRun() {
    vector<int> wedge; terrWedges(wedge);
    vector<int> myDoors;
    for (int d = 0; d < D; d++) if (wedge[d] == ID) myDoors.push_back(d);
    const int W = TERR_W > 0 ? TERR_W : (K == 3 ? 48 : 32), RB = 18;
    vector<int> cnt(K, W * RB);
    SyncPlan sp = buildSyncPlan(cnt); // payload sizes are constant: one static plan
    vector<int> L;
    vector<vector<uint8_t>> epochBits(K);
    vector<pair<int, int>> recs;
    int epoch = 0;
    replayed.assign(K, 0);
    auto applyRecords = [&](int a) {
        if (replayed[a]) return;
        replayed[a] = 1;
        for (int i = 0; i < W; i++) {
            unsigned v = 0;
            for (int b = 0; b < RB; b++)
                v |= (unsigned)(epochBits[a][(size_t)i * RB + b] != 0) << b;
            if (!v) continue; // idle-round sentinel
            int d = (int)(v >> 1) - 1;
            if (d < 0 || d >= D) soloRun();
            core.apply(d, (v & 1) != 0);
        }
        core.drainCascade();
    };
    while (true) {
        core.closure();
        if (core.connected()) {
            if (ID == 0) claimAndExit();
            emitLine("halt"); flushOut(); exit(0);
        }
        for (int j = 0; j < K; j++) epochBits[j].clear();
        replayed.assign(K, 0);
        // ---- work phase: W own adaptive queries ----
        recs.clear();
        for (int r = 0; r < W; r++) {
            bool fullL = (r % 8 == 0); // fields refresh per query, full list rarely
            if (fullL) core.order((size_t)2 * K * W, L);
            else core.orderFields();
            int pick = terrPick(core, myDoors, ID, L);
            if (pick < 0 && !fullL) { core.order((size_t)2 * K * W, L); pick = terrPick(core, myDoors, ID, L); }
            if (pick < 0) { idleRound(); recs.push_back({ -1, 0 }); continue; }
            bool open = queryDoor(pick);
            recs.push_back({ pick, open ? 1 : 0 });
            core.apply(pick, open);
            core.drainCascade();
            if (core.connected()) claimAndExit();
        }
        {
            vector<uint8_t>& bits = epochBits[ID];
            bits.assign((size_t)W * RB, 0);
            for (int i = 0; i < W; i++) {
                unsigned v = recs[(size_t)i].first < 0 ? 0u
                    : (((unsigned)(recs[(size_t)i].first + 1) << 1) | (unsigned)recs[(size_t)i].second);
                for (int b = 0; b < RB; b++) bits[(size_t)i * RB + b] = (uint8_t)((v >> b) & 1);
            }
        }
        replayed[ID] = 1;
        // ---- sync phase: identical transport, record payloads ----
        char hdr = (char)('0' + (epoch & 31));
        for (auto& ph : sp.phases) {
            const Transfer* sendT = nullptr; const Transfer* recvT = nullptr;
            for (auto& t : ph.tr) {
                if (t.from == ID) sendT = &t;
                if (t.to == ID) recvT = &t;
            }
            string outChars;
            int outMsgs = 0, inMsgs = 0;
            if (sendT) {
                vector<uint8_t> allBits;
                for (int a : sendT->set)
                    allBits.insert(allBits.end(), epochBits[a].begin(), epochBits[a].end());
                encodeBits(allBits, outChars);
                outMsgs = msgsFor((ll)allBits.size());
            }
            if (recvT) {
                ll bits = 0; for (int a : recvT->set) bits += cnt[a];
                inMsgs = msgsFor(bits);
            }
            string inChars;
            for (int r = 0; r < ph.qmax; r++) {
                if (sendT && r < outMsgs) {
                    ll cap = MSGLEN - 1;
                    string body(1, hdr);
                    size_t from = (size_t)r * cap;
                    if (from < outChars.size())
                        body.append(outChars, from, min((size_t)cap, outChars.size() - from));
                    char pre[16]; snprintf(pre, sizeof pre, "> %d ", sendT->to);
                    emitLine(pre + body);
                    string rep; if (!readLine(rep)) dieQuietly();
                } else idleRound();
            }
            for (int r = 0; r < ph.qmax; r++) {
                if (recvT && r < inMsgs) {
                    char pre[16]; snprintf(pre, sizeof pre, "< %d", recvT->from);
                    string rep;
                    for (int tries = 0;; tries++) {
                        emitLine(pre);
                        if (!readLine(rep)) dieQuietly();
                        if (!rep.empty() && rep[0] != '-') break;
                        if (tries >= 6) soloRun();
                    }
                    size_t sq = rep.find(' ');
                    if (sq == string::npos || sq + 1 >= rep.size() || rep[sq + 1] != hdr) soloRun();
                    inChars.append(rep, sq + 2, string::npos);
                } else idleRound();
            }
            if (recvT) {
                size_t bitPos = 0;
                for (int a : recvT->set) {
                    if (epochBits[a].empty() && cnt[a] > 0) {
                        if (inChars.size() * 6 < bitPos + cnt[a]) soloRun();
                        epochBits[a].resize((size_t)cnt[a]);
                        for (int k = 0; k < cnt[a]; k++) {
                            size_t p = bitPos + k;
                            int v = inChars[p / 6] - '0';
                            epochBits[a][(size_t)k] = (uint8_t)((v >> (p % 6)) & 1);
                        }
                        applyRecords(a);
                        if (core.connected()) claimAndExit();
                    }
                    bitPos += cnt[a];
                }
            }
        }
        for (int j = 0; j < K; j++) {
            if ((int)epochBits[j].size() < cnt[j]) soloRun();
            applyRecords(j);
        }
        epoch++;
    }
}

int main() {
    initPri();
    string line;
    if (!readLine(line)) return 0;
    long long msglen = 0;
    if (sscanf(line.c_str(), "%d %d %d %lld", &N, &K, &ID, &msglen) != 4) return 0;
    MSGLEN = msglen;
    m = (N + 1) / 2;
    HD = m * (m - 1);
    D = 2 * HD;
    core.init();

    if (m == 1) { // N == 1: empty path
        if (ID == 0) { emitLine("! "); flushOut(); }
        else { emitLine("halt"); flushOut(); }
        return 0;
    }
    if (K <= 1) soloRun();
    if (MSGLEN < 8 || ((ll)D <= 50LL * K && K < 40)) { // tiny high-K cases prefer one epoch over static funnel
        funnel::B = 6 * MSGLEN;
        funnel::run();
        return 0;
    }
    if (TERRM && K >= 3 && K <= TERR_KMAX && MSGLEN >= 64 &&
        (ll)D <= min((ll)TERR_DMAX, 6200LL * K))
        terrRun(); // never returns

    const size_t WTAKE = (size_t)K * workCap();
    vector<int> L, cnt(K), myDoors;
    vector<vector<uint8_t>> epochBits(K);
    int epoch = 0;
    replayed.assign(K, 0);

    while (true) {
        // ---- epoch boundary ----
        core.closure();
        if (core.connected()) {
            if (ID == 0) claimAndExit();
            emitLine("halt"); flushOut(); return 0;
        }
        core.orderChain(2 * WTAKE, L); // second half of L = spare pool
        if (g_potMin <= RACE_POT) raceRun(); // components nearly touch: sprint solo
        size_t WT = WTAKE;
        if (CH_EW > 0 && g_potMin <= (ll)CH_POT) WT = min(WT, (size_t)K * CH_EW);
        size_t Lmain = min(L.size(), WT);
        int W_e = (int)((Lmain + K - 1) / K);
        if (W_e < 1) W_e = 1;
        for (int j = 0; j < K; j++) {
            ll lo = min((ll)Lmain, (ll)j * W_e), hi = min((ll)Lmain, (ll)(j + 1) * W_e);
            cnt[j] = (int)(hi - lo);
        }
        myDoors.clear();
        for (ll i = (ll)ID * W_e; i < min((ll)Lmain, (ll)(ID + 1) * W_e); i++)
            myDoors.push_back(L[(size_t)i]);
        for (int j = 0; j < K; j++) epochBits[j].clear();
        replayed.assign(K, 0);

        // ---- work phase: pipelined queries (batched writes drain 1/round) ----
        // Far from the endgame the whole block is written ahead (wall-clock win
        // under the judge's 10% CPU throttle); near it a small window keeps the
        // instant-claim latency tight.
        {
            size_t issued = 0, got = 0, nDoors = myDoors.size();
            size_t win = (g_potMin > 64) ? nDoors : 4;
            if (win < 1) win = 1;
            while (got < nDoors) {
                while (issued < nDoors && issued - got < win) {
                    int r, c; doorCell(myDoors[issued], r, c);
                    char buf[40]; snprintf(buf, sizeof buf, "? %d %d", r, c);
                    emitLine(buf);
                    issued++;
                }
                string rep; if (!readLine(rep)) dieQuietly();
                bool open = !rep.empty() && rep[0] == '1';
                epochBits[ID].push_back(open ? 1 : 0);
                core.apply(myDoors[got], open);
                core.drainCascade();
                got++;
                if (core.connected()) claimAndExit();
            }
            for (int i = (int)nDoors; i < W_e; i++) idleRound();
        }

        // ---- sync phase (allgather) ----
        SyncPlan sp = buildSyncPlan(cnt);
        char hdr = (char)('0' + (epoch & 31));
        for (auto& ph : sp.phases) {
            const Transfer* sendT = nullptr; const Transfer* recvT = nullptr;
            for (auto& t : ph.tr) {
                if (t.from == ID) sendT = &t;
                if (t.to == ID) recvT = &t;
            }
            string outChars;
            int outMsgs = 0, inMsgs = 0;
            if (sendT) {
                vector<uint8_t> allBits;
                for (int a : sendT->set)
                    allBits.insert(allBits.end(), epochBits[a].begin(), epochBits[a].end());
                encodeBits(allBits, outChars);
                outMsgs = msgsFor((ll)allBits.size());
            }
            if (recvT) {
                ll bits = 0; for (int a : recvT->set) bits += cnt[a];
                inMsgs = msgsFor(bits);
            }
            string inChars;
            auto sendMsg = [&](int r) {
                ll cap = MSGLEN - 1;
                string body(1, hdr);
                size_t from = (size_t)r * cap;
                if (from < outChars.size())
                    body.append(outChars, from, min((size_t)cap, outChars.size() - from));
                char pre[16]; snprintf(pre, sizeof pre, "> %d ", sendT->to);
                emitLine(pre + body);
                string rep; if (!readLine(rep)) dieQuietly();
            };
            auto recvMsg = [&]() {
                char pre[16]; snprintf(pre, sizeof pre, "< %d", recvT->from);
                string rep;
                for (int tries = 0;; tries++) {
                    emitLine(pre);
                    if (!readLine(rep)) dieQuietly();
                    if (!rep.empty() && rep[0] != '-') break;
                    if (tries >= 6) soloRun();
                }
                size_t sq = rep.find(' ');
                if (sq == string::npos || sq + 1 >= rep.size() || rep[sq + 1] != hdr) soloRun();
                inChars.append(rep, sq + 2, string::npos);
            };
            for (int r = 0; r < ph.qmax; r++)
                if (sendT && r < outMsgs) sendMsg(r); else idleRound();
            for (int r = 0; r < ph.qmax; r++)
                if (recvT && r < inMsgs) recvMsg(); else idleRound();
            if (recvT) { // decode transfer; replay sender skips; claim mid-sync
                size_t bitPos = 0;
                for (int a : recvT->set) {
                    if (epochBits[a].empty() && cnt[a] > 0) {
                        if (inChars.size() * 6 < bitPos + cnt[a]) soloRun();
                        epochBits[a].resize(cnt[a]);
                        for (int k = 0; k < cnt[a]; k++) {
                            size_t p = bitPos + k;
                            int v = inChars[p / 6] - '0';
                            epochBits[a][k] = (uint8_t)((v >> (p % 6)) & 1);
                        }
                        replayAgent(a, W_e, Lmain, L, epochBits[a]);
                        if (core.connected()) claimAndExit();
                    }
                    bitPos += cnt[a];
                }
            }
        }
        // ---- merge: replay any stream not applied during the sync ----
        for (int j = 0; j < K; j++) {
            if ((int)epochBits[j].size() < cnt[j]) soloRun(); // lost data: recover solo
            replayAgent(j, W_e, Lmain, L, epochBits[j]);
        }
        epoch++;
    }
}

#else
// =====================================================================
// ==============             SIMULATOR MODE             ==============
// =====================================================================
// usage: sim <maze.txt> <K> <MSGLEN> [WCAP]
#include <unordered_map>
static vector<string> g_maze;
static bool truthOpen(int d) {
    int r, c; doorCell(d, r, c);
    return g_maze[(size_t)r - 1][(size_t)c - 1] == '.';
}
static int g_wcapOverride = 0;
#ifdef COLLECT
static long long g_cnt[75 * 75][2];
#endif

// tiny DSU over canonical component roots: models one agent's private view
// (canon + its own open doors) for mid-epoch claim detection
struct RootOverlay {
    unordered_map<int, int> par;
    int find(int x) {
        auto it = par.find(x);
        if (it == par.end() || it->second == x) return x;
        int r = find(it->second);
        par[x] = r;
        return r;
    }
    void unite(int a, int b) { a = find(a); b = find(b); if (a != b) par[a] = b; }
    void clear() { par.clear(); }
};

int main(int argc, char** argv) {
    if (argc < 4) { fprintf(stderr, "usage: sim maze.txt K MSGLEN [WCAP]\n"); return 1; }
    FILE* f = fopen(argv[1], "r");
    if (!f) { perror("maze"); return 1; }
    if (fscanf(f, "%d ", &N) != 1) return 1;
    {
        char rowbuf[1024];
        for (int i = 0; i < N; i++) {
            if (!fgets(rowbuf, sizeof rowbuf, f)) return 1;
            string s(rowbuf);
            while (!s.empty() && (s.back() == '\n' || s.back() == '\r')) s.pop_back();
            g_maze.push_back(s);
        }
    }
    fclose(f);
    initPri();
    K = atoi(argv[2]);
    MSGLEN = atoll(argv[3]);
    if (argc > 4) { g_wcapOverride = atoi(argv[4]); WCAP_OVERRIDE = g_wcapOverride; }
    if (argc > 5) LAMBDA = atoi(argv[5]);
    if (argc > 6) UNKW = atoi(argv[6]);
    if (argc > 7) BLOCKS = atoi(argv[7]);
    if (argc > 8) RACE_POT = atoi(argv[8]);
    if (argc > 9) SPARES = atoi(argv[9]);
    if (argc > 10) MU = atoi(argv[10]);
    if (getenv("CHAIN")) CHAIN = atoi(getenv("CHAIN"));
    if (getenv("CH_POT")) CH_POT = atoi(getenv("CH_POT"));
    if (getenv("CH_FRAC")) CH_FRAC = atoi(getenv("CH_FRAC"));
    if (getenv("CH_GEN")) CH_GEN = atoi(getenv("CH_GEN"));
    if (getenv("CH_HEDGE")) CH_HEDGE = atoi(getenv("CH_HEDGE"));
    if (getenv("CH_CAPX")) CH_CAPX = atoi(getenv("CH_CAPX"));
    if (getenv("CH_EW")) CH_EW = atoi(getenv("CH_EW"));
    if (getenv("CH_STRIKES")) CH_STRIKES = atoi(getenv("CH_STRIKES"));
    int SWALLOW = getenv("SWALLOW") ? atoi(getenv("SWALLOW")) : 0; // endgame: take ALL live candidates in one epoch
    int SWW = getenv("SWW") ? atoi(getenv("SWW")) : 96;            // max swallow epoch width
    if (getenv("TERRM")) TERRM = atoi(getenv("TERRM"));
    if (getenv("TERR_W")) TERR_W = atoi(getenv("TERR_W"));
    if (getenv("TERR_KMAX")) TERR_KMAX = atoi(getenv("TERR_KMAX"));
    if (getenv("TERR_DMAX")) TERR_DMAX = atoi(getenv("TERR_DMAX"));
    ID = 0;
    m = (N + 1) / 2;
    HD = m * (m - 1);
    D = 2 * HD;

    if (TERRM && K >= 3 && K <= TERR_KMAX && MSGLEN >= 64 &&
        (ll)D <= min((ll)TERR_DMAX, 6200LL * K)) {
        // faithful territory-mode sim: no cross-agent dedup, real sync rounds
        vector<int> wedge; terrWedges(wedge);
        vector<vector<int>> wDoors(K);
        for (int d = 0; d < D; d++) wDoors[wedge[d]].push_back(d);
        const int W = TERR_W > 0 ? TERR_W : (K == 3 ? 48 : 32);
        vector<int> cntT(K, W * 18);
        SyncPlan spT = buildSyncPlan(cntT);
        Core canonT; canonT.init();
        vector<Core> agT(K);
        vector<vector<int>> LTj(K);
        vector<vector<pair<int, uint8_t>>> gotT(K);
        ll tT = 0, qT = 0;
        int epT = 0;
        bool doneT = false;
        while (!doneT) {
            canonT.closure();
            if (canonT.connected()) { tT += 1; break; }
            for (int j = 0; j < K; j++) { agT[j] = canonT; gotT[j].clear(); }
            for (int r = 0; r < W && !doneT; r++) {
                tT++;
                for (int j = 0; j < K && !doneT; j++) {
                    bool fullL = (r % 8 == 0);
                    if (fullL) agT[j].order((size_t)2 * K * W, LTj[j]);
                    else agT[j].orderFields();
                    int pick = terrPick(agT[j], wDoors[j], j, LTj[j]);
                    if (pick < 0 && !fullL) { agT[j].order((size_t)2 * K * W, LTj[j]); pick = terrPick(agT[j], wDoors[j], j, LTj[j]); }
                    if (pick < 0) continue;
                    bool open = truthOpen(pick);
                    qT++;
                    gotT[j].push_back({ pick, (uint8_t)(open ? 1 : 0) });
                    agT[j].apply(pick, open);
                    agT[j].drainCascade();
                    if (agT[j].connected()) doneT = true;
                }
            }
            if (doneT) { tT += 1; break; }
            tT += spT.rounds;
            for (int j = 0; j < K; j++)
                for (auto& pr : gotT[j]) canonT.apply(pr.first, pr.second != 0);
            epT++;
#ifdef EPOCHLOG
            fprintf(stderr, "T ep=%2d potMin=%4lld cand=%5lld W=%2d cumQ=%lld t=%lld\n",
                    epT, g_potMin, g_candTotal, W, qT, tT);
#endif
        }
        printf("rounds=%lld queries=%lld epochs=%d D=%d skipped=0 terr=1\n", tT, qT, epT, D);
        return 0;
    }
    Core canon; canon.init();
    vector<Core> ag(K);
    vector<vector<int>> seq(K);
    vector<size_t> ptr(K);
    vector<int> L, cnt(K);
    ll t = 0, queries = 0, skipped = 0;
    int epochs = 0;
    const size_t WTAKE = (size_t)K * (g_wcapOverride > 0 ? g_wcapOverride : workCap());

    bool race = false;
    while (true) {
        canon.closure();
        if (canon.connected()) { t += 1; break; }
        canon.orderChain(2 * WTAKE, L);
        if (g_potMin <= RACE_POT) { race = true; break; }
        size_t WT = WTAKE;
        if (CH_EW > 0 && g_potMin <= (ll)CH_POT) WT = min(WT, (size_t)K * CH_EW);
        if (SWALLOW && g_candTotal > 0 && g_candTotal <= (ll)L.size() &&
            (g_candTotal + K - 1) / K <= (ll)SWW)
            WT = (size_t)g_candTotal; // endgame swallow: one epoch covers every live door
        size_t Lmain = min(L.size(), WT);
        int W_e = (int)((Lmain + K - 1) / K);
        if (W_e < 1) W_e = 1;
        for (int j = 0; j < K; j++) {
            ll lo = min((ll)Lmain, (ll)j * W_e), hi = min((ll)Lmain, (ll)(j + 1) * W_e);
            cnt[j] = (int)(hi - lo);
            ag[j] = canon;
            seq[j].clear();
            for (ll i = lo; i < hi; i++) seq[j].push_back(L[(size_t)i]);
            ptr[j] = 0;
        }
        bool claimed = false;
        vector<pair<int, uint8_t>> found;
        for (int i = 0; i < W_e && !claimed; i++) {
            t++;
            for (int j = 0; j < K; j++) {
                if (ptr[j] >= seq[j].size()) continue;
                int d = seq[j][ptr[j]++];
                bool open = truthOpen(d);
#ifdef COLLECT
                { int p = ag[j].patId(d); g_cnt[p][open ? 1 : 0]++; }
#endif
                queries++;
                found.push_back({ d, (uint8_t)(open ? 1 : 0) });
                ag[j].apply(d, open);
                ag[j].drainCascade();
                if (ag[j].connected()) { claimed = true; break; }
            }
        }
        if (claimed) { t += 1; break; }
        SyncPlan sp = buildSyncPlan(cnt);
        t += sp.rounds;
        ll opens = 0;
        for (auto& f : found) { canon.apply(f.first, f.second != 0); opens += f.second; }
        epochs++;
#ifdef EPOCHLOG
        fprintf(stderr, "ep=%2d potMin=%4lld cand=%5lld ch=%4lld W=%2d q=%4zu opens=%3lld cumQ=%lld t=%lld\n",
                epochs, g_potMin, g_candTotal, g_chainLen, W_e, found.size(), opens, queries, t);
#endif
    }
    if (getenv("STATIC")) { // static-order funnel model (v3 hypothesis)
        int Bs = getenv("SB") ? atoi(getenv("SB")) : 2 * (K - 1); // worker batch bits
        if (Bs < 8) Bs = 8;
        Core c0; c0.init();
        vector<int> L0;
        c0.order((size_t)D, L0); // pure-geometry order on the empty maze
        // arrival model: door with global rank p is scanned by agent p%K at its
        // local round p/K; workers' bits reach the solver ~Bs rounds later;
        // the solver itself scans at ~half rate (recv load), so its slice
        // contributes at 2x round cost. Simplify: effective throughput K-0.5,
        // uniform lag Bs.
        double thr = K - 0.5;
        Core sol; sol.init();
        ll r = 0; size_t p = 0;
        ll lag = Bs + 2;
        bool ok = false;
        while (p < L0.size()) {
            r++;
            size_t upto = (size_t)max(0.0, thr * (double)(r - lag));
            if (upto > L0.size()) upto = L0.size();
            for (; p < upto; p++) {
                sol.apply(L0[p], truthOpen(L0[p]));
                sol.drainCascade();
                if (sol.connected()) { ok = true; break; }
            }
            if (ok) break;
        }
        printf("STATIC rounds=%lld coverage=%.2f Bs=%d D=%d %s\n",
               r + 1, 100.0 * p / D, Bs, D, ok ? "" : "NOCONNECT");
        return 0;
    }
    if (getenv("TERR")) { // territory model: K diagonal wedges, sequential search inside
        // each agent: fully adaptive width-1 search restricted to its wedge
        // (global order() filtered by wedge membership); allgather every TW
        // rounds costs TSY rounds; claim mid-epoch on own view.
        int TW = getenv("TW") ? atoi(getenv("TW")) : (g_wcapOverride > 0 ? g_wcapOverride : workCap());
        int TSY; { int st = 1, lg = 0; while (st < K) { st *= 2; lg++; } TSY = 2 * lg; }
        if (getenv("TSY")) TSY = atoi(getenv("TSY"));
        int STEAL = getenv("TSTEAL") ? atoi(getenv("TSTEAL")) : 1;
        int TR = getenv("TR") ? atoi(getenv("TR")) : 1; // reorder own view every TR own queries
        vector<int> wedge(D);
        {   // equal-door anti-diagonal bands by door midpoint level
            vector<pair<int, int>> lv(D);
            for (int d = 0; d < D; d++) {
                int a, b; doorRooms(d, a, b);
                int la = a / m + a % m, lb = b / m + b % m;
                lv[d] = { la + lb, d }; // 2*level (+1 for the crossed door)
            }
            sort(lv.begin(), lv.end());
            for (int i = 0; i < D; i++) wedge[lv[i].second] = (int)((ll)i * K / D);
        }
        Core canon2; canon2.init();
        vector<Core> tc(K);
        vector<int> Lt2;
        ll t5 = 0; queries = 0;
        int ep5 = 0;
        bool done = false;
        while (!done) {
            canon2.closure();
            if (canon2.connected()) { t5 += 1; break; }
            vector<vector<pair<int, uint8_t>>> got(K);
            vector<vector<int>> myL(K);
            vector<int> curRoom(K, -1);
            for (int j = 0; j < K; j++) tc[j] = canon2;
            vector<uint8_t> takenEp(D, 0); // wedge-local: no cross-agent dupes within epoch
            for (int r = 0; r < TW && !done; r++) {
                t5++;
                for (int j = 0; j < K && !done; j++) {
                    Core& C = tc[j];
                    int pick = -1;
                    if (r % TR == 0) {
                        C.order(max((size_t)512, (size_t)2 * K * TW), myL[j]);
                        curRoom[j] = -1;
                    } else if (curRoom[j] >= 0) {
                        // cheap step: follow the stale dg field from the corridor tip
                        int v = curRoom[j];
                        for (int guard = 0; guard < 4 * m && pick < 0; guard++) {
                            int dd[4], n = roomDoors(v, dd), nxt = -1, und = -1;
                            for (int i = 0; i < n; i++) {
                                int d = dd[i], a, b; doorRooms(d, a, b);
                                int o = (a == v) ? b : a;
                                if (C.dg[o] >= C.dg[v]) continue;
                                if (C.st[d] == 2 && nxt < 0) nxt = o;
                                if (!C.st[d] && !takenEp[d] && und < 0) und = d;
                            }
                            if (und >= 0) { pick = und; break; }
                            if (nxt < 0) break;
                            v = nxt;
                        }
                        curRoom[j] = -1;
                    }
                    if (C.connected()) { done = true; break; }
                    if (pick < 0) {
                        int alt = -1;
                        for (int d : myL[j]) {
                            if (takenEp[d] || C.st[d]) continue;
                            if (alt < 0) alt = d;
                            if (wedge[d] == j) { pick = d; break; }
                        }
                        if (pick < 0 && STEAL) pick = alt; // wedge dry: take global best
                    }
                    if (pick < 0) continue;
                    takenEp[pick] = 1;
                    bool open = truthOpen(pick);
                    queries++;
                    got[j].push_back({ pick, (uint8_t)(open ? 1 : 0) });
                    C.apply(pick, open);
                    C.drainCascade();
                    if (open) { // corridor tip advances through the opened door
                        int a, b; doorRooms(pick, a, b);
                        curRoom[j] = (C.dg[a] < C.dg[b]) ? a : b;
                    } else curRoom[j] = -1;
                    if (C.connected()) { done = true; break; }
                }
            }
            if (done) { t5 += 1; break; }
            t5 += TSY;
            for (int j = 0; j < K; j++)
                for (auto& pr : got[j]) canon2.apply(pr.first, pr.second != 0);
            ep5++;
        }
        printf("TERR rounds=%lld queries=%lld epochs=%d TW=%d TSY=%d D=%d\n",
               t5, queries, ep5, TW, TSY, D);
        return 0;
    }
    if (getenv("SKIPF")) { // streaming funnel + inference-skip feedback (v4 model)
        // workers scan static blocks, solver (agent 0) integrates results with
        // lag LU, runs full closure, and feeds back "door already decided" skip
        // bitmaps with lag LD; a skipped door costs 0 rounds. Worker cycle =
        // B queries + send + recv (solver capacity needs B >= 2(K-1)-2).
        int OT = getenv("SKO") ? atoi(getenv("SKO")) : 0; // 0 id-blocks 1 L0-blocks 2 L0-interleave
        int Wn = K - 1;
        int B = getenv("SKB") ? atoi(getenv("SKB")) : max(8, 2 * Wn - 2);
        int LU = B + 2;
        int LD = getenv("SKLD") ? atoi(getenv("SKLD")) : B + 2;
        vector<int> L0;
        if (OT == 0) { L0.resize(D); for (int d = 0; d < D; d++) L0[d] = d; }
        else { Core c0; c0.init(); c0.order((size_t)D, L0); }
        vector<vector<int>> blk(Wn);
        if (OT == 2) { for (size_t i = 0; i < L0.size(); i++) blk[i % Wn].push_back(L0[i]); }
        else {
            size_t per = (L0.size() + Wn - 1) / Wn;
            for (int w = 0; w < Wn; w++)
                for (size_t i = per * w; i < min(L0.size(), per * (w + 1)); i++)
                    blk[w].push_back(L0[i]);
        }
        Core sol; sol.init();
        vector<ll> decT(D, LLONG_MAX);
        vector<size_t> pt(Wn, 0);
        vector<pair<ll, pair<int, int>>> arr; // (arrival round, (door, bit))
        size_t ah = 0;
        ll t4 = 0, skip4 = 0; queries = 0;
        bool done = false;
        while (!done) {
            t4++;
            while (ah < arr.size() && arr[ah].first <= t4) {
                sol.apply(arr[ah].second.first, arr[ah].second.second != 0);
                ah++;
            }
            sol.drainCascade();
            for (int d = 0; d < D; d++) { // full closure sweep + decision stamps
                if (sol.st[d]) { if (decT[d] == LLONG_MAX) decT[d] = t4; continue; }
                int a, b; doorRooms(d, a, b);
                if (sol.find(a) == sol.find(b)) { sol.apply(d, false); decT[d] = t4; }
            }
            sol.drainCascade();
            for (int d = 0; d < D; d++)
                if (sol.st[d] && decT[d] == LLONG_MAX) decT[d] = t4;
            if (sol.connected()) { done = true; break; }
            bool anyLeft = false;
            for (int w = 0; w < Wn; w++) {
                ll lt = t4 - 2 * w; // staggered start
                if (lt <= 0) { anyLeft = true; continue; }
                if (lt % (B + 2) >= B) { anyLeft = anyLeft || pt[w] < blk[w].size(); continue; }
                while (pt[w] < blk[w].size() && decT[blk[w][pt[w]]] <= t4 - LD) { pt[w]++; skip4++; }
                if (pt[w] < blk[w].size()) {
                    int d = blk[w][pt[w]++];
                    queries++;
                    arr.push_back({ t4 + LU, { d, truthOpen(d) ? 1 : 0 } });
                    anyLeft = true;
                }
            }
            if (!anyLeft && ah >= arr.size()) break; // scan exhausted, no claim
        }
        printf("SKIPF rounds=%lld queries=%lld skipped=%lld cover=%.1f%% B=%d OT=%d D=%d %s\n",
               t4 + 1, queries, skip4, 100.0 * (queries + skip4) / D, B, OT, D,
               done ? "" : "NOCONNECT");
        return 0;
    }
    if (getenv("TIER")) { // two-tier model: G gossip-brains + (K-G) couriers
        int G = atoi(getenv("TIER"));
        if (G < 2) G = 2;
        int NQ = K - G;                       // couriers
        int spg = (NQ + G - 1) / G;           // couriers per gossiper
        int gossOps = 2 * spg;                // serve couriers: recv+send each
        { int st = 1; while (st < G) { st *= 2; gossOps += 2; } } // allgather
        int Tw = gossOps;                     // window length (gossiper-bound)
        int Wq = Tw - 2;                      // courier queries per window
        if (Wq < 4) { Wq = 4; Tw = Wq + 2; }
        vector<Core> gc(G);                   // per-gossiper state
        for (int g = 0; g < G; g++) gc[g].init();
        // results by window: results[w] = list of (door,bit) per gossiper
        vector<vector<vector<pair<int,uint8_t>>>> hist; // [w][g] -> pairs
        vector<vector<int>> asn(NQ);          // courier assignments this window
        vector<uint8_t> assigned(D, 0);
        vector<int> Lt;
        ll t3 = 0; queries = 0;
        int w = 0;
        bool done = false;
        while (!done) {
            // assignment for window w: gossiper g uses its core (shared thru w-2
            // plus its own couriers' w-1 results), takes ranks == g (mod G)
            hist.push_back(vector<vector<pair<int,uint8_t>>>(G));
            for (int g = 0; g < G && !done; g++) {
                gc[g].order((size_t)G * spg * Wq * 2, Lt);
                if (gc[g].connected()) { done = true; t3 += 1; break; }
                vector<int> mine;
                for (size_t i = g; i < Lt.size(); i += G)
                    if (!assigned[Lt[i]]) mine.push_back(Lt[i]);
                size_t p = 0;
                for (int c = 0; c < spg; c++) {
                    int q = g * spg + c;
                    if (q >= NQ) break;
                    asn[q].clear();
                    for (int i = 0; i < Wq && p < mine.size(); i++, p++) {
                        asn[q].push_back(mine[p]); assigned[mine[p]] = 1;
                    }
                }
            }
            if (done) break;
            // couriers execute window w
            t3 += Tw;
            for (int q = 0; q < NQ; q++) {
                int g = q / spg;
                for (int d : asn[q]) {
                    bool open = truthOpen(d);
                    queries++;
                    hist[w][g].push_back({ d, (uint8_t)(open ? 1 : 0) });
                }
            }
            // window-end integration: own couriers' w results -> own core;
            // all gossipers' w-1 results -> everyone (allgather during w)
            for (int g = 0; g < G; g++)
                for (auto& pr : hist[w][g]) { gc[g].apply(pr.first, pr.second != 0); }
            for (int g = 0; g < G; g++) gc[g].drainCascade();
            if (w >= 1)
                for (int g = 0; g < G; g++)
                    for (int g2 = 0; g2 < G; g2++) {
                        if (g2 == g) continue;
                        for (auto& pr : hist[w-1][g2]) gc[g].apply(pr.first, pr.second != 0);
                    }
            for (int g = 0; g < G; g++) { gc[g].drainCascade(); if (gc[g].connected()) done = true; }
            if (done) { t3 += 1; break; }
            w++;
        }
        printf("TIER rounds=%lld queries=%lld G=%d Wq=%d Tw=%d D=%d\n", t3, queries, G, Wq, Tw, D);
        return 0;
    }
    if (getenv("HUB")) { // hub-pipeline architecture model (brain = agent 0)
        // workers: cycle = Wh queries + 1 send + 1 recv, offsets stagger by 2;
        // brain: pure comms; assigns top unqueried-unassigned doors by order().
        int Wrk = K - 1;
        if (getenv("HUBW")) Wrk = min(Wrk, atoi(getenv("HUBW")));
        int Wh = max(4, 2 * Wrk - 2);            // batch so the brain keeps up
        ll cycle = Wh + 2;
        Core brain; brain.init();
        vector<uint8_t> assigned(D, 0);
        vector<vector<int>> cur(Wrk), nxt(Wrk);  // current/next assignment
        vector<vector<uint8_t>> res(Wrk);
        vector<int> Lh;
        brain.order((size_t)Wh * Wrk, Lh);
        {   size_t p = 0;
            for (int w = 0; w < Wrk; w++)
                for (int i = 0; i < Wh && p < Lh.size(); i++) { cur[w].push_back(Lh[p]); assigned[Lh[p]] = 1; p++; }
        }
        ll t2 = 0; queries = 0;
        vector<size_t> qi(Wrk, 0);
        bool done = false;
        while (!done) {
            t2++;
            for (int w = 0; w < Wrk && !done; w++) {
                ll since = t2 - 1 - 2 * w; // worker w starts after 2w idle rounds
                if (since < 0) continue;
                ll ph = since % cycle;
                if (ph < Wh) { // query round
                    if (qi[w] < cur[w].size()) {
                        int d = cur[w][(size_t)qi[w]];
                        res[w].push_back(truthOpen(d) ? 1 : 0);
                        queries++;
                    }
                    qi[w]++;
                } else if (ph == Wh) { // send results; brain integrates next round
                    for (size_t i = 0; i < cur[w].size(); i++)
                        brain.apply(cur[w][i], res[w][i] != 0);
                    brain.drainCascade();
                    if (brain.connected()) { done = true; break; }
                    // brain computes this worker's next batch
                    brain.order((size_t)Wh * (Wrk + 1), Lh); // top fresh, minus in-flight
                    nxt[w].clear();
                    for (int d : Lh) {
                        if (assigned[d] || brain.st[d]) continue;
                        nxt[w].push_back(d); assigned[d] = 1;
                        if ((int)nxt[w].size() >= Wh) break;
                    }
                } else { // recv round: swap in the new assignment
                    cur[w] = nxt[w]; res[w].clear(); qi[w] = 0;
                }
            }
        }
        printf("HUB rounds=%lld queries=%lld Wh=%d D=%d\n", t2 + 1, queries, Wh, D);
        return 0;
    }
    if (race) { // per-agent independent corridor race, exact model
        vector<Core> rc(K, canon);
        vector<int> Lr;
        bool first = true, done = false;
        while (!done) {
            t++;
            for (int j = 0; j < K && !done; j++) {
                rc[j].order(first ? (size_t)K + 1 : 1, Lr);
                if (Lr.empty()) continue;
                int pick = first ? (int)min((size_t)j, Lr.size() - 1) : 0;
                int d = Lr[pick];
                queries++;
                rc[j].apply(d, truthOpen(d));
                rc[j].drainCascade();
                if (rc[j].connected()) done = true;
            }
            first = false;
        }
        t++; // claim round
    }
    printf("rounds=%lld queries=%lld epochs=%d D=%d skipped=%lld\n", t, queries, epochs, D, skipped);
#ifdef COLLECT
    for (int p = 0; p < 75 * 75; p++)
        if (g_cnt[p][0] + g_cnt[p][1] > 0)
            printf("PAT %d %lld %lld\n", p, g_cnt[p][0], g_cnt[p][1]);
#endif
    return 0;
}
#endif

static void initPriLearned() {
    PRI[25] = 143;
    PRI[400] = 150;
    PRI[1900] = 148;
    PRI[1901] = 174;
    PRI[1905] = 137;
    PRI[1906] = 146;
    PRI[1910] = 155;
    PRI[1925] = 145;
    PRI[1926] = 159;
    PRI[1930] = 136;
    PRI[1931] = 134;
    PRI[1932] = 144;
    PRI[1936] = 127;
    PRI[2000] = 188;
    PRI[2001] = 180;
    PRI[2005] = 176;
    PRI[2300] = 121;
    PRI[2301] = 149;
    PRI[2305] = 137;
    PRI[2376] = 155;
    PRI[2380] = 125;
    PRI[2676] = 110;
    PRI[2680] = 113;
    PRI[3801] = 142;
    PRI[3802] = 167;
    PRI[3805] = 114;
    PRI[3806] = 119;
    PRI[3807] = 120;
    PRI[3810] = 113;
    PRI[3811] = 115;
    PRI[3815] = 108;
    PRI[3876] = 156;
    PRI[3877] = 175;
    PRI[3880] = 130;
    PRI[3881] = 137;
    PRI[3882] = 137;
    PRI[3885] = 131;
    PRI[3886] = 131;
    PRI[3890] = 130;
    PRI[3952] = 203;
    PRI[3955] = 166;
    PRI[3956] = 163;
    PRI[3957] = 163;
    PRI[3960] = 161;
    PRI[3961] = 162;
    PRI[3965] = 174;
    PRI[4180] = 99;
    PRI[4181] = 109;
    PRI[4182] = 108;
    PRI[4185] = 98;
    PRI[4186] = 93;
    PRI[4190] = 91;
    PRI[4256] = 119;
    PRI[4257] = 130;
    PRI[4260] = 116;
    PRI[4261] = 124;
    PRI[4265] = 122;
    PRI[4332] = 136;
    PRI[4336] = 137;
    PRI[4340] = 139;
    PRI[4560] = 108;
    PRI[4561] = 104;
    PRI[4565] = 116;
    PRI[4636] = 123;
    PRI[4640] = 133;
}