// 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)
// 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 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;
    }
    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);
        }
    }
    // 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 <= 6) return 64;
    if (D > 50000) return 48; // huge maze: fewer epoch boundaries (CPU budget)
    if (D < 128 * K) return 48; // tiny maze: ~2 fat epochs beat 3 thin ones
    int w = 256 / K;
    if (w < 32) w = 32;
    return w;
}

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

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) { // gossip not worth it: static funnel
        funnel::B = 6 * MSGLEN;
        funnel::run();
        return 0;
    }

    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.order(2 * WTAKE, L); // second half of L = spare pool
        if (g_potMin <= RACE_POT) raceRun(); // components nearly touch: sprint solo
        size_t Lmain = min(L.size(), WTAKE);
        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]);
    ID = 0;
    m = (N + 1) / 2;
    HD = m * (m - 1);
    D = 2 * HD;

    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.order(2 * WTAKE, L);
        if (g_potMin <= RACE_POT) { race = true; break; }
        size_t Lmain = min(L.size(), WTAKE);
        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 W=%2d q=%4zu opens=%3lld cumQ=%lld t=%lld\n",
                epochs, g_potMin, W_e, found.size(), opens, queries, t);
#endif
    }
    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;
}