// v12: v10 + the frontier dispatcher probes on idle turns, aimed at the
// gap. Instead of hammering `< ?` between fact batches, agent 0 spends 3
// of every 4 dry turns probing edges in expanding L1 rings around the
// midpoint of the closest gap between the start-side and goal-side
// components (recomputed from its DSU every 64 turns via two grid BFS).
// The known blob it builds is a stepping stone: the fronts only need to
// reach it, not each other. (v11 scanned a static center disk — big wins
// when the meeting zone was central, a no-op otherwise; tracking the gap
// converts the rest.) Cycle rule skips edges already deducible as walls,
// and worker facts mark edges known so they are never re-probed.
//
// v10: regime switch by agent count; frontier workers scan when idle.
//
//   A == 1      : solo goal-directed DFS walker.
//   A == 2      : two independent walkers from both corners.
//   3 <= A <= 8 : v7 bidirectional frontier search — angular-sector
//                 ownership, greedy expansion, peer-to-peer handoffs,
//                 dispatcher claims on connectivity (the two sides only
//                 need to MEET, not to finish). Beats independent walkers
//                 2-4x at A=3-4 and the scan up to 1.7x at A=5-8.
//   9 <= A <= 11: frontier when the maze is large (m >= 100) — with 4-5
//                 workers per side the wedge/peer overhead still pays off;
//                 idle wedges scan their own territory radially so nobody
//                 polls uselessly. Scan otherwise.
//   A >= 12     : v4 full scan with spanning-tree deduction — the wide
//                 scan frontier keeps many agents busy; measured best at
//                 high agent counts.
//
// See v4.cpp and v7.cpp for the two engines' details.
#include <bits/stdc++.h>
using namespace std;
#ifndef EAGER_FRAC
#define EAGER_FRAC 0.68
#endif
#ifndef EAGER_BITS_C
#define EAGER_BITS_C 48
#endif
#ifndef EAGER_EVERY
#define EAGER_EVERY 1
#endif

static long long N, A, ID, MAXLEN;
static int m;

static const int di[4] = {1, 0, -1, 0}; // D R U L
static const int dj[4] = {0, 1, 0, -1};
static const char dch[4] = {'D', 'R', 'U', 'L'};

static string rdline() {
    string s;
    if (!getline(cin, s)) exit(0);
    return s;
}
static void wr(const string &s) { cout << s << "\n" << flush; }

static long long numEdges() { return 2LL * m * (m - 1); }
struct EdgeRef { int pr, pc, ra, rb, dir; };
static EdgeRef edgeInfo(long long e) {
    long long block = e / (2 * m - 1), off = e % (2 * m - 1);
    int i = (int)block, j;
    if (off < m - 1) {
        j = (int)off;
        return {2 * i + 1, 2 * j + 2, i * m + j, i * m + j + 1, 1};
    }
    j = (int)(off - (m - 1));
    return {2 * i + 2, 2 * j + 1, i * m + j, (i + 1) * m + j, 0};
}
static long long edgeIdOf(int room, int d) {
    int r = room / m, c = room % m;
    if (d == 2) r--;
    if (d == 3) c--;
    if (d == 1 || d == 3) return (long long)r * (2 * m - 1) + c;
    return (long long)r * (2 * m - 1) + (m - 1) + c;
}
static void pack18(string &s, uint32_t v) {
    for (int k = 12; k >= 0; k -= 6) s.push_back((char)('0' + ((v >> k) & 63)));
}
static void pack30(string &s, uint32_t v) {
    for (int k = 24; k >= 0; k -= 6) s.push_back((char)('0' + ((v >> k) & 63)));
}
static uint32_t unpack30(const string &s, size_t pos) {
    uint32_t v = 0;
    for (int t = 0; t < 5; t++) v = (v << 6) | (uint32_t)(s[pos + t] - '0');
    return v;
}
static uint32_t unpack18(const string &s, size_t pos) {
    uint32_t v = 0;
    for (int t = 0; t < 3; t++) v = (v << 6) | (uint32_t)(s[pos + t] - '0');
    return v;
}

// Diagonal-first scan order: the unique path is diagonally biased (measured
// mean |r-c| ~ 0.17N) and row-major order needs ~100% of edges scanned
// before the whole path is covered, while |r-c| order needs only ~69%.
// Both scanners and the dispatcher index bands through this permutation.
static vector<int> scanPerm;
static void buildScanPerm() {
    long long E = numEdges();
    vector<pair<int, int>> tmp;
    tmp.reserve((size_t)E);
    for (long long e = 0; e < E; e++) {
        EdgeRef x = edgeInfo(e);
        int key = abs((x.ra / m + x.rb / m) - (x.ra % m + x.rb % m));
        tmp.push_back({key, (int)e});
    }
    sort(tmp.begin(), tmp.end());
    scanPerm.reserve(tmp.size());
    for (auto &pr : tmp) scanPerm.push_back(pr.second);
}

// ---- role/band layout (identical on every agent) ----
// Scanners weigh 2 units each; the dispatcher takes 1 unit (at the END of
// the edge list) when scanners are few, else 0.
static long long scanS() { return A - 1; }
static int dispW() { return scanS() <= 8 ? 1 : 0; }
static long long units() { return 2 * scanS() + dispW(); }
// interleaved over the diagonal-first perm: scanner q's i-th edge sits at
// global position (i/2)*U + 2q + (i%2), so all scanners advance through
// the shared priority order in lockstep and the claim fires at the path's
// worst perm position (~69% of E) instead of the worst band position.
static long long scanPos(long long q, long long i) {
    return (i >> 1) * units() + 2 * q + (i & 1);
}
static long long dispPos(long long j) { return j * units() + 2 * scanS(); }

// ---- shared knowledge state + deduction rules ----
struct Know {
    vector<int> dsu;
    vector<uint8_t> knownMask, openMask; // per room, bit d = edge in dir d
    Know() : dsu(m * m), knownMask((size_t)m * m, 0), openMask((size_t)m * m, 0) {
        iota(dsu.begin(), dsu.end(), 0);
    }
    int find(int x) { while (dsu[x] != x) x = dsu[x] = dsu[dsu[x]]; return x; }
    int incident(int room) {
        int r = room / m, c = room % m, k = 0;
        for (int d = 0; d < 4; d++) {
            int nr = r + di[d], nc = c + dj[d];
            if (nr >= 0 && nc >= 0 && nr < m && nc < m) k++;
        }
        return k;
    }
    void set(int ra, int rb, int dir, bool open) { // dir: ra->rb
        knownMask[ra] |= 1 << dir;
        knownMask[rb] |= 1 << (dir ^ 2);
        if (open) {
            openMask[ra] |= 1 << dir;
            openMask[rb] |= 1 << (dir ^ 2);
            dsu[find(ra)] = find(rb);
        }
    }
    // -1 unknown, else 0/1
    int deduce(int ra, int rb, int dir) {
        if (find(ra) == find(rb)) return 0;               // cycle rule
        for (int x : {ra, rb}) {                          // degree rule
            if (openMask[x]) continue;
            if (__builtin_popcount(knownMask[x]) == incident(x) - 1) return 1;
        }
        return -1;
    }
};

// ---------------- walker (v3) for A<=4 / solo fallback ----------------
static void walker(bool fromStart, int bias) {
    int rootR = fromStart ? 0 : m - 1, rootC = rootR;
    int tgtR = fromStart ? m - 1 : 0, tgtC = tgtR;
    const int root = rootR * m + rootC, tgt = tgtR * m + tgtC;
    vector<uint8_t> vis((size_t)m * m, 0);
    vector<int> par((size_t)m * m, -1);
    vector<uint8_t> pmv((size_t)m * m, 0);
    struct Fr { int room; uint8_t ord[4]; int k; };
    vector<Fr> st;
    auto mkFr = [&](int room) {
        Fr f; f.room = room; f.k = 0;
        int r = room / m, c = room % m;
        int sc[4] = {tgtR - r, tgtC - c, r - tgtR, c - tgtC};
        int idx[4] = {0, 1, 2, 3};
        stable_sort(idx, idx + 4, [&](int a, int b) {
            if (sc[a] != sc[b]) return sc[a] > sc[b];
            return bias ? a > b : a < b;
        });
        for (int t = 0; t < 4; t++) f.ord[t] = (uint8_t)idx[t];
        return f;
    };
    vis[root] = 1;
    st.push_back(mkFr(root));
    while (!st.empty()) {
        Fr &f = st.back();
        if (f.k == 4) { st.pop_back(); continue; }
        int d = f.ord[f.k++];
        int i = f.room / m, j = f.room % m;
        int ni = i + di[d], nj = j + dj[d];
        if (ni < 0 || nj < 0 || ni >= m || nj >= m) continue;
        int nxt = ni * m + nj;
        if (vis[nxt]) continue;
        wr("? " + to_string(2 * i + 1 + di[d]) + " " + to_string(2 * j + 1 + dj[d]));
        if (rdline()[0] != '1') continue;
        vis[nxt] = 1;
        par[nxt] = f.room;
        pmv[nxt] = (uint8_t)d;
        if (nxt == tgt) {
            vector<uint8_t> seq;
            for (int v = tgt; v != root; v = par[v]) seq.push_back(pmv[v]);
            reverse(seq.begin(), seq.end());
            string path;
            if (fromStart) {
                for (uint8_t mv : seq) { path += dch[mv]; path += dch[mv]; }
            } else {
                for (int t = (int)seq.size() - 1; t >= 0; t--) {
                    char c = dch[seq[t] ^ 2];
                    path += c; path += c;
                }
            }
            wr("! " + path);
            exit(0);
        }
        st.push_back(mkFr(nxt));
    }
    wr("halt");
    exit(1);
}
static void soloSolve() { walker(true, 0); }

// ---------------- scanner ----------------
static void scanner(long long q) {
    const long long E = numEdges();
    Know K;
    // batch size balances scanner send overhead, dispatcher read rate
    // (1 msg/turn!) and last-batch staleness; on small mazes 120 bits is
    // most of a band and the dispatcher sits blind. ~sqrt(0.7E) is the
    // read-bound optimum.
    long long batchBits = min({120LL, (MAXLEN - 24) * 6,
                               max(24LL, (long long)sqrt(0.7 * (double)numEdges()))});
    batchBits = batchBits / 6 * 6; // whole chars only: a partial final char
                                   // decodes its zero padding as wall bits
    if (batchBits < 6) batchBits = 6;
    const long long eagerAt = (long long)(EAGER_FRAC * (double)E);
    const bool eagerMe = ((q % EAGER_EVERY) == 0) && (A >= 16); // GATE: eager-flush helps read-bound high-A but wastes throughput at A9-15
    long long eagerBits = min(batchBits, (long long)EAGER_BITS_C);
    deque<uint8_t> pending; // unsent bits, in band order
    long long sent = 0;     // bits already sent (= band-sequence index of pending[0])
    auto flush = [&](long long nbits) { // send nbits pending bits; costs the turn
        string enc;
        for (long long t = 0; t < nbits; t += 6) {
            int v = 0;
            for (int b = 0; b < 6; b++)
                v = (v << 1) | (t + b < nbits ? pending[t + b] : 0);
            enc.push_back((char)('0' + v));
        }
        wr("> 0 S " + to_string(sent) + " " + enc);
        rdline(); // OK
        pending.erase(pending.begin(), pending.begin() + nbits);
        sent += nbits;
    };
    long long i = 0;
    while (scanPos(q, i) < E || !pending.empty()) {
        // deduce everything currently free (costs no turns)
        while (scanPos(q, i) < E) {
            EdgeRef x = edgeInfo(scanPerm[scanPos(q, i)]);
            int v = K.deduce(x.ra, x.rb, x.dir);
            if (v < 0) break;
            K.set(x.ra, x.rb, x.dir, v);
            pending.push_back((uint8_t)v);
            i++;
        }
        long long curBatch = (eagerMe && scanPos(q, i) >= eagerAt) ? eagerBits : batchBits;
        if ((long long)pending.size() >= curBatch) { flush(curBatch); continue; }
        if (scanPos(q, i) >= E) {
            if (!pending.empty()) flush((long long)pending.size());
            break;
        }
        EdgeRef x = edgeInfo(scanPerm[scanPos(q, i)]);
        wr("? " + to_string(x.pr) + " " + to_string(x.pc));
        int bit = rdline()[0] == '1' ? 1 : 0;
        K.set(x.ra, x.rb, x.dir, bit);
        pending.push_back((uint8_t)bit);
        i++;
    }
    wr("halt");
    exit(0);
}

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

// ---------------- frontier worker ----------------
static void frontierWorker() {
    const bool startSide = (ID % 2 == 1);
    const int W = (int)((A - 1 + (startSide ? 1 : 0)) / 2); // workers on my side
    const int myIdx = (int)((ID - 1) / 2);
    const int cr = startSide ? 0 : m - 1, cc = cr;         // my corner
    const int tgtR = startSide ? m - 1 : 0, tgtC = tgtR;   // opposite corner
    const int FACT_CH = 216, FACT_T = 96, PEER_CH = 210, PEER_T = 6, POLL_T = 48;

    auto sectorOf = [&](int room) -> int {
        int ri = abs(room / m - cr), rj = abs(room % m - cc);
        if (ri + rj == 0) return 0;
        int s = (int)((long long)ri * W / (ri + rj));
        return min(s, W - 1);
    };
    auto ownerOf = [&](int room) { return 1 + 2 * sectorOf(room) + (startSide ? 0 : 1); };

    vector<uint8_t> knownMask((size_t)m * m, 0), openLocal((size_t)m * m, 0),
        seen((size_t)m * m, 0);
    Dsu dsu(m * m);
    auto tryClaim = [&]() { // workers claim too: relay gives them both sides
        if (dsu.find(0) != dsu.find(m * m - 1)) return;
        vector<int> par((size_t)m * m, -1);
        vector<uint8_t> pmv((size_t)m * m, 0), sn((size_t)m * m, 0);
        deque<int> bq{0};
        sn[0] = 1;
        while (!bq.empty()) {
            int cur = bq.front(); bq.pop_front();
            if (cur == m * m - 1) break;
            int r = cur / m, c = cur % m;
            for (int d = 0; d < 4; d++) {
                if (!(openLocal[cur] & (1 << d))) continue;
                int nxt = (r + di[d]) * m + (c + dj[d]);
                if (sn[nxt]) continue;
                sn[nxt] = 1;
                par[nxt] = cur;
                pmv[nxt] = (uint8_t)d;
                bq.push_back(nxt);
            }
        }
        if (!sn[m * m - 1]) return;
        string path;
        vector<uint8_t> sq;
        for (int v = m * m - 1; v != 0; v = par[v]) sq.push_back(pmv[v]);
        for (int t = (int)sq.size() - 1; t >= 0; t--) {
            path += dch[sq[t]]; path += dch[sq[t]];
        }
        wr("! " + path);
        exit(0);
    };
    auto dist = [&](int room) {
        int r = room / m, c = room % m;
        int base = abs(r - tgtR) + abs(c - tgtC);
        int pol = (A == 8) ? 0 : (int)(((A == 3 || A == 7) ? ID : myIdx) & 3);
        if (pol == 1) return 8 * base + abs(r - c);
        if (pol == 2) return 8 * base + abs((r + c) - (m - 1));
        if (pol == 3) {
            uint32_t h = (uint32_t)(room * 1103515245u + ID * 1000003u);
            h ^= h >> 16;
            return 4 * base + (int)(h & 7);
        }
        return 8 * base;
    };
    auto initMask = [&](int room, int entryDir) -> uint8_t {
        int r = room / m, c = room % m;
        uint8_t mk = 0;
        for (int d = 0; d < 4; d++) {
            if (d == entryDir) continue;
            if (knownMask[room] & (1 << d)) continue;
            int nr = r + di[d], nc = c + dj[d];
            if (nr < 0 || nc < 0 || nr >= m || nc >= m) continue;
            mk |= 1 << d;
        }
        return mk;
    };

    // my wedge's edges in radial order from my corner: the idle-time scan
    // list. Pre-warming the wedge where the frontier will arrive keeps every
    // worker busy and feeds connectivity directly.
    vector<int> scanList;
    {
        vector<pair<int, int>> tmp; // (radial dist, edge id)
        for (long long e = 0; e < numEdges(); e++) {
            EdgeRef x = edgeInfo(e);
            if (sectorOf(x.ra) != myIdx) continue;
            int rad = abs(x.ra / m - cr) + abs(x.ra % m - cc);
            tmp.push_back({rad, (int)e});
        }
        sort(tmp.begin(), tmp.end());
        scanList.reserve(tmp.size());
        for (auto &pr : tmp) scanList.push_back(pr.second);
    }
    size_t scanPos = 0;

    typedef tuple<int, int, int, uint8_t> QI; // (pri, room, depth, mask)
    priority_queue<QI, vector<QI>, greater<QI>> q;
    string factBuf;
    map<int, pair<string, long long>> peerBuf; // owner -> (buf, firstTurn)
    long long turn = 0, factAge = 0, lastPoll = 0;

    auto shipFact = [&](int room, int d, bool open) {
        if (factBuf.empty()) factAge = turn;
        pack18(factBuf, ((uint32_t)edgeIdOf(room, d) << 1) | (open ? 1 : 0));
    };
    auto markEdge = [&](int room, int d, bool open) {
        int nb = (room / m + di[d]) * m + (room % m + dj[d]);
        knownMask[room] |= 1 << d;
        knownMask[nb] |= 1 << (d ^ 2);
        if (open) {
            openLocal[room] |= 1 << d;
            openLocal[nb] |= 1 << (d ^ 2);
            dsu.unite(room, nb);
        }
        shipFact(room, d, open); // walls too: the dispatcher explores with
                                 // the union knowledge and must not re-probe
    };
    auto markOpenQuiet = [&](int room, int d) { // known-open, already shipped
        int nb = (room / m + di[d]) * m + (room % m + dj[d]);
        knownMask[room] |= 1 << d;
        knownMask[nb] |= 1 << (d ^ 2);
        openLocal[room] |= 1 << d;
        openLocal[nb] |= 1 << (d ^ 2);
        dsu.unite(room, nb);
    };

    // enqueue with cascade: known-open edges (from idle scanning) propagate
    // the wave for free — locally by recursion, across wedges by peer token
    vector<tuple<int, int, int>> cascade; // (room, entryDir, depth)
    auto enqueue = [&](int room0, int entry0, int depth0) {
        cascade.push_back({room0, entry0, depth0});
        while (!cascade.empty()) {
            auto [room, entry, depth] = cascade.back();
            cascade.pop_back();
            if (seen[room]) continue;
            seen[room] = 1;
            uint8_t mk = initMask(room, entry);
            if (mk) q.push({dist(room) - (A == 5 ? depth : (A == 6 ? 3 * depth : 0)), room, depth, mk});
            for (int d = 0; d < 4; d++) {
                if (d == entry) continue;
                if (!(openLocal[room] & (1 << d))) continue;
                int nb = (room / m + di[d]) * m + (room % m + dj[d]);
                if (seen[nb]) continue;
                int nd = min(depth + 1, 511);
                if (ownerOf(nb) == (int)ID) {
                    cascade.push_back({nb, d ^ 2, nd});
                } else {
                    auto &pb = peerBuf[ownerOf(nb)];
                    if (pb.first.empty()) pb.second = turn;
                    pack30(pb.first, ((uint32_t)nb << 11) | ((uint32_t)(d ^ 2) << 9) |
                                         (uint32_t)nd);
                }
            }
        }
    };
    if (myIdx == 0) enqueue(cr * m + cc, -1, 0);

    for (;; turn++) {
        // one send per turn max: peers first (latency-critical), then facts
        int sendTo = -1;
        for (auto &kv : peerBuf)
            if ((long long)kv.second.first.size() >= PEER_CH ||
                turn - kv.second.second >= PEER_T) {
                sendTo = kv.first;
                break;
            }
        if (sendTo >= 0) {
            wr("> " + to_string(sendTo) + " P " + peerBuf[sendTo].first);
            rdline(); // OK
            peerBuf.erase(sendTo);
            continue;
        }
        if (!factBuf.empty() &&
            ((long long)factBuf.size() >= FACT_CH || turn - factAge >= FACT_T)) {
            wr("> 0 F " + factBuf);
            rdline();
            factBuf.clear();
            continue;
        }
        bool mustPoll = turn - lastPoll >= POLL_T;
        if (q.empty() || mustPoll) {
            if (q.empty() && !mustPoll && turn - lastPoll < 4) {
                // idle: scan my wedge radially instead of hammering the inbox
                while (scanPos < scanList.size()) {
                    EdgeRef x = edgeInfo(scanList[scanPos]);
                    if (knownMask[x.ra] & (1 << x.dir)) { scanPos++; continue; }
                    break;
                }
                if (scanPos < scanList.size()) {
                    EdgeRef x = edgeInfo(scanList[scanPos++]);
                    wr("? " + to_string(x.pr) + " " + to_string(x.pc));
                    bool open = rdline()[0] == '1';
                    markEdge(x.ra, x.dir, open);
                    continue;
                }
            }
            lastPoll = turn;
            wr("< ?");
            string line = rdline();
            if (line == "- -") continue;
            lastPoll = turn - POLL_T + 1; // burst: poll again next turn
            size_t sp = line.find(' ');
            string body = line.substr(sp + 1);
            if (body[0] == 'P') {
                for (size_t pos = 2; pos + 5 <= body.size(); pos += 5) {
                    uint32_t v = unpack30(body, pos);
                    int room = (int)(v >> 11), ent = (int)((v >> 9) & 3);
                    markOpenQuiet(room, ent); // handoff edge is known open
                    enqueue(room, ent, (int)(v & 511));
                }
                tryClaim();
            } else if (body[0] == 'R') {
                for (size_t pos = 2; pos + 3 <= body.size(); pos += 3) {
                    uint32_t v = unpack18(body, pos);
                    long long e = (long long)(v >> 1);
                    if (e >= numEdges()) continue;
                    EdgeRef x = edgeInfo(e);
                    knownMask[x.ra] |= 1 << x.dir;
                    knownMask[x.rb] |= 1 << (x.dir ^ 2);
                    if (v & 1) {
                        openLocal[x.ra] |= 1 << x.dir;
                        openLocal[x.rb] |= 1 << (x.dir ^ 2);
                        dsu.unite(x.ra, x.rb);
                    }
                }
                tryClaim();
            }
            continue;
        }
        auto [p, room, depth, mask] = q.top();
        q.pop();
        // probe the most target-ward pending direction of this room
        int best = -1, bestD = INT_MAX;
        for (int d = 0; d < 4; d++) {
            if (!(mask & (1 << d))) continue;
            int nb = (room / m + di[d]) * m + (room % m + dj[d]);
            if (dist(nb) < bestD) { bestD = dist(nb); best = d; }
        }
        int d = best;
        mask &= ~(1 << d);
        if (knownMask[room] & (1 << d)) { // learned meanwhile (scan or peer)
            if (mask) q.push({p, room, depth, mask});
            if (openLocal[room] & (1 << d)) { // propagate through known-open
                int nb = (room / m + di[d]) * m + (room % m + dj[d]);
                int nd = min(depth + 1, 511);
                if (ownerOf(nb) == (int)ID) enqueue(nb, d ^ 2, nd);
                else if (!seen[nb]) {
                    auto &pb = peerBuf[ownerOf(nb)];
                    if (pb.first.empty()) pb.second = turn;
                    pack30(pb.first, ((uint32_t)nb << 11) | ((uint32_t)(d ^ 2) << 9) |
                                         (uint32_t)nd);
                }
            }
            turn--;
            continue;
        }
        if (mask) q.push({p, room, depth, mask});
        int r = room / m, c = room % m;
        wr("? " + to_string(2 * r + 1 + di[d]) + " " + to_string(2 * c + 1 + dj[d]));
        bool open = rdline()[0] == '1';
        markEdge(room, d, open);
        if (!open) continue;
        tryClaim();
        int nb = (r + di[d]) * m + (c + dj[d]);
        int owner = ownerOf(nb);
        int ndep = min(depth + 1, 511);
        if (owner == (int)ID) {
            enqueue(nb, d ^ 2, ndep);
        } else {
            auto &pb = peerBuf[owner];
            if (pb.first.empty()) pb.second = turn;
            pack30(pb.first, ((uint32_t)nb << 11) | ((uint32_t)(d ^ 2) << 9) |
                                 (uint32_t)ndep);
        }
    }
}

// ---------------- dispatcher ----------------
static void frontDispatcher() {
    const long long E = numEdges();
    Dsu dsu(m * m);
    vector<uint8_t> openMask((size_t)m * m, 0), knownMask((size_t)m * m, 0);
    const int start = 0, goal = m * m - 1;
    long long misses = 0;
    int dryProbes = 0; // probes left before the next inbox poll

    // cross-side relay: forward each side's facts (walls AND opens) to the
    // opposite side's workers, plus our own probe results to everyone.
    // Workers dedup against them and cascade through the other side's tree.
    vector<string> relayBuf((size_t)A);
    vector<long long> relayAge((size_t)A, 0);
    const long long RELAY_CH = min(252LL, (MAXLEN - 4) / 3 * 3);
    auto relayTo = [&](int w, uint32_t v, long long now) {
        if (relayBuf[w].empty()) relayAge[w] = now;
        pack18(relayBuf[w], v);
    };

    // Adaptive scan target: probe edges in expanding L1 rings around the
    // midpoint of the gap between the start-side and goal-side components.
    // The known blob is a stepping stone the two fronts only need to reach.
    int tr = m / 2, tc = m / 2, rad = 0;
    bool exhausted = false;
    vector<long long> cand;
    size_t candPos = 0;
    long long turn = 0, lastCalc = -1000;
    bool dirty = true;

    auto refill = [&]() { // next ring of unknown edges around (tr,tc)
        cand.clear();
        candPos = 0;
        auto pushRoom = [&](int r, int c) {
            if (r < 0 || c < 0 || r >= m || c >= m) return;
            int room = r * m + c;
            for (int d = 0; d < 2; d++) { // D and R: each edge once
                int nr = r + di[d], nc = c + dj[d];
                if (nr >= m || nc >= m) continue;
                if (knownMask[room] & (1 << d)) continue;
                if (dsu.find(room) == dsu.find(nr * m + nc)) { // cycle rule
                    knownMask[room] |= 1 << d;
                    knownMask[nr * m + nc] |= 1 << (d ^ 2);
                    continue;
                }
                cand.push_back(edgeIdOf(room, d));
            }
        };
        while (cand.empty()) {
            if (rad > 2 * (m - 1)) { exhausted = true; return; }
            if (rad == 0) pushRoom(tr, tc);
            else
                for (int k = 0; k < rad; k++) {
                    pushRoom(tr - rad + k, tc + k);
                    pushRoom(tr + k, tc + rad - k);
                    pushRoom(tr + rad - k, tc - k);
                    pushRoom(tr - k, tc - rad + k);
                }
            rad++;
        }
    };

    // The two fronts interlock long before they connect, and the dispatcher
    // can see where: rescan for candidate BRIDGE edges — unknown edges
    // directly between a start-component and a goal-component room (each
    // probe either completes connectivity or kills a bridge), then
    // distance-2 bridges through one unknown room. The tip-midpoint disk
    // is only the fallback while the fronts are still far apart.
    vector<long long> bridgeQ;
    size_t bridgePos = 0;
    auto retarget = [&]() {
        if (!dirty || turn - lastCalc < 64) return;
        lastCalc = turn;
        dirty = false;
        const int MM = m * m, sroot = dsu.find(start), groot = dsu.find(goal);
        int bestS = INT_MAX, bestG = INT_MAX, tipS = start, tipG = goal;
        bridgeQ.clear();
        bridgePos = 0;
        vector<long long> tier2;
        auto side = [&](int x) { // 0 = start comp, 1 = goal comp, -1 other
            int rt = dsu.find(x);
            return rt == sroot ? 0 : rt == groot ? 1 : -1;
        };
        for (int x = 0; x < MM; x++) {
            int r = x / m, c = x % m, sd = side(x);
            if (sd == 0) {
                int d = (m - 1 - r) + (m - 1 - c);
                if (d < bestS) { bestS = d; tipS = x; }
            } else if (sd == 1) {
                int d = r + c;
                if (d < bestG) { bestG = d; tipG = x; }
            } else { // unknown room: distance-2 bridge if it touches both
                bool tS = false, tG = false;
                for (int d = 0; d < 4; d++) {
                    int nr = r + di[d], nc = c + dj[d];
                    if (nr < 0 || nc < 0 || nr >= m || nc >= m) continue;
                    if (knownMask[x] & (1 << d)) continue;
                    int nsd = side(nr * m + nc);
                    tS |= nsd == 0;
                    tG |= nsd == 1;
                }
                if (tS && tG)
                    for (int d = 0; d < 4; d++) {
                        int nr = r + di[d], nc = c + dj[d];
                        if (nr < 0 || nc < 0 || nr >= m || nc >= m) continue;
                        if (knownMask[x] & (1 << d)) continue;
                        if (side(nr * m + nc) >= 0) tier2.push_back(edgeIdOf(x, d));
                    }
            }
            for (int d = 0; d < 2; d++) { // direct bridges (D/R: each once)
                int nr = r + di[d], nc = c + dj[d];
                if (nr >= m || nc >= m) continue;
                if (knownMask[x] & (1 << d)) continue;
                int osd = side(nr * m + nc);
                if (sd >= 0 && osd >= 0 && sd != osd)
                    bridgeQ.push_back(edgeIdOf(x, d));
            }
        }
        bridgeQ.insert(bridgeQ.end(), tier2.begin(), tier2.end());
        int ntr = (tipS / m + tipG / m) / 2, ntc = (tipS % m + tipG % m) / 2;
        if (abs(ntr - tr) + abs(ntc - tc) > 4) { // moved: rescan around it
            tr = ntr;
            tc = ntc;
            rad = 0;
            exhausted = false;
            cand.clear();
            candPos = 0;
        }
    };

    auto tryClaim = [&]() {
        if (dsu.find(start) != dsu.find(goal)) return;
        vector<int> par((size_t)m * m, -1);
        vector<uint8_t> pmv((size_t)m * m, 0), seen((size_t)m * m, 0);
        deque<int> q{start};
        seen[start] = 1;
        while (!q.empty()) {
            int cur = q.front(); q.pop_front();
            if (cur == goal) break;
            int r = cur / m, c = cur % m;
            for (int d = 0; d < 4; d++) {
                if (!(openMask[cur] & (1 << d))) continue;
                int nxt = (r + di[d]) * m + (c + dj[d]);
                if (seen[nxt]) continue;
                seen[nxt] = 1;
                par[nxt] = cur;
                pmv[nxt] = (uint8_t)d;
                q.push_back(nxt);
            }
        }
        if (!seen[goal]) return;
        string path;
        vector<uint8_t> seq;
        for (int v = goal; v != start; v = par[v]) seq.push_back(pmv[v]);
        for (int t = (int)seq.size() - 1; t >= 0; t--) {
            path += dch[seq[t]]; path += dch[seq[t]];
        }
        wr("! " + path);
        exit(0);
    };

    for (;; turn++) {
        tryClaim();
        if (misses > 30000) soloSolve();
        {
            int sendTo = -1;
            for (int w = 1; w < (int)A; w++)
                if (!relayBuf[w].empty() &&
                    ((long long)relayBuf[w].size() >= RELAY_CH ||
                     turn - relayAge[w] >= 96)) {
                    sendTo = w;
                    break;
                }
            if (sendTo > 0) {
                long long take = min((long long)relayBuf[sendTo].size(), RELAY_CH);
                wr("> " + to_string(sendTo) + " R " +
                   relayBuf[sendTo].substr(0, take));
                rdline(); // OK
                relayBuf[sendTo].erase(0, take);
                relayAge[sendTo] = turn;
                continue;
            }
        }
        if (dryProbes > 0) { // inbox was dry: probe the gap
            retarget();
            auto skipKnown = [&](vector<long long> &v, size_t &pos) {
                while (pos < v.size()) { // skip edges learned meanwhile
                    EdgeRef x = edgeInfo(v[pos]);
                    if ((knownMask[x.ra] & (1 << x.dir)) ||
                        dsu.find(x.ra) == dsu.find(x.rb)) {
                        knownMask[x.ra] |= 1 << x.dir;
                        knownMask[x.rb] |= 1 << (x.dir ^ 2);
                        pos++;
                        continue;
                    }
                    break;
                }
                return pos < v.size();
            };
            long long pick = -1;
            if (skipKnown(bridgeQ, bridgePos)) {
                pick = bridgeQ[bridgePos++];
            } else if (!exhausted) {
                if (!skipKnown(cand, candPos)) refill();
                if (!exhausted && skipKnown(cand, candPos)) pick = cand[candPos++];
            }
            if (pick >= 0) {
                EdgeRef x = edgeInfo(pick);
                wr("? " + to_string(x.pr) + " " + to_string(x.pc));
                bool open = rdline()[0] == '1';
                knownMask[x.ra] |= 1 << x.dir;
                knownMask[x.rb] |= 1 << (x.dir ^ 2);
                if (open) {
                    openMask[x.ra] |= 1 << x.dir;
                    openMask[x.rb] |= 1 << (x.dir ^ 2);
                    dsu.unite(x.ra, x.rb);
                    dirty = true;
                }
                uint32_t v = ((uint32_t)pick << 1) | (open ? 1 : 0);
                for (int w = 1; w < (int)A; w++) relayTo(w, v, turn);
                dryProbes--;
                continue;
            }
        }
        wr("< ?");
        string line = rdline();
        if (line == "- -") { misses++; dryProbes = 3; continue; }
        misses = 0;
        dryProbes = 0;
        size_t sp = line.find(' ');
        string body = line.substr(sp + 1);
        if (body[0] != 'F') continue;
        long long snd = stoll(line.substr(0, sp));
        for (size_t pos = 2; pos + 3 <= body.size(); pos += 3) {
            uint32_t v = unpack18(body, pos);
            long long e = (long long)(v >> 1);
            if (e >= E) continue;
            EdgeRef x = edgeInfo(e);
            knownMask[x.ra] |= 1 << x.dir;
            knownMask[x.rb] |= 1 << (x.dir ^ 2);
            if (v & 1) {
                dsu.unite(x.ra, x.rb);
                openMask[x.ra] |= 1 << x.dir;
                openMask[x.rb] |= 1 << (x.dir ^ 2);
                dirty = true;
            }
            for (int w = 1; w < (int)A; w++) // to the opposite side only
                if ((w & 1) != (snd & 1)) relayTo(w, v, turn);
        }
    }
}

// ---------------- dispatcher ----------------
static void scanDispatcher() {
    const long long E = numEdges();
    Know K;
    vector<uint8_t> haveBit((size_t)E, 0);
    const int start = 0, goal = m * m - 1;
    long long known = 0, misses = 0;
    long long dIdx = 0; // own interleave slot index (empty when dispW()==0)
    int dryProbes = 0;  // bridge/own-slot probes left before the next inbox poll
    long long turn = 0, lastCalc = -1000;
    bool dirty = true;  // connectivity changed since bridgeQ last built

    // Idle-turn meeting-zone probing (ported from frontDispatcher). Measured
    // (event-log) the scan dispatcher is essentially IDLE the whole game
    // (~0 dry probes, thousands of misses) while the claim-critical edge sits
    // ~90 turns buffered in some scanner. Instead of waiting for that flush,
    // agent 0 spends its free turns probing unknown edges in expanding L1
    // rings around the midpoint of the gap between the start- and goal-side
    // component tips, so it often discovers the connecting edge ITSELF with
    // zero scanner-buffer latency. bridgeQ (exact bridges) is still tried
    // first; this disk is the fallback while the fronts are still apart.
    int tr = m / 2, tc = m / 2, rad = 0;
    bool exhausted = false;
    vector<long long> cand;
    size_t candPos = 0;

    auto record = [&](long long pos, int bit) { // pos: index into scanPerm
        if (haveBit[pos]) return;
        haveBit[pos] = 1;
        known++;
        EdgeRef x = edgeInfo(scanPerm[pos]);
        if (bit && K.find(x.ra) != K.find(x.rb)) dirty = true;
        K.set(x.ra, x.rb, x.dir, bit);
    };
    auto refill = [&]() { // next ring of unknown edges around (tr,tc)
        cand.clear();
        candPos = 0;
        auto pushRoom = [&](int r, int c) {
            if (r < 0 || c < 0 || r >= m || c >= m) return;
            int room = r * m + c;
            for (int d = 0; d < 2; d++) { // D and R: each edge once
                int nr = r + di[d], nc = c + dj[d];
                if (nr >= m || nc >= m) continue;
                if (K.knownMask[room] & (1 << d)) continue;
                if (K.find(room) == K.find(nr * m + nc)) { // cycle rule
                    K.knownMask[room] |= 1 << d;
                    K.knownMask[nr * m + nc] |= 1 << (d ^ 2);
                    continue;
                }
                cand.push_back(edgeIdOf(room, d));
            }
        };
        while (cand.empty()) {
            if (rad > 2 * (m - 1)) { exhausted = true; return; }
            if (rad == 0) pushRoom(tr, tc);
            else
                for (int k = 0; k < rad; k++) {
                    pushRoom(tr - rad + k, tc + k);
                    pushRoom(tr + k, tc + rad - k);
                    pushRoom(tr + rad - k, tc - k);
                    pushRoom(tr - k, tc - rad + k);
                }
            rad++;
        }
    };
    // Bridge probing on dry turns (ported from frontDispatcher): the claim
    // fires the instant start/goal components connect, so probe edges that
    // could bridge them directly (tier 1) or through one unknown room
    // (tier 2). Recomputed only when connectivity changes and at most every
    // 64 turns. Falls back to own-slot sweeping when no candidate exists.
    vector<long long> bridgeQ;
    size_t bridgePos = 0;
    auto retarget = [&]() {
        if (!dirty || turn - lastCalc < 64) return;
        lastCalc = turn;
        dirty = false;
        const int MM = m * m, sroot = K.find(start), groot = K.find(goal);
        bridgeQ.clear();
        bridgePos = 0;
        vector<long long> tier2;
        int bestS = INT_MAX, bestG = INT_MAX, tipS = start, tipG = goal;
        auto side = [&](int x) { // 0 = start comp, 1 = goal comp, -1 other
            int rt = K.find(x);
            return rt == sroot ? 0 : rt == groot ? 1 : -1;
        };
        for (int x = 0; x < MM; x++) {
            int r = x / m, c = x % m, sd = side(x);
            if (sd == 0) {
                int dd = (m - 1 - r) + (m - 1 - c);
                if (dd < bestS) { bestS = dd; tipS = x; }
            } else if (sd == 1) {
                int dd = r + c;
                if (dd < bestG) { bestG = dd; tipG = x; }
            }
            if (sd < 0) { // unknown room: distance-2 bridge if it touches both
                bool tS = false, tG = false;
                for (int d = 0; d < 4; d++) {
                    int nr = r + di[d], nc = c + dj[d];
                    if (nr < 0 || nc < 0 || nr >= m || nc >= m) continue;
                    if (K.knownMask[x] & (1 << d)) continue;
                    int nsd = side(nr * m + nc);
                    tS |= nsd == 0;
                    tG |= nsd == 1;
                }
                if (tS && tG)
                    for (int d = 0; d < 4; d++) {
                        int nr = r + di[d], nc = c + dj[d];
                        if (nr < 0 || nc < 0 || nr >= m || nc >= m) continue;
                        if (K.knownMask[x] & (1 << d)) continue;
                        if (side(nr * m + nc) >= 0) tier2.push_back(edgeIdOf(x, d));
                    }
            }
            for (int d = 0; d < 2; d++) { // direct bridges (D/R: each once)
                int nr = r + di[d], nc = c + dj[d];
                if (nr >= m || nc >= m) continue;
                if (K.knownMask[x] & (1 << d)) continue;
                int osd = side(nr * m + nc);
                if (sd >= 0 && osd >= 0 && sd != osd)
                    bridgeQ.push_back(edgeIdOf(x, d));
            }
        }
        bridgeQ.insert(bridgeQ.end(), tier2.begin(), tier2.end());
        int ntr = (tipS / m + tipG / m) / 2, ntc = (tipS % m + tipG % m) / 2;
        if (abs(ntr - tr) + abs(ntc - tc) > 4) { // meeting zone moved: recenter
            tr = ntr;
            tc = ntc;
            rad = 0;
            exhausted = false;
            cand.clear();
            candPos = 0;
        }
    };
    auto skipKnown = [&](vector<long long> &v, size_t &pos) {
        while (pos < v.size()) { // skip edges learned/cycled meanwhile
            EdgeRef x = edgeInfo(v[pos]);
            if ((K.knownMask[x.ra] & (1 << x.dir)) ||
                K.find(x.ra) == K.find(x.rb)) {
                K.knownMask[x.ra] |= 1 << x.dir;
                K.knownMask[x.rb] |= 1 << (x.dir ^ 2);
                pos++;
                continue;
            }
            break;
        }
        return pos < v.size();
    };
    auto tryClaim = [&]() {
        if (K.find(start) != K.find(goal)) return;
        vector<int> par((size_t)m * m, -1);
        vector<uint8_t> pmv((size_t)m * m, 0), seen((size_t)m * m, 0);
        deque<int> q{start};
        seen[start] = 1;
        while (!q.empty()) {
            int cur = q.front(); q.pop_front();
            if (cur == goal) break;
            int r = cur / m, c = cur % m;
            for (int d = 0; d < 4; d++) {
                if (!(K.openMask[cur] & (1 << d))) continue;
                int nxt = (r + di[d]) * m + (c + dj[d]);
                if (seen[nxt]) continue;
                seen[nxt] = 1;
                par[nxt] = cur;
                pmv[nxt] = (uint8_t)d;
                q.push_back(nxt);
            }
        }
        if (!seen[goal]) return;
        string path;
        vector<uint8_t> seq;
        for (int v = goal; v != start; v = par[v]) seq.push_back(pmv[v]);
        for (int t = (int)seq.size() - 1; t >= 0; t--) {
            path += dch[seq[t]]; path += dch[seq[t]];
        }
        wr("! " + path);
        exit(0);
    };

    for (; ; turn++) {
        tryClaim();
        if (known >= E || misses > 30000) soloSolve();
        // sweep own slots (free deductions) — never costs a turn
        while (dispW() && dispPos(dIdx) < E && haveBit[dispPos(dIdx)]) dIdx++;
        if (dispW() && dispPos(dIdx) < E) {
            long long dp = dispPos(dIdx);
            EdgeRef x = edgeInfo(scanPerm[dp]);
            int v = K.deduce(x.ra, x.rb, x.dir);
            if (v >= 0) { record(dp, v); dIdx++; continue; } // no turn spent
        }
        if (dryProbes > 0) { // inbox was dry: prefer a bridge probe
            retarget();
            long long pick = -1;
            bool ownSlot = false;
            long long dp = -1;
            if (skipKnown(bridgeQ, bridgePos)) {
                pick = bridgeQ[bridgePos++];
            } else if (A >= 16 && !exhausted &&
                       (skipKnown(cand, candPos) ||
                        ([&] { refill(); return skipKnown(cand, candPos); }()))) {
                // meeting-zone disk: unknown edges around the tip midpoint
                pick = cand[candPos++];
            } else if (dispW() && dispPos(dIdx) < E) {
                // fall back to own interleave slot (existing scan behaviour)
                dp = dispPos(dIdx);
                pick = scanPerm[dp];
                ownSlot = true;
            }
            if (pick >= 0) {
                EdgeRef x = edgeInfo(pick);
                wr("? " + to_string(x.pr) + " " + to_string(x.pc));
                int bit = rdline()[0] == '1' ? 1 : 0;
                if (ownSlot) { record(dp, bit); dIdx++; }
                else {
                    if (bit && K.find(x.ra) != K.find(x.rb)) dirty = true;
                    K.set(x.ra, x.rb, x.dir, bit);
                }
                dryProbes--;
                continue;
            }
        }
        wr("< ?");
        string line = rdline();
        if (line == "- -") { misses++; dryProbes = 3; continue; }
        dryProbes = 0;
        istringstream in(line);
        long long snd, k; string tag, enc;
        in >> snd >> tag >> k >> enc;
        if (tag != "S") continue;
        for (size_t t = 0; t < enc.size() * 6; t++) {
            long long pos = scanPos(snd - 1, k + (long long)t);
            if (pos >= E) break;
            int bit = ((enc[t / 6] - '0') >> (5 - t % 6)) & 1;
            record(pos, bit);
        }
    }
}


static const int FRONTIER_MAX_A = 8;

int main() {
    {
        istringstream in(rdline());
        in >> N >> A >> ID >> MAXLEN;
    }
    m = (int)((N + 1) / 2);
    if (N == 1) {
        if (ID == 0) wr("!");
        else wr("halt");
        return 0;
    }
    if (A == 1) { walker(true, 0); return 0; }
    if (A == 2) {
        walker(ID % 2 == 0, 0);
        return 0;
    }
    bool useFrontier = A <= FRONTIER_MAX_A;
    if (useFrontier) {
        if (ID == 0) frontDispatcher();
        else frontierWorker();
    } else {
        buildScanPerm();
        if (ID == 0) scanDispatcher();
        else scanner(ID - 1);
    }
    return 0;
}