// Datacenter Imprisonment - v6: explorer blobs (small K) + blind split (large K).
//
// Maze structure (merlin's maze.rs make_maze):
//   - N odd, rooms at odd-odd cells are ALWAYS empty; only "connector" cells
//     (exactly one even coordinate) are unknown; W = 2m(m-1), m = (N+1)/2.
//     Empty cells form a spanning tree of the m*m rooms.
//
// Score metric = round number of the claim (all alive agents act each round;
// a message sent in round r is readable in round r+1). Master claims as soon
// as known-open edges connect the corner rooms: any path in a subgraph of a
// tree IS the unique tree path.
//
// EXPLORER mode (K <= 10, empirically better there):
//   - Workers run autonomous BFS floods ("blobs") of the room tree from
//     deterministic seeds (worker 1 at the goal, others on a uniform grid).
//     A blob never queries edges internal to its own visited set.
//   - Workers stream discovered OPEN edges as 17-bit indices, 6 bits/char,
//     R = 6*ML/17 records/message (sentinel-padded), on a fixed staggered
//     cadence -> the master's receive schedule is deterministic.
//   - Master runs a goal-biased DFS from the start over combined knowledge.
//   - A worker whose own blob spans both corners claims by itself.
//
// BLIND mode (K > 10, deterministic and near W/K):
//   - All W connectors are split into contiguous chunks; workers query their
//     chunk 1/round and stream dense bit-packed results (6 results/char,
//     remainder-sized message first), then halt; master queries a tail chunk
//     and interleaves receives at precomputed arrival rounds. Chunk sizes are
//     planned by binary search over an exact simulation of the schedule.
//   - Fallback on schedule anomaly: master self-queries unknowns while
//     draining survivors.

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

static int N, K, ID, ML;
static int m;        // rooms per side
static long long W;  // number of connectors
static long long B;  // blind mode: results per message = 6*ML

#ifndef EXPLORER_K
#define EXPLORER_K 6  // explorer mode when K <= this
#endif
static const long long SENT = (1 << 17) - 1;  // explorer sentinel (W <= 125500)

static vector<pair<int, int>> conns;  // canonical connector order (row-major)
static vector<long long> rowStart;    // canonical index of first connector in row r

static void wline(const char* s) {
    fputs(s, stdout);
    fputc('\n', stdout);
    fflush(stdout);
}

struct Dsu {
    vector<int> p;
    void init(int n) {
        p.resize(n);
        iota(p.begin(), p.end(), 0);
    }
    int find(int x) {
        while (p[x] != x) x = p[x] = p[p[x]];
        return x;
    }
    void uni(int a, int b) { p[find(a)] = find(b); }
};

// connector canonical idx -> (roomA, roomB, dir char from A to B)
static inline void edgeOf(long long idx, int& a, int& b, char& d) {
    int r = conns[idx].first, c = conns[idx].second;
    if (r % 2 == 0) {  // vertical, rooms above/below
        int i = r / 2 - 1, j = (c - 1) / 2;
        a = i * m + j;
        b = (i + 1) * m + j;
        d = 'D';
    } else {  // horizontal
        int i = (r - 1) / 2, j = c / 2 - 1;
        a = i * m + j;
        b = i * m + (j + 1);
        d = 'R';
    }
}

// connector cell (r,c) -> canonical index
static inline long long connIdxOf(int r, int c) {
    return rowStart[r] + (r % 2 ? (c - 2) / 2 : (c - 1) / 2);
}

// goal-biased dirs: D, R, U, L
static const int DI[4] = {1, 0, -1, 0};
static const int DJ[4] = {0, 1, 0, -1};

// reconstruct the start->goal path over known-open adjacency; "*" if absent
static string buildPath(const vector<unsigned char>& openDR) {
    const int start = 0, goal = m * m - 1;
    if (start == goal) return string();
    vector<int> par((size_t)m * m, -1), pdir((size_t)m * m, 0);
    vector<int> q;
    q.push_back(start);
    par[start] = start;
    for (size_t h = 0; h < q.size() && par[goal] == -1; h++) {
        int u = q[h], i = u / m, j = u % m;
        auto push = [&](int v, char d) {
            if (par[v] == -1) {
                par[v] = u;
                pdir[v] = (int)d;
                q.push_back(v);
            }
        };
        if (openDR[u] & 1) push(u + m, 'D');
        if (openDR[u] & 2) push(u + 1, 'R');
        if (i > 0 && (openDR[u - m] & 1)) push(u - m, 'U');
        if (j > 0 && (openDR[u - 1] & 2)) push(u - 1, 'L');
    }
    if (par[goal] == -1) return string("*");
    string path;
    for (int v = goal; v != start; v = par[v]) {
        path.push_back((char)pdir[v]);
        path.push_back((char)pdir[v]);
    }
    reverse(path.begin(), path.end());
    return path;
}

// ======================= EXPLORER mode (K <= EXPLORER_K) =======================

namespace explorer {

int R;  // records per message
int P;  // send cadence in rounds (R+1)

// deterministic seed room for worker w (1..K-1)
int seedOf(int w) {
    const int goal = m * m - 1;
    if (w == 1) return goal;
    int idx = w - 2;         // 0-based grid slot
    int nw = max(K - 2, 1);  // workers on the grid
    int g = 1;
    while (g * g < nw) g++;
    int a = idx / g, b = idx % g;
    int i = (int)(((long long)(2 * a + 1) * m) / (2 * g));
    int j = (int)(((long long)(2 * b + 1) * m) / (2 * g));
    i = min(i, m - 1);
    j = min(j, m - 1);
    int room = i * m + j;
    if (room == 0 || room == goal) room = (i * m + j + m + 1) % (m * m);
    return room;
}

static const int CS = 12;  // super-cell side (rooms) for territory hints

// enumerate the connector indices of a SIDE x SIDE room window centred on
// room T (clamped); deterministic order shared by master and workers
static void windowEdges(int T, vector<long long>& out) {
    const int SIDE = 19;
    int side = min(SIDE, m);
    int i0 = max(0, min(T / m - side / 2, m - side));
    int j0 = max(0, min(T % m - side / 2, m - side));
    out.clear();
    for (int i = i0; i < i0 + side; i++)
        for (int j = j0; j < j0 + side; j++) {
            if (i + 1 < i0 + side) out.push_back(connIdxOf(2 * i + 2, 2 * j + 1));
            if (j + 1 < j0 + side) out.push_back(connIdxOf(2 * i + 1, 2 * j + 2));
        }
}

int run() {
    R = (6 * ML) / 17;
    P = R + 1;
    const int start = 0, goal = m * m - 1;
    const int nWorkers = K - 1;
    const bool streaming = (R >= 4) && (W < SENT);
    const int g = (m + CS - 1) / CS;  // super-cell grid side
    const int NC = g * g;             // number of super-cells
    const bool hints = streaming && NC >= 4 && NC <= 6 * ML && nWorkers >= 2;

    auto cellOf = [&](int room) { return (room / m / CS) * g + (room % m) / CS; };

    // per-worker first-send round (staggered), in [2, P]
    auto phaseOf = [&](int w) -> long long {
        if (nWorkers <= 0) return 2;
        long long ph = 2 + ((long long)(w - 1) * P) / nWorkers;
        return min<long long>(ph, (long long)P);
    };
    // hint polls: mid-window, every second window
    auto firstPoll = [&](int w) -> long long { return phaseOf(w) + P / 2; };

    vector<signed char> know(W, -1);
    vector<unsigned char> visited((size_t)m * m, 0);
    vector<unsigned char> openDR((size_t)m * m, 0);
    Dsu dsu;
    dsu.init(m * m);

    auto markOpen = [&](long long idx) {
        int a, b;
        char d;
        edgeOf(idx, a, b, d);
        dsu.uni(a, b);
        openDR[a] |= (d == 'D') ? 1 : 2;
    };

    string rep;

    if (ID != 0) {
        // ---------------- worker: autonomous blob explorer ----------------
        if (!streaming) {
            wline("halt");
            return 0;
        }
        vector<unsigned char> foreign(NC, 0);  // latest hint: cells owned by others
        deque<pair<int, int>> fr;              // main frontier (room, next dir)
        deque<pair<int, int>> defer;           // (room, dir) postponed by hints
        int seed = seedOf(ID);
        visited[seed] = 1;
        fr.push_back({seed, 0});

        // advance until one query is emitted; -1 if nothing to do (no command)
        auto stepW = [&]() -> long long {
            for (;;) {
                int u, dir;
                bool fromDefer = false;
                if (!fr.empty()) {
                    auto& f = fr.front();
                    if (f.second == 4) {
                        fr.pop_front();
                        continue;
                    }
                    u = f.first;
                    dir = f.second++;
                } else if (!defer.empty()) {
                    u = defer.front().first;
                    dir = defer.front().second;
                    defer.pop_front();
                    fromDefer = true;
                } else
                    return -1;
                int i = u / m + DI[dir], j = u % m + DJ[dir];
                if (i < 0 || i >= m || j < 0 || j >= m) continue;
                int v = i * m + j;
                if (visited[v]) continue;
                if (!fromDefer && foreign[cellOf(v)]) {  // someone else's territory
                    defer.push_back({u, dir});
                    continue;
                }
                int r = (u / m) * 2 + 1 + DI[dir], c = (u % m) * 2 + 1 + DJ[dir];
                long long idx = connIdxOf(r, c);
                if (know[idx] != -1) continue;
                printf("? %d %d\n", r, c);
                fflush(stdout);
                if (!(cin >> rep)) exit(0);
                int bit = rep[0] == '1';
                know[idx] = (signed char)bit;
                if (bit) {
                    markOpen(idx);
                    visited[v] = 1;
                    fr.push_back({v, 0});
                }
                return idx;
            }
        };

        long long nextSend = phaseOf(ID);
        long long nextPoll = hints ? firstPoll(ID) : LLONG_MAX;
        vector<long long> recs;
        recs.reserve(R + 1);
        for (long long t = 1;; t++) {
            if (dsu.find(start) == dsu.find(goal)) {  // my own blob spans both corners
                string path = buildPath(openDR);
                if (path != "*") {
                    printf("! %s\n", path.c_str());
                    fflush(stdout);
                    return 0;
                }
            }
            if (t == nextSend) {
                string body;
                body.reserve(3 * R);
                unsigned int acc = 0;
                int nb = 0;
                for (int k = 0; k < R; k++) {
                    unsigned int v =
                        (k < (int)recs.size()) ? (unsigned int)recs[k] : (unsigned int)SENT;
                    acc |= v << nb;
                    nb += 17;
                    while (nb >= 6) {
                        body.push_back((char)('0' + (acc & 63)));
                        acc >>= 6;
                        nb -= 6;
                    }
                }
                if (nb > 0) body.push_back((char)('0' + (acc & 63)));
                printf("> 0 %s\n", body.c_str());
                fflush(stdout);
                if (!(cin >> rep)) return 0;  // "OK"
                recs.clear();
                nextSend += P;
                continue;
            }
            if (t == nextPoll) {
                wline("< 0");
                string snd, body;
                if (!(cin >> snd >> body)) return 0;
                if (snd != "-") {
                    for (int c = 0; c < NC; c++) {
                        int ch = body[c / 6] - '0';
                        foreign[c] = (ch >> (c % 6)) & 1;
                    }
                    // re-filter: nothing needed; defer entries re-checked on pop
                }
                nextPoll += 2LL * P;
                continue;
            }
            long long idx = stepW();
            if (idx >= 0) {
                if (know[idx] == 1) recs.push_back(idx);
            } else {
                wline(".");
                if (!(cin >> rep)) return 0;
            }
        }
    }

    // ---------------- master ----------------
    deque<pair<int, int>> fr;
    visited[start] = 1;
    fr.push_back({start, 0});
    // goal-biased DFS from start over combined knowledge
    auto stepM = [&]() -> bool {  // true if a command was emitted
        while (!fr.empty()) {
            auto& f = fr.back();
            int u = f.first;
            if (f.second == 4) {
                fr.pop_back();
                continue;
            }
            int dir = f.second++;
            int i = u / m + DI[dir], j = u % m + DJ[dir];
            if (i < 0 || i >= m || j < 0 || j >= m) continue;
            int v = i * m + j;
            if (visited[v]) continue;
            int r = (u / m) * 2 + 1 + DI[dir], c = (u % m) * 2 + 1 + DJ[dir];
            long long idx = connIdxOf(r, c);
            if (know[idx] == 0) continue;
            if (know[idx] == 1) {  // streamed open - free traverse
                visited[v] = 1;
                fr.push_back({v, 0});
                continue;
            }
            printf("? %d %d\n", r, c);
            fflush(stdout);
            if (!(cin >> rep)) exit(0);
            int bit = rep[0] == '1';
            know[idx] = (signed char)bit;
            if (bit) {
                markOpen(idx);
                visited[v] = 1;
                fr.push_back({v, 0});
            }
            return true;
        }
        return false;
    };

    vector<long long> nextDue(K, LLONG_MAX), nextPollDue(K, LLONG_MAX);
    if (streaming)
        for (int w = 1; w < K; w++) nextDue[w] = phaseOf(w) + 1;
    if (hints)
        for (int w = 1; w < K; w++) nextPollDue[w] = firstPoll(w);

    // territory: first worker whose open edge touches a super-cell owns it
    vector<int> cellOwner(NC, -1);
    long long version = 0;
    vector<long long> sentVer(K, -1);
    auto claimCell = [&](int room, int agent) {
        int c = cellOf(room);
        if (cellOwner[c] == -1) {
            cellOwner[c] = agent;
            version++;
        }
    };

    auto decode = [&](const string& body, int sender) {
        unsigned long long acc = 0;
        int nb = 0;
        size_t pos = 0;
        for (int k = 0; k < R; k++) {
            while (nb < 17 && pos < body.size()) {
                acc |= (unsigned long long)(body[pos++] - '0') << nb;
                nb += 6;
            }
            unsigned int v = (unsigned int)(acc & SENT);
            acc >>= 17;
            nb -= 17;
            if ((long long)v == SENT || (long long)v >= W) continue;
            int a, b;
            char d;
            edgeOf(v, a, b, d);
            claimCell(a, sender);
            claimCell(b, sender);
            if (know[v] == -1) {
                know[v] = 1;
                markOpen(v);
            }
        }
    };

    for (long long t = 1;; t++) {
        if (dsu.find(start) == dsu.find(goal)) {
            string path = buildPath(openDR);
            if (path != "*") {
                printf("! %s\n", path.c_str());
                fflush(stdout);
                return 0;
            }
        }

        // 1) hint send with a hard deadline (worker polls at t+1)
        int hw = -1;
        for (int w = 1; w < K; w++)
            if (nextPollDue[w] == t + 1) {
                if (sentVer[w] < version && hw == -1) hw = w;
                nextPollDue[w] += 2LL * P;
            }
        if (hw != -1) {
            string body((NC + 5) / 6, '0');
            for (int c = 0; c < NC; c++)
                if (cellOwner[c] != -1 && cellOwner[c] != hw)
                    body[c / 6] = (char)(body[c / 6] + (1 << (c % 6)));
            printf("> %d %s\n", hw, body.c_str());
            fflush(stdout);
            if (!(cin >> rep)) return 0;  // "OK"
            sentVer[hw] = version;
            continue;
        }

        // 2) due stream receives
        int due = -1;
        for (int w = 1; w < K; w++)
            if (nextDue[w] <= t) {
                due = w;
                break;
            }
        if (due != -1) {
            wline("< ?");
            string snd, body;
            if (!(cin >> snd >> body)) return 0;
            if (snd == "-") {
                for (int w = 1; w < K; w++)  // due workers are dead
                    if (nextDue[w] <= t) nextDue[w] = LLONG_MAX;
            } else {
                int s = atoi(snd.c_str());
                if (s >= 1 && s < K) {
                    decode(body, s);
                    if (nextDue[s] != LLONG_MAX) nextDue[s] += P;
                }
            }
            continue;
        }

        // 3) own exploration
        if (!stepM()) {
            wline(".");
            if (!(cin >> rep)) return 0;
        }
    }
    return 0;
}

}  // namespace explorer

// ================= BIDIR mode (K <= EXPLORER_K): best-first fronts =============
//
// Agents never move; a query is the only cost. So each agent runs a greedy
// best-first flood (priority queue over frontier connectors) instead of DFS:
//   - master (id 0): flood from START keyed by euclid dist to GOAL;
//   - worker 1:      flood from GOAL keyed by euclid dist to START;
//   - workers 2..:   flood from seeds on the (1,1)-(N,N) diagonal keyed by
//                    focal sum (dist_to_start + dist_to_goal) -> the blob grows
//                    an ellipse-corridor segment both ways, forming a chain.
// Workers stream discovered OPEN edges (17-bit indices) to the master exactly
// as in explorer mode. The master absorbs any streamed component the moment it
// touches its start-connected region (free traversal closure), which teleports
// its frontier to the far end of the merged corridor. Claims on connectivity.

namespace bidir {

#ifndef CHASE
#define CHASE 1  // corridor-BFS chasing (master retargets + worker directives)
#endif
#ifndef CHASE_N
#define CHASE_N 140  // chase wins from ~N=151 (measured; loses at N<=121)
#endif
// chase pays off only on long games (short games thrash on directive churn)
static bool chaseOn() { return CHASE && N >= CHASE_N; }

int R;  // records per message
int P;  // send cadence in rounds (R+1)

// deterministic seed room for worker w (1..K-1): w=1 at goal, others on diagonal
int seedOf(int w) {
    const int goal = m * m - 1;
    if (w == 1) return goal;
    double f = (double)(w - 1) / (double)max(K - 1, 2);
    int i = (int)llround(f * (m - 1));
    int room = i * m + i;
    if (room == 0) room = m + 1;
    if (room == goal) room = goal - m - 1;
    return room;
}

// enumerate the connector indices of a SIDE x SIDE room window centred on
// room T (clamped); deterministic order shared by master and workers
static void windowEdges(int T, vector<long long>& out) {
    const int SIDE = 19;
    int side = min(SIDE, m);
    int i0 = max(0, min(T / m - side / 2, m - side));
    int j0 = max(0, min(T % m - side / 2, m - side));
    out.clear();
    for (int i = i0; i < i0 + side; i++)
        for (int j = j0; j < j0 + side; j++) {
            if (i + 1 < i0 + side) out.push_back(connIdxOf(2 * i + 2, 2 * j + 1));
            if (j + 1 < j0 + side) out.push_back(connIdxOf(2 * i + 1, 2 * j + 2));
        }
}

int run() {
    R = (6 * ML) / 17;
    P = R + 1;
    const int start = 0, goal = m * m - 1;
    const int nWorkers = K - 1;
    const bool streaming = (R >= 4) && (W < SENT);

    // per-worker first-send round (staggered), in [2, P]
    auto phaseOf = [&](int w) -> long long {
        if (nWorkers <= 0) return 2;
        long long ph = 2 + ((long long)(w - 1) * P) / nWorkers;
        return min<long long>(ph, (long long)P);
    };

    vector<signed char> know(W, -1);
    vector<unsigned char> visited((size_t)m * m, 0);
    vector<unsigned char> openDR((size_t)m * m, 0);
    Dsu dsu;
    dsu.init(m * m);

    auto markOpen = [&](long long idx) {
        int a, b;
        char d;
        edgeOf(idx, a, b, d);
        dsu.uni(a, b);
        openDR[a] |= (d == 'D') ? 1 : 2;
    };

    // priority key: dist to current chase target (master chases the goal-side
    // component; w1 chases start; both retargetable). Middle workers grow a
    // focal-sum corridor blob until the master sends them a directive.
    int target = (ID == 1) ? 0 : m * m - 1;
    bool useFocal = (ID >= 2);
    vector<int> dgf;  // master: BFS dist to goal component via possibly-open edges
    auto key = [&](int v) -> long long {
        if (!dgf.empty()) return (long long)dgf[v] << 11;
        double i = v / m, j = v % m;
        double val;
        if (useFocal) {
            double ds = sqrt(i * i + j * j);
            double gi = m - 1 - i, gj = m - 1 - j;
            val = ds + sqrt(gi * gi + gj * gj);
        } else {
            double ti = target / m, tj = target % m;
            val = sqrt((i - ti) * (i - ti) + (j - tj) * (j - tj));
        }
        return (long long)(val * 1024.0);
    };

    struct PQE {
        long long k;
        long long ord;
        int u;
        int dir;
    };
    struct Cmp {
        bool operator()(const PQE& a, const PQE& b) const {
            if (a.k != b.k) return a.k > b.k;
            return a.ord < b.ord;  // LIFO tie-break (locality)
        }
    };
    priority_queue<PQE, vector<PQE>, Cmp> pq;
    long long ordc = 0;

    // mark u visited; walk known-open closure; push unknown frontier edges
    vector<int> stk;
    vector<int> visList;  // rooms in my visited closure (master: start component)
    auto absorb = [&](int u0) {
        if (visited[u0]) return;
        visited[u0] = 1;
        stk.push_back(u0);
        visList.push_back(u0);
        while (!stk.empty()) {
            int u = stk.back();
            stk.pop_back();
            for (int dir = 0; dir < 4; dir++) {
                int i = u / m + DI[dir], j = u % m + DJ[dir];
                if (i < 0 || i >= m || j < 0 || j >= m) continue;
                int v = i * m + j;
                if (visited[v]) continue;
                int r = (u / m) * 2 + 1 + DI[dir], c = (u % m) * 2 + 1 + DJ[dir];
                long long idx = connIdxOf(r, c);
                if (know[idx] == 1) {
                    visited[v] = 1;
                    stk.push_back(v);
                    visList.push_back(v);
                } else if (know[idx] == -1) {
                    pq.push({key(v), ordc++, u, dir});
                }
            }
        }
    };

    // rebuild pq from scratch under the current key (after a retarget)
    auto rebuildPQ = [&]() {
        priority_queue<PQE, vector<PQE>, Cmp> empty;
        pq.swap(empty);
        for (int u : visList)
            for (int dir = 0; dir < 4; dir++) {
                int i = u / m + DI[dir], j = u % m + DJ[dir];
                if (i < 0 || i >= m || j < 0 || j >= m) continue;
                int v = i * m + j;
                if (visited[v]) continue;
                long long idx = connIdxOf((u / m) * 2 + 1 + DI[dir], (u % m) * 2 + 1 + DJ[dir]);
                if (know[idx] == -1) pq.push({key(v), ordc++, u, dir});
            }
    };

    // BFS distance field from `srcs` through possibly-open edges (edges I know
    // are walls block; unknown/open pass). Used to key the pq so fronts route
    // around known coastlines instead of grinding on them (euclid does).
    vector<int> bfsPar, bfsQ;
    auto computeField = [&](const vector<int>& srcs) {
        dgf.assign((size_t)m * m, INT_MAX);
        bfsPar.assign((size_t)m * m, -1);
        bfsQ.clear();
        for (int s0 : srcs) {
            dgf[s0] = 0;
            bfsQ.push_back(s0);
        }
        for (size_t h = 0; h < bfsQ.size(); h++) {
            int u = bfsQ[h];
            for (int dir = 0; dir < 4; dir++) {
                int i = u / m + DI[dir], j = u % m + DJ[dir];
                if (i < 0 || i >= m || j < 0 || j >= m) continue;
                int v = i * m + j;
                if (dgf[v] != INT_MAX) continue;
                long long idx = connIdxOf((u / m) * 2 + 1 + DI[dir], (u % m) * 2 + 1 + DJ[dir]);
                if (know[idx] == 0) continue;
                dgf[v] = dgf[u] + 1;
                bfsPar[v] = u;
                bfsQ.push_back(v);
            }
        }
    };

    string rep;
    // emit exactly one query; returns queried idx, or -1 if frontier empty
    auto step = [&]() -> long long {
        while (!pq.empty()) {
            PQE e = pq.top();
            pq.pop();
            int u = e.u, dir = e.dir;
            int i = u / m + DI[dir], j = u % m + DJ[dir];
            int v = i * m + j;
            if (visited[v]) continue;
            int r = (u / m) * 2 + 1 + DI[dir], c = (u % m) * 2 + 1 + DJ[dir];
            long long idx = connIdxOf(r, c);
            if (know[idx] == 0) continue;
            if (know[idx] == 1) {  // streamed open - free traverse
                absorb(v);
                continue;
            }
            printf("? %d %d\n", r, c);
            fflush(stdout);
            if (!(cin >> rep)) exit(0);
            int bit = rep[0] == '1';
            know[idx] = (signed char)bit;
            if (bit) {
                markOpen(idx);
                absorb(v);
            }
            return idx;
        }
        return -1;
    };

    static const bool dbg = getenv("D_DEBUG") != nullptr;
    auto tryClaim = [&](long long t) -> bool {
        if (dsu.find(start) != dsu.find(goal)) return false;
        string path = buildPath(openDR);
        if (path == "*") return false;
        if (dbg) fprintf(stderr, "[claim] id=%d t=%lld\n", ID, t);
        printf("! %s\n", path.c_str());
        fflush(stdout);
        return true;
    };

    if (ID != 0) {
        // ---------------- worker: streaming best-first front ----------------
        if (!streaming) {
            wline("halt");
            return 0;
        }
        absorb(seedOf(ID));
        long long nextSend = phaseOf(ID);
        long long nextPoll = chaseOn() ? phaseOf(ID) + P / 2 : LLONG_MAX;  // directive poll
        long long nextRetgtW = 64;
        vector<long long> recs;
        recs.reserve(R + 1);
        for (long long t = 1;; t++) {
            if (tryClaim(t)) return 0;
            if (t == nextPoll) {
                wline("< 0");
                string snd, body;
                if (!(cin >> snd >> body)) return 0;
                if (snd != "-" && body.size() >= 3) {
                    int T = (body[0] - '0') | ((body[1] - '0') << 6) | ((body[2] - '0') << 12);
                    if (T >= 0 && T < m * m) {
                        // knowledge bitmap around the target: 2 bits per edge
                        if (body.size() >= 4) {
                            vector<long long> we;
                            windowEdges(T, we);
                            for (size_t k = 0; k < we.size() && 3 + k / 3 < body.size(); k++) {
                                int st = ((body[3 + k / 3] - '0') >> (2 * (k % 3))) & 3;
                                long long idx = we[k];
                                if (st == 0 || know[idx] != -1) continue;
                                know[idx] = (st == 1);
                                if (st == 1) {
                                    markOpen(idx);
                                    int a2, b2;
                                    char d2;
                                    edgeOf(idx, a2, b2, d2);
                                    if (visited[a2] && !visited[b2])
                                        absorb(b2);
                                    else if (visited[b2] && !visited[a2])
                                        absorb(a2);
                                }
                            }
                        }
                        if (useFocal || T != target) {
                            target = T;
                            useFocal = false;
                        }
                        computeField({target});
                        rebuildPQ();
                    }
                }
                nextPoll += P;
                continue;
            }
            if (t >= nextRetgtW && !useFocal) {  // wall-aware re-key (no round cost)
                computeField({target});
                rebuildPQ();
                nextRetgtW = t + 64 + (long long)visList.size() / 256;
            }
            if (t == nextSend) {
                string body;
                body.reserve(3 * R);
                unsigned int acc = 0;
                int nb = 0;
                for (int k = 0; k < R; k++) {
                    unsigned int v =
                        (k < (int)recs.size()) ? (unsigned int)recs[k] : (unsigned int)SENT;
                    acc |= v << nb;
                    nb += 17;
                    while (nb >= 6) {
                        body.push_back((char)('0' + (acc & 63)));
                        acc >>= 6;
                        nb -= 6;
                    }
                }
                if (nb > 0) body.push_back((char)('0' + (acc & 63)));
                printf("> 0 %s\n", body.c_str());
                fflush(stdout);
                if (!(cin >> rep)) return 0;  // "OK"
                recs.clear();
                nextSend += P;
                continue;
            }
            long long idx = step();
            if (idx >= 0) {
                if (know[idx] == 1) recs.push_back(idx);
            } else {
                wline(".");
                if (!(cin >> rep)) return 0;
            }
        }
    }

    // ---------------- master ----------------
    absorb(start);
    vector<long long> nextDue(K, LLONG_MAX);
    if (streaming)
        for (int w = 1; w < K; w++) nextDue[w] = phaseOf(w) + 1;

    // chase: retarget at the goal-side component cell nearest to my component
    // (approximate closest pair by alternating minimization), rebuild pq on change
    auto sqd = [&](int a, int b) -> long long {
        long long di = a / m - b / m, dj = a % m - b % m;
        return di * di + dj * dj;
    };
    vector<int> repw(K, -1);           // a room known to be in worker w's blob
    vector<int> lastTgt(K, -1);        // last directive sent to worker w
    vector<int> pendTgt(K, -1);        // directive waiting to be sent
    vector<long long> sendOK(K, 0);    // earliest round to send to w (rate limit)
    auto retarget = [&]() {
        // corridor field from the goal component (see computeField)
        int gRoot = dsu.find(goal);
        vector<int> srcs;
        for (int r_ = 0; r_ < m * m; r_++)
            if (dsu.find(r_) == gRoot) srcs.push_back(r_);
        computeField(srcs);
        // my corridor endpoint = my room closest (corridor-wise) to goal comp
        int a = start;
        long long bd = LLONG_MAX;
        for (int v : visList)
            if (dgf[v] < bd) bd = dgf[v], a = v;
        rebuildPQ();  // own key follows the refreshed dgf
        if (!chaseOn()) return;  // directives only pay off on longer games
        // primary corridor a -> goal component
        vector<int> path;
        for (int v = a; v != -1; v = bfsPar[v]) path.push_back(v);
        // second, edge-disjoint corridor (hedge + spreads workers at high K):
        // block the unknown edges of path1, recompute the field, re-extract
        vector<int> path2;
        if (K >= 5 && path.size() >= 3) {
            vector<pair<long long, signed char>> saved;
            for (size_t i = 0; i + 1 < path.size(); i++) {
                int u = path[i], v = path[i + 1];
                int r = (u / m) + (v / m) + 1, c = (u % m) + (v % m) + 1;
                long long idx = connIdxOf(r, c);
                if (know[idx] == -1) {
                    saved.push_back({idx, know[idx]});
                    know[idx] = 0;
                }
            }
            vector<int> dgfSave = dgf;
            computeField(srcs);
            int a2 = -1;
            long long bd2 = LLONG_MAX;
            for (int v : visList)
                if (dgf[v] < bd2) bd2 = dgf[v], a2 = v;
            if (a2 >= 0 && bd2 < INT_MAX && bd2 <= 2 * bd + 16)
                for (int v = a2; v != -1; v = bfsPar[v]) path2.push_back(v);
            for (auto& [idx, kv] : saved) know[idx] = kv;
            dgf.swap(dgfSave);  // master's key keeps the REAL field
        }
        // spread worker targets: w1 digs toward my end of path1; middle
        // workers alternate between the two corridors' evenly spaced waypoints
        int n1 = 0, n2 = 0;
        for (int w = 2; w < K; w++)
            (path2.empty() || (w & 1)) ? n1++ : n2++;
        int i1 = 0, i2 = 0;
        for (int w = 1; w < K; w++) {
            int T;
            if (w == 1)
                T = a;
            else if (path2.empty() || (w & 1)) {
                double f = (double)(++i1) / (double)(n1 + 1);
                T = path[min((size_t)(f * (path.size() - 1)), path.size() - 1)];
            } else {
                double f = (double)(++i2) / (double)(n2 + 1);
                T = path2[min((size_t)(f * (path2.size() - 1)), path2.size() - 1)];
            }
            if (lastTgt[w] == -1 || sqd(T, lastTgt[w]) >= 9) pendTgt[w] = T;
        }
    };

    long long nDec = 0;
    auto decode = [&](const string& body, int sender) {
        unsigned long long acc = 0;
        int nb = 0;
        size_t pos = 0;
        for (int k = 0; k < R; k++) {
            while (nb < 17 && pos < body.size()) {
                acc |= (unsigned long long)(body[pos++] - '0') << nb;
                nb += 6;
            }
            unsigned int v = (unsigned int)(acc & SENT);
            acc >>= 17;
            nb -= 17;
            if ((long long)v == SENT || (long long)v >= W) continue;
            if (dbg) nDec++;
            {
                int a, b;
                char d;
                edgeOf(v, a, b, d);
                repw[sender] = a;
            }
            if (know[v] == -1) {
                know[v] = 1;
                markOpen(v);
                int a, b;
                char d;
                edgeOf(v, a, b, d);
                if (visited[a] && !visited[b])
                    absorb(b);
                else if (visited[b] && !visited[a])
                    absorb(a);
            }
        }
    };

    long long nextRetgt = 48;
    for (long long t = 1;; t++) {
        if (dbg && (t % 2000) == 0)
            fprintf(stderr, "[m] t=%lld vis=%zu dec=%lld\n", t, visList.size(), nDec);
        if (tryClaim(t)) return 0;
        if (t >= nextRetgt) {
            retarget();
            nextRetgt = t + 48 + (long long)visList.size() / 256;
        }

        int due = -1;
        for (int w = 1; w < K; w++)
            if (nextDue[w] <= t) {
                due = w;
                break;
            }
        if (due != -1) {
            wline("< ?");
            string snd, body;
            if (!(cin >> snd >> body)) return 0;
            if (snd == "-") {
                for (int w = 1; w < K; w++)  // due workers are dead
                    if (nextDue[w] <= t) nextDue[w] = LLONG_MAX;
            } else {
                int s = atoi(snd.c_str());
                if (s >= 1 && s < K) {
                    decode(body, s);
                    if (nextDue[s] != LLONG_MAX) nextDue[s] += P;
                }
            }
            continue;
        }

        // send one pending directive (rate-limited to one per worker per window)
        int sw = -1;
        if (chaseOn())
            for (int w = 1; w < K; w++)
            if (pendTgt[w] != -1 && t >= sendOK[w] && pendTgt[w] != lastTgt[w]) {
                sw = w;
                break;
            }
        if (sw != -1) {
            int T = pendTgt[sw];
            string msg;
            msg.push_back((char)('0' + (T & 63)));
            msg.push_back((char)('0' + ((T >> 6) & 63)));
            msg.push_back((char)('0' + ((T >> 12) & 63)));
            if (ML >= 240) {  // knowledge bitmap: kills cross-agent duplication
                vector<long long> we;
                windowEdges(T, we);
                int acc = 0, nb = 0;
                for (size_t k = 0; k < we.size(); k++) {
                    int st = (know[we[k]] == -1) ? 0 : (know[we[k]] == 1 ? 1 : 2);
                    acc |= st << (2 * (k % 3));
                    if (k % 3 == 2 || k + 1 == we.size()) {
                        msg.push_back((char)('0' + acc));
                        acc = 0;
                    }
                }
            }
            printf("> %d %s\n", sw, msg.c_str());
            fflush(stdout);
            if (!(cin >> rep)) return 0;  // "OK"
            lastTgt[sw] = T;
            pendTgt[sw] = -1;
            sendOK[sw] = t + P;
            continue;
        }

        long long idx = step();
        if (idx < 0) {
            wline(".");
            if (!(cin >> rep)) return 0;
        }
    }
    return 0;
}

}  // namespace bidir

// ========================= BLIND mode (K > EXPLORER_K) =========================

namespace blind {

// send-block size: results per message. Smaller than the message capacity B
// so the master's knowledge tracks coverage with bounded lag and it can claim
// early once the elliptical prefix connects the corners.
long long SB;
bool endgame;  // gap-focus endgame enabled (workers poll after each send)

// worker cycle: block queries, 1 send round, then (endgame) 1 poll round.
// polls let the master broadcast a "gap focus" hint mid-run.
long long pollCost() { return endgame ? 1 : 0; }
// rounds used by a worker with share s
long long roundsFor(long long s) {
    if (s == 0) return 0;
    long long nb = (s + SB - 1) / SB;
    return s + nb * (1 + pollCost());
}
// max share s with roundsFor(s) <= F
long long capFor(long long F) {
    if (F < 2) return 0;
    long long lo = 0, hi = F;
    while (lo < hi) {
        long long mid = (lo + hi + 1) / 2;
        if (roundsFor(mid) <= F)
            lo = mid;
        else
            hi = mid - 1;
    }
    return lo;
}
// send rounds (and optionally poll rounds) for share s, remainder-first
void sendRounds(long long s, vector<long long>& out, vector<long long>* polls = nullptr) {
    out.clear();
    if (polls) polls->clear();
    if (s == 0) return;
    long long t = 0, rem = s, block = (s - 1) % SB + 1;
    while (rem > 0) {
        long long take = min(block, rem);
        t += take;
        rem -= take;
        t += 1;
        out.push_back(t);
        if (endgame) {
            t += 1;
            if (polls) polls->push_back(t);
        }
        block = SB;
    }
}

struct Sched {
    long long C = 0;
    vector<long long> shares;  // workers 1..K-1
    long long masterShare = 0;
    vector<pair<long long, int>> arrivals;  // (readable round, sender), sorted
};

bool buildSched(long long C, Sched& out) {
    int nw = K - 1;
    out.shares.assign(max(nw, 0), 0);
    long long rem = W;
    for (int w = 1; w <= nw; w++) {
        long long F = C - 1 - w;
        long long s = min(capFor(F), rem);
        out.shares[w - 1] = s;
        rem -= s;
    }
    out.arrivals.clear();
    vector<long long> sr;
    for (int w = 1; w <= nw; w++) {
        sendRounds(out.shares[w - 1], sr);
        for (long long t : sr) out.arrivals.push_back({t + 1, w});
    }
    sort(out.arrivals.begin(), out.arrivals.end());
    size_t ai = 0;
    long long own = 0;
    for (long long t = 1; t <= C - 1; t++) {
        if (ai < out.arrivals.size() && out.arrivals[ai].first <= t)
            ai++;
        else
            own++;
    }
    if (ai < out.arrivals.size()) return false;
    if (own < rem) return false;
    out.masterShare = rem;
    out.C = C;
    return true;
}

Sched planSchedule() {
    Sched s;
    long long lo = 2, hi = 2 * W + K + 10;
    while (lo < hi) {
        long long mid = (lo + hi) / 2;
        Sched tmp;
        if (buildSched(mid, tmp))
            hi = mid;
        else
            lo = mid + 1;
    }
    while (!buildSched(lo, s)) lo++;
    return s;
}

int run() {
    B = 6LL * ML;
#ifdef NO_ENDGAME
    endgame = false;
#else
    // K <= 40: the hint broadcast costs K-1 master rounds; at K=45-50 that
    // outweighs the focus benefit (measured +12..21% at N=441)
    endgame = (m >= 76) && (K >= 10) && (K <= 40) && (ML >= 32) && (W / K >= 1500);
#endif
    SB = max(64LL, min(B, W / max(K - 1, 1) / 12 + 1));
    if (endgame) SB = min(SB, 192LL);  // bounded poll cadence -> timely hints
    const int start = 0, goal = m * m - 1;

    Sched sch = planSchedule();

    // Coverage order: sort connectors by focal-sum distance to the two corner
    // cells (paths concentrate near small focal sums), so the swept prefix
    // grows an ellipse from both corners; the master claims on connectivity,
    // typically at ~0.75 of full coverage. Assign sorted positions to
    // queriers round-robin (stride) so the global covered set is always a
    // prefix of this order.
    vector<int> order(W);
    {
        vector<pair<long long, int>> keyed(W);
        for (int e = 0; e < W; e++) {
            double r = conns[e].first, c = conns[e].second;
            double ds = sqrt((r - 1) * (r - 1) + (c - 1) * (c - 1));
            double dg = sqrt((N - r) * (N - r) + (N - c) * (N - c));
            keyed[e] = {(long long)((ds + dg) * 1024.0), e};
        }
        sort(keyed.begin(), keyed.end());
        for (int i = 0; i < W; i++) order[i] = keyed[i].second;
    }
    // per-querier position lists (querier = agent id; master 0 included)
    vector<vector<int>> plist(K);
    {
        vector<long long> cap(K);
        cap[0] = sch.masterShare;
        for (int w = 1; w < K; w++) cap[w] = sch.shares[w - 1];
        for (int q = 0; q < K; q++) plist[q].reserve(cap[q]);
        vector<int> active;
        for (int w = 1; w < K; w++)
            if (cap[w] > 0) active.push_back(w);
        if (cap[0] > 0) active.push_back(0);
        size_t ptr = 0;
        for (int p = 0; p < W && !active.empty(); p++) {
            ptr %= active.size();
            int q = active[ptr];
            plist[q].push_back(order[p]);
            if ((long long)plist[q].size() >= cap[q])
                active.erase(active.begin() + ptr);
            else
                ptr++;
        }
    }

    if (ID != 0) {
        // ---------------- worker: strided streamer ----------------
        long long s = sch.shares[ID - 1];
        if (s == 0) {
            wline("halt");
            return 0;
        }
        vector<int> mine = plist[ID];
        string body, rep;
        // gap-focus state: after a hint (center room, radius) the remaining
        // items are reordered (inside-radius by distance first) and results
        // switch to explicit 'p'-marked (idx*2|bit) 18-bit record messages
        bool focus = false;
        vector<int> wps;  // polyline waypoints (rooms)
        int hr = 0;
        auto resort = [&](long long from) {
            double r2 = (double)hr * hr;
            vector<pair<long long, int>> in;
            vector<int> out;
            for (long long k = from; k < s; k++) {
                int e = mine[k];
                double er = (conns[e].first - 1) / 2.0, ec = (conns[e].second - 1) / 2.0;
                double best = 1e18;
                for (size_t q = 0; q + 1 < wps.size(); q++) {
                    double ai = wps[q] / m, aj = wps[q] % m;
                    double bi = wps[q + 1] / m, bj = wps[q + 1] % m;
                    double vi = bi - ai, vj = bj - aj;
                    double L2 = vi * vi + vj * vj;
                    double tt = L2 > 0 ? ((er - ai) * vi + (ec - aj) * vj) / L2 : 0;
                    tt = max(0.0, min(1.0, tt));
                    double pi_ = ai + tt * vi, pj = aj + tt * vj;
                    double d2 = (er - pi_) * (er - pi_) + (ec - pj) * (ec - pj);
                    best = min(best, d2);
                }
                if (best <= r2)
                    in.push_back({(long long)(best * 16), e});
                else
                    out.push_back(e);
            }
            stable_sort(in.begin(), in.end(),
                        [](const auto& A, const auto& B) { return A.first < B.first; });
            long long k = from;
            for (auto& [d, e] : in) mine[k++] = e;
            for (int e : out) mine[k++] = e;
        };
        auto pollHint = [&](long long i) -> bool {  // true = protocol continues
            wline("< 0");
            string snd, hbody;
            if (!(cin >> snd >> hbody)) return false;
            if (snd != "-" && hbody.size() >= 5) {
                int nw = hbody[0] - '0';
                if (nw >= 2 && nw <= 12 && (int)hbody.size() >= 2 + 3 * nw) {
                    vector<int> nwps(nw);
                    bool ok = true;
                    for (int q = 0; q < nw; q++) {
                        int c = (hbody[1 + 3 * q] - '0') | ((hbody[2 + 3 * q] - '0') << 6) |
                                ((hbody[3 + 3 * q] - '0') << 12);
                        if (c < 0 || c >= m * m) ok = false;
                        nwps[q] = c;
                    }
                    int r = (hbody[1 + 3 * nw] - '0') * 2 + 2;
                    if (ok && (nwps != wps || !focus)) {
                        wps = nwps;
                        hr = r;
                        focus = true;
                        resort(i);
                    }
                }
            }
            return true;
        };
        long long block = (s - 1) % SB + 1;  // remainder-first
        long long i = 0;
        while (i < s && !focus) {
            long long take = min(block, s - i);
            body.clear();
            int acc = 0, nb = 0;
            for (long long t = 0; t < take; t++, i++) {
                auto [r, c] = conns[mine[i]];
                printf("? %d %d\n", r, c);
                fflush(stdout);
                if (!(cin >> rep)) return 0;
                if (rep[0] == '1') acc |= 1 << nb;
                if (++nb == 6) {
                    body.push_back((char)('0' + acc));
                    acc = 0;
                    nb = 0;
                }
            }
            if (nb) body.push_back((char)('0' + acc));
            printf("> 0 %s\n", body.c_str());
            fflush(stdout);
            if (!(cin >> rep)) return 0;  // "OK"
            block = SB;
            if (endgame && !pollHint(i)) return 0;
        }
        // focus phase: explicit records, small blocks, poll after each send
        vector<int> outbox;
        const long long IB = 64;
        while (i < s || !outbox.empty()) {
            if ((long long)outbox.size() >= IB || (i >= s && !outbox.empty())) {
                body.clear();
                body.push_back('p');
                unsigned long long acc = 0;
                int nb = 0;
                long long take2 = min((long long)outbox.size(), (long long)85);
                for (long long k = 0; k < take2; k++) {
                    acc |= (unsigned long long)outbox[k] << nb;
                    nb += 18;
                    while (nb >= 6) {
                        body.push_back((char)('0' + (acc & 63)));
                        acc >>= 6;
                        nb -= 6;
                    }
                }
                if (nb > 0) body.push_back((char)('0' + (acc & 63)));
                outbox.erase(outbox.begin(), outbox.begin() + take2);
                printf("> 0 %s\n", body.c_str());
                fflush(stdout);
                if (!(cin >> rep)) return 0;  // "OK"
                if (!pollHint(i)) return 0;
            } else {
                auto [r, c] = conns[mine[i]];
                printf("? %d %d\n", r, c);
                fflush(stdout);
                if (!(cin >> rep)) return 0;
                outbox.push_back((int)(mine[i] * 2 + (rep[0] == '1')));
                i++;
            }
        }
        wline("halt");
        return 0;
    }

    // ---------------- master ----------------
    vector<signed char> know(W, -1);
    Dsu dsu;
    dsu.init(m * m);
    vector<unsigned char> openDR((size_t)m * m, 0);

    long long nKnown = 0;
    auto applyResult = [&](long long idx, int bit) {
        if (know[idx] != -1) return;
        nKnown++;
        know[idx] = (signed char)bit;
        if (bit) {
            int a, b;
            char d;
            edgeOf(idx, a, b, d);
            dsu.uni(a, b);
            openDR[a] |= (d == 'D') ? 1 : 2;
        }
    };

    vector<long long> done(K, 0);
    size_t ai = 0;
    long long ownPtr = 0;
    bool anomaly = false;
    long long scanPtr = 0;

    auto readMsg = [&]() -> bool {
        wline("< ?");
        string snd, body;
        if (!(cin >> snd >> body)) exit(0);
        if (snd == "-") return false;
        int w = atoi(snd.c_str());
        if (w < 1 || w >= K) return true;
        if (!body.empty() && body[0] == 'p') {  // explicit records (focus phase)
            long long nrec = ((long long)body.size() - 1) / 3;
            unsigned long long acc = 0;
            int nb = 0;
            size_t pos = 1;
            for (long long k = 0; k < nrec; k++) {
                while (nb < 18 && pos < body.size()) {
                    acc |= (unsigned long long)(body[pos++] - '0') << nb;
                    nb += 6;
                }
                unsigned int v = (unsigned int)(acc & ((1u << 18) - 1));
                acc >>= 18;
                nb -= 18;
                long long idx = v >> 1;
                if (idx < W) applyResult(idx, v & 1);
            }
            return true;
        }
        long long s = sch.shares[w - 1];
        long long first = (s - 1) % SB + 1;
        long long nbits = (done[w] == 0) ? first : SB;
        nbits = min(nbits, s - done[w]);
        for (long long i = 0; i < nbits && i / 6 < (long long)body.size(); i++) {
            int v = body[i / 6] - '0';
            applyResult(plist[w][done[w] + i], (v >> (i % 6)) & 1);
        }
        done[w] += nbits;
        return true;
    };

    // ---- gap-focus endgame state ----
    bool hintActive = false;
    vector<char> pendHint(K, 0);
    vector<long long> voidAfter(K, LLONG_MAX);  // positional arrivals after this are void
    int hcen = -1;
    vector<int> hwps;
    long long hrad = 0, hspan = LLONG_MAX, lastHintT = -(1 << 30);
    long long nextCorr = 64;
    priority_queue<long long, vector<long long>, greater<>> extraArr;  // focus arrivals
    vector<int> dgf, bfsPar, bfsQ, gsrc;
    string hintBody;
    // corridor BFS between the corner components through possibly-open edges
    auto corridor = [&]() -> long long {  // returns span; sets hcen/hrad candidate
        int gRoot = dsu.find(goal), sRoot = dsu.find(start);
        dgf.assign((size_t)m * m, INT_MAX);
        bfsPar.assign((size_t)m * m, -1);
        bfsQ.clear();
        for (int r_ = 0; r_ < m * m; r_++)
            if (dsu.find(r_) == gRoot) {
                dgf[r_] = 0;
                bfsQ.push_back(r_);
            }
        for (size_t h = 0; h < bfsQ.size(); h++) {
            int u = bfsQ[h];
            for (int dir = 0; dir < 4; dir++) {
                int i = u / m + DI[dir], j = u % m + DJ[dir];
                if (i < 0 || i >= m || j < 0 || j >= m) continue;
                int v = i * m + j;
                if (dgf[v] != INT_MAX) continue;
                long long idx = connIdxOf((u / m) * 2 + 1 + DI[dir], (u % m) * 2 + 1 + DJ[dir]);
                if (know[idx] == 0) continue;
                dgf[v] = dgf[u] + 1;
                bfsPar[v] = u;
                bfsQ.push_back(v);
            }
        }
        int a = -1;
        long long bd = LLONG_MAX;
        for (int r_ = 0; r_ < m * m; r_++)
            if (dsu.find(r_) == sRoot && dgf[r_] < bd) bd = dgf[r_], a = r_;
        if (a < 0 || bd <= 0 || bd >= INT_MAX) return LLONG_MAX;
        vector<int> path;
        for (int v = a; v != -1; v = bfsPar[v]) path.push_back(v);
        hcen = path[path.size() / 2];
        // polyline: up to 10 waypoints subsampled along the corridor
        int nw = (int)min((size_t)10, max((size_t)2, path.size() / 12 + 2));
        hwps.assign(nw, 0);
        for (int q = 0; q < nw; q++)
            hwps[q] = path[(size_t)((double)q / (nw - 1) * (path.size() - 1))];
        hrad = min(bd / 6 + 8, (long long)24);
        return bd;
    };
    // reorder a positions list suffix by distance to the hint polyline
    auto resortOwn = [&](vector<int>& lst, long long from) {
        double r2 = (double)hrad * hrad;
        vector<pair<long long, int>> in;
        vector<int> out;
        for (size_t k = from; k < lst.size(); k++) {
            int e = lst[k];
            double er = (conns[e].first - 1) / 2.0, ec = (conns[e].second - 1) / 2.0;
            double best = 1e18;
            for (size_t q = 0; q + 1 < hwps.size(); q++) {
                double ai = hwps[q] / m, aj = hwps[q] % m;
                double bi = hwps[q + 1] / m, bj = hwps[q + 1] % m;
                double vi = bi - ai, vj = bj - aj;
                double L2 = vi * vi + vj * vj;
                double tt = L2 > 0 ? ((er - ai) * vi + (ec - aj) * vj) / L2 : 0;
                tt = max(0.0, min(1.0, tt));
                double pi_ = ai + tt * vi, pj = aj + tt * vj;
                double d2 = (er - pi_) * (er - pi_) + (ec - pj) * (ec - pj);
                best = min(best, d2);
            }
            if (best <= r2)
                in.push_back({(long long)(best * 16), e});
            else
                out.push_back(e);
        }
        stable_sort(in.begin(), in.end(),
                    [](const auto& A, const auto& B) { return A.first < B.first; });
        size_t k = from;
        for (auto& [d, e] : in) lst[k++] = e;
        for (int e : out) lst[k++] = e;
    };

    string rep;
    for (long long t = 1;; t++) {
        if (dsu.find(start) == dsu.find(goal)) {
            string path = buildPath(openDR);
            if (path != "*") {
                printf("! %s\n", path.c_str());
                fflush(stdout);
                return 0;
            }
        }

        // endgame trigger / re-trigger (only once the corridor is reliable:
        // short span and enough of the sweep already known)
        if (endgame && !anomaly && t >= nextCorr && nKnown * 5 >= W * 2) {
            nextCorr = t + 64;
            int oldc = hcen;
            long long span = corridor();
            long long moved2 = 0;
            if (oldc >= 0 && hcen >= 0) {
                long long di = hcen / m - oldc / m, dj = hcen % m - oldc % m;
                moved2 = di * di + dj * dj;
            }
            bool renew = !hintActive || (t - lastHintT >= 128 &&
                                         (span * 2 < hspan || moved2 > (hrad / 2) * (hrad / 2)));
            // desperation ladder: on high-f* mazes the sweep is failing and
            // aggressive focus is worth the risk
            long long spanT = (nKnown * 20 >= W * 13)   ? (long long)(m - 1)
                              : (nKnown * 20 >= W * 11) ? (long long)(m - 1) / 2
                                                        : (long long)(m - 1) / 3;
            if (span < spanT && renew) {
                if (getenv("D_DEBUG"))
                    fprintf(stderr, "[hint] t=%lld span=%lld cen=(%d,%d) rad=%lld\n", t, span,
                            hcen / m, hcen % m, hrad);
                hspan = span;
                lastHintT = t;
                hintActive = true;
                hintBody.clear();
                hintBody.push_back((char)('0' + (int)hwps.size()));
                for (int wp : hwps) {
                    hintBody.push_back((char)('0' + (wp & 63)));
                    hintBody.push_back((char)('0' + ((wp >> 6) & 63)));
                    hintBody.push_back((char)('0' + ((wp >> 12) & 63)));
                }
                hintBody.push_back((char)('0' + (int)min(63LL, hrad / 2)));
                for (int w = 1; w < K; w++)
                    if (sch.shares[w - 1] > 0 && done[w] + 64 < sch.shares[w - 1])
                        pendHint[w] = 1;
                if (ownPtr < sch.masterShare) resortOwn(plist[0], ownPtr);
            }
        }

        bool pendingMsgs = false;
        for (int w = 1; w < K && !pendingMsgs; w++)
            if (done[w] < sch.shares[w - 1] && voidAfter[w] == LLONG_MAX) pendingMsgs = true;

        if (!anomaly) {
            // void positional arrivals from workers that have switched to focus
            while (ai < sch.arrivals.size() &&
                   sch.arrivals[ai].first > voidAfter[sch.arrivals[ai].second])
                ai++;
            if (ai < sch.arrivals.size() && sch.arrivals[ai].first <= t) {
                if (readMsg())
                    ai++;
                else if (!hintActive)
                    anomaly = true;  // schedule broken (worker died?)
                else
                    ai++;  // tolerate: focus-phase timing drift
            } else if (hintActive && [&] {
                           for (int w = 1; w < K; w++)
                               if (pendHint[w]) return true;
                           return false;
                       }()) {
                int w = 1;
                while (!pendHint[w]) w++;
                printf("> %d %s\n", w, hintBody.c_str());
                fflush(stdout);
                if (!(cin >> rep)) return 0;  // "OK"
                pendHint[w] = 0;
                // worker switches at its first poll >= t+1 (readable then);
                // void its later positional arrivals; schedule its focus-phase
                // sends (deterministic 64q+send+poll cycles from that poll)
                if (voidAfter[w] == LLONG_MAX) {
                    vector<long long> sends, polls;
                    sendRounds(sch.shares[w - 1], sends, &polls);
                    long long sw = LLONG_MAX, doneQ = 0;
                    {
                        long long s2 = sch.shares[w - 1];
                        long long b0 = (s2 - 1) % SB + 1;
                        for (size_t pi = 0; pi < polls.size(); pi++) {
                            if (polls[pi] >= t + 1) {
                                sw = polls[pi];
                                doneQ = min(s2, b0 + (long long)pi * SB);
                                break;
                            }
                        }
                    }
                    voidAfter[w] = sw;
                    if (sw != LLONG_MAX) {
                        long long rem2 = sch.shares[w - 1] - doneQ, t2 = sw;
                        while (rem2 > 0) {
                            long long q = min(64LL, rem2);
                            rem2 -= q;
                            t2 += q + 1;
                            extraArr.push(t2 + 1);
                            t2 += 1;  // worker's re-hint poll
                        }
                    }
                }
            } else if (hintActive && !extraArr.empty() && extraArr.top() <= t) {
                extraArr.pop();
                readMsg();  // tolerate '- -' (worker death / drift)
            } else if (ownPtr < sch.masterShare) {
                auto [r, c] = conns[plist[0][ownPtr]];
                printf("? %d %d\n", r, c);
                fflush(stdout);
                if (!(cin >> rep)) return 0;
                applyResult(plist[0][ownPtr], rep[0] == '1');
                ownPtr++;
            } else if (hintActive) {
                // exhausted own share: self-scan unknowns
                while (scanPtr < W && know[scanPtr] != -1) scanPtr++;
                if (scanPtr < W) {
                    auto [r, c] = conns[scanPtr];
                    printf("? %d %d\n", r, c);
                    fflush(stdout);
                    if (!(cin >> rep)) return 0;
                    applyResult(scanPtr, rep[0] == '1');
                } else {
                    wline(".");
                    if (!(cin >> rep)) return 0;
                }
            } else if (pendingMsgs && ai >= sch.arrivals.size()) {
                anomaly = true;
                if (!readMsg()) { /* keep draining via fallback */ }
            } else {
                wline(".");
                if (!(cin >> rep)) return 0;
            }
        } else {
            // fallback: alternate draining survivors with self-querying unknowns
            if (pendingMsgs && (t & 1)) {
                readMsg();
            } else {
                while (scanPtr < W && know[scanPtr] != -1) scanPtr++;
                if (scanPtr < W) {
                    auto [r, c] = conns[scanPtr];
                    printf("? %d %d\n", r, c);
                    fflush(stdout);
                    if (!(cin >> rep)) return 0;
                    applyResult(scanPtr, rep[0] == '1');
                } else if (pendingMsgs) {
                    readMsg();
                } else {
                    wline(".");
                    if (!(cin >> rep)) return 0;
                }
            }
        }
    }
    return 0;
}

}  // namespace blind

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    if (!(cin >> N >> K >> ID >> ML)) return 0;

    m = (N + 1) / 2;
    if (m == 1) {  // N == 1: start == goal
        if (ID == 0)
            wline("! ");
        else
            wline("halt");
        return 0;
    }

    conns.reserve((size_t)2 * m * (m - 1));
    rowStart.assign(N + 2, 0);
    for (int r = 1; r <= N; r++) {
        rowStart[r] = (long long)conns.size();
        for (int c = (r % 2) + 1; c <= N; c += 2)  // r+c odd
            conns.push_back({r, c});
    }
    W = (long long)conns.size();

    // bidir/blind crossover measured offline (avg turns, 5-8 seeds); with
    // wall-aware worker re-key, bidir wins to K~16 at N=501 (K=12: -26%) but
    // N~401 has fat-tail mazes -> conservative:
#if defined(FORCE_BIDIR)
    return bidir::run();
#elif defined(FORCE_BLIND)
    return blind::run();
#else
    int bidirK = (N <= 110)   ? 6
                 : (N <= 350) ? 10
                 : (N <= 470) ? 12
                 : (N <= 490) ? 14
                              : 16;
    if (K <= bidirK) return bidir::run();
    return blind::run();
#endif
}