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

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

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 && (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];
            char msg[4] = {(char)('0' + (T & 63)), (char)('0' + ((T >> 6) & 63)),
                           (char)('0' + ((T >> 12) & 63)), 0};
            printf("> %d %s\n", sw, msg);
            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;

// rounds used by a worker with share s: s queries + ceil(s/SB) sends
long long roundsFor(long long s) { return s == 0 ? 0 : s + (s + SB - 1) / SB; }
// max share s with roundsFor(s) <= F
long long capFor(long long F) {
    if (F < 2) return 0;
    long long k = (F + SB) / (SB + 1);
    long long s = F - k;
    if (s < 0) s = 0;
    while (s > 0 && roundsFor(s) > F) s--;
    return s;
}
// send rounds for share s, remainder-first packing
void sendRounds(long long s, vector<long long>& out) {
    out.clear();
    if (s == 0) return;
    long long t = 0, rem = s, block = (s - 1) % SB + 1;
    while (rem > 0) {
        t += block;
        rem -= block;
        t += 1;
        out.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;
    SB = max(64LL, min(B, W / max(K - 1, 1) / 12 + 1));
    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;
        }
        const vector<int>& mine = plist[ID];
        string body, rep;
        long long block = (s - 1) % SB + 1;  // remainder-first
        long long i = 0;
        while (i < s) {
            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;
        }
        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);

    auto applyResult = [&](long long idx, int bit) {
        if (know[idx] != -1) return;
        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;
        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;
    };

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

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

        if (!anomaly) {
            if (ai < sch.arrivals.size() && sch.arrivals[ai].first <= t) {
                if (readMsg())
                    ai++;
                else
                    anomaly = true;  // schedule broken (worker died?)
            } 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 (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 <= 200) ? 10 : (N <= 350) ? 9 : (N <= 450) ? 10 : 14;
    if (K <= bidirK) return bidir::run();
    return blind::run();
#endif
}