// Datacenter Imprisonment (D) — v4: hybrid static-scan + adaptive brain.
//
// Maze model (from provided generator source): rooms at odd (r,c) are always
// empty, even/even cells always walls; the only unknowns are the E = 2m(m-1)
// door cells between adjacent rooms, m = (N+1)/2. Empty cells form a
// spanning tree of the rooms, so two sound inference rules apply everywhere:
//   cycle rule: endpoints already connected -> door closed (free)
//   cut rule:   component with exactly one undetermined incident door -> open
//
// HYBRID mode (E large relative to A): workers 1..A-1 statically scan
// diagonal stripes of the maze (band-near-diagonal doors first) with local
// inference, and send packed result bits to agent 0 at synchronized turn
// milestones (every D-th own turn), so agent 0 polls with zero misses.
// Agent 0 (the brain) maintains a global closure (DSU + per-component
// undetermined-door sets with cut/cycle cascades) plus side labels: rooms
// reachable from (1,1) are side S, from (N,N) side G. Every turn it either
// reads a due worker message or makes one FRESH adaptive query on the best
// frontier door (key = treedist + 4*manhattan-to-other-corner, alternating
// sides). It claims the moment S and G connect. Fresh queries are ~2.5x more
// informative per turn than static ones, which is where the speedup at
// low/mid agent counts comes from.
//
// STATIC mode (small E per agent): v2 protocol — contiguous Hilbert ranges,
// local inference, eager packed sends, staggered loads, DSU early claim.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

static const char* ALPH =
    "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/";
static int VAL[256];

static int N, A, ID, B;   // maze size, num agents, my id, max msg len
static ll m, E, L;        // rooms per side, candidate door edges, bits per msg

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

struct EdgeI {
    int u, v;   // room indices (row*m+col)
    char dir;   // direction u -> v: 'R' or 'D'
    int qr, qc; // door cell to query
};

// Raw edge enumeration: for each room row r: (m-1) horizontal doors, then
// (for r < m-1) m vertical doors below the row.
static EdgeI edgeInfoRaw(ll idx) {
    ll rowBlock = 2 * m - 1;
    ll full = (m - 1) * rowBlock;
    ll r, off;
    if (idx < full) {
        r = idx / rowBlock;
        off = idx % rowBlock;
    } else {
        r = m - 1;
        off = idx - full;
    }
    if (off < m - 1) {
        int u = (int)(r * m + off);
        return {u, u + 1, 'R', (int)(2 * r + 1), (int)(2 * off + 2)};
    }
    ll c = off - (m - 1);
    int u = (int)(r * m + c);
    return {u, (int)(u + m), 'D', (int)(2 * r + 2), (int)(2 * c + 1)};
}

static bool probeCell(int qr, int qc) {
    char buf[48];
    snprintf(buf, sizeof buf, "? %d %d", qr, qc);
    wr(buf);
    string r = rd();
    return !r.empty() && r[0] == '1';
}

static ll hilbertD(int x, int y, int order) {
    ll d = 0;
    for (int s = order / 2; s > 0; s /= 2) {
        int rx = (x & s) > 0, ry = (y & s) > 0;
        d += (ll)s * s * ((3 * rx) ^ ry);
        if (ry == 0) {
            if (rx == 1) {
                x = s - 1 - x;
                y = s - 1 - y;
            }
            swap(x, y);
        }
    }
    return d;
}

// ---------------- shared path-building state ----------------

static vector<uint8_t> openR, openD;  // per room: right/down door open

static string buildPath() {
    int R = (int)(m * m), target = R - 1;
    vector<int> par(R, -1);
    vector<char> pd(R, 0);
    deque<int> q;
    par[0] = 0;
    q.push_back(0);
    int mm = (int)m;
    while (!q.empty()) {
        int u = q.front();
        q.pop_front();
        if (u == target) break;
        int r = u / mm, c = u % mm;
        if (c + 1 < mm && openR[u] && par[u + 1] < 0) {
            par[u + 1] = u; pd[u + 1] = 'R'; q.push_back(u + 1);
        }
        if (r + 1 < mm && openD[u] && par[u + mm] < 0) {
            par[u + mm] = u; pd[u + mm] = 'D'; q.push_back(u + mm);
        }
        if (c > 0 && openR[u - 1] && par[u - 1] < 0) {
            par[u - 1] = u; pd[u - 1] = 'L'; q.push_back(u - 1);
        }
        if (r > 0 && openD[u - mm] && par[u - mm] < 0) {
            par[u - mm] = u; pd[u - mm] = 'U'; q.push_back(u - mm);
        }
    }
    if (par[target] < 0) return "";
    string dirs;
    for (int cur = target; cur != 0; cur = par[cur]) dirs.push_back(pd[cur]);
    reverse(dirs.begin(), dirs.end());
    string out;
    out.reserve(dirs.size() * 2);
    for (char c : dirs) {
        out.push_back(c);
        out.push_back(c);
    }
    return out;
}

[[noreturn]] static void claimAndExit() {
    wr("! " + buildPath());
    exit(0);
}

// Local inference used while scanning (cycle + cut rules against my own
// discovered forest; out-of-my-knowledge doors stay counted as unknown).
struct Infer {
    vector<int> par;
    vector<ll> slot;
    Infer(int n) : par(n), slot(n, 0) {
        iota(par.begin(), par.end(), 0);
        int mm = (int)m;
        for (int r = 0; r < mm; ++r)
            for (int c = 0; c < mm; ++c)
                slot[r * mm + c] = (r > 0) + (r + 1 < mm) + (c > 0) + (c + 1 < mm);
    }
    int find(int x) {
        while (par[x] != x) x = par[x] = par[par[x]];
        return x;
    }
    void unite(int a, int b) {
        a = find(a);
        b = find(b);
        if (a == b) return;
        par[a] = b;
        slot[b] += slot[a];
    }
    pair<bool, bool> resolve(const EdgeI& e) {  // {open, queried}
        int ru = find(e.u), rv = find(e.v);
        if (ru == rv) {  // cycle rule
            slot[ru] -= 2;
            return {false, false};
        }
        if (slot[ru] == 1 || slot[rv] == 1) {  // cut rule
            slot[ru]--;
            slot[rv]--;
            unite(e.u, e.v);
            return {true, false};
        }
        bool open = probeCell(e.qr, e.qc);
        slot[ru]--;
        slot[rv]--;
        if (open) unite(e.u, e.v);
        return {open, true};
    }
};

// ================= STATIC protocol (v2) =================

static vector<ll> PERM;  // position -> raw edge index (Hilbert order)

static void buildPerm() {
    int order = 1;
    while (order < N + 2) order <<= 1;
    vector<pair<ll, ll>> keys(E);
    for (ll e = 0; e < E; ++e) {
        EdgeI ei = edgeInfoRaw(e);
        keys[e] = {hilbertD(ei.qr, ei.qc, order), e};
    }
    sort(keys.begin(), keys.end());
    PERM.resize(E);
    for (ll i = 0; i < E; ++i) PERM[i] = keys[i].second;
}

static inline EdgeI edgeInfoP(ll idx) { return edgeInfoRaw(PERM[idx]); }

static const ll SLACK = 1;

static ll qNeed(ll p) {  // conservative queries bound after inference
    int pct;
    if (p < 300) pct = 100;
    else if (p < 1000) pct = 96;
    else if (p < 3000) pct = 93;
    else if (p < 20000) pct = 91;
    else pct = 89;
    return (p * pct + 99) / 100;
}

static ll sendsFor(ll p) { return p ? (p + L - 1) / L : 0; }

static ll maxProbes(ll cap) {
    if (cap < 2) return 0;
    ll lo = 0, hi = cap * 2 + 4;
    while (lo < hi) {
        ll mid = (lo + hi + 1) / 2;
        if (qNeed(mid) + sendsFor(mid) <= cap)
            lo = mid;
        else
            hi = mid - 1;
    }
    return lo;
}

static ll maxRootProbes(ll budget) {
    if (budget <= 0) return 0;
    ll lo = 0, hi = budget * 2 + 4;
    while (lo < hi) {
        ll mid = (lo + hi + 1) / 2;
        if (qNeed(mid) <= budget)
            lo = mid;
        else
            hi = mid - 1;
    }
    return lo;
}

static bool feasible(ll T, vector<ll>& pout) {
    vector<ll> pmax(A, 0);
    for (int i = 1; i < A; ++i) {
        ll cap = T - 2 - SLACK - (ll)(A - 1 - i);
        pmax[i] = maxProbes(cap);
    }
    ll M = 0;
    for (int iter = 0; iter < 400; ++iter) {
        ll p0 = min(E, maxRootProbes(T - 1 - SLACK - M));
        ll rem = E - p0, Mact = 0;
        vector<ll> p(A, 0);
        p[0] = p0;
        for (int i = A - 1; i >= 1 && rem > 0; --i) {
            p[i] = min(pmax[i], rem);
            rem -= p[i];
            Mact += sendsFor(p[i]);
        }
        if (rem > 0) return false;
        if (qNeed(p0) + Mact + 1 + SLACK <= T) {
            pout = p;
            return true;
        }
        if (Mact <= M) return false;
        M = Mact;
    }
    return false;
}

static vector<ll> computeSchedule() {
    ll lo = 1, hi = E + 2LL * A + 64;
    vector<ll> best;
    while (lo <= hi) {
        ll mid = lo + (hi - lo) / 2;
        vector<ll> p;
        if (feasible(mid, p)) {
            best = p;
            hi = mid - 1;
        } else {
            lo = mid + 1;
        }
    }
    if (best.empty()) {
        best.assign(A, 0);
        best[0] = E;
    }
    return best;
}

static void runWorkerStatic(ll S, ll cnt) {
    if (cnt == 0) return;  // exit now; costs no turns
    Infer inf((int)(m * m));
    string buf;
    int acc = 0, nb = 0;
    for (ll t = 0; t < cnt; ++t) {
        EdgeI e = edgeInfoP(S + t);
        auto [open, queried] = inf.resolve(e);
        if (open) acc |= 1 << nb;
        if (++nb == 6) {
            buf.push_back(ALPH[acc]);
            acc = 0;
            nb = 0;
        }
        if (queried && (int)buf.size() >= B) {
            wr("> 0 " + buf.substr(0, B));
            buf.erase(0, B);
            rd();
        }
    }
    if (nb) buf.push_back(ALPH[acc]);
    while (!buf.empty()) {
        int take = min<int>(B, (int)buf.size());
        wr("> 0 " + buf.substr(0, take));
        buf.erase(0, take);
        rd();
    }
    // exit; merlin treats EOF like halt but without consuming a turn
}

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 uni(int a, int b) {
        a = find(a);
        b = find(b);
        if (a != b) p[a] = b;
    }
};

static void runRootStatic(const vector<ll>& p) {
    vector<uint8_t> knownBit(E, 0);
    DSU dsu((int)(m * m));
    auto connectedSG = [&]() { return dsu.find(0) == dsu.find((int)(m * m - 1)); };
    auto applyBit = [&](ll idx, bool open) {
        if (knownBit[idx]) return;
        knownBit[idx] = 1;
        if (!open) return;
        EdgeI e = edgeInfoP(idx);
        if (e.dir == 'R')
            openR[e.u] = 1;
        else
            openD[e.u] = 1;
        dsu.uni(e.u, e.v);
    };

    vector<ll> S(A + 1, 0);
    for (int i = 0; i < A; ++i) S[i + 1] = S[i] + p[i];

    {
        Infer inf((int)(m * m));
        for (ll t = 0; t < p[0]; ++t) {
            EdgeI e = edgeInfoP(t);
            auto [open, queried] = inf.resolve(e);
            (void)queried;
            applyBit(t, open);
            if (open && connectedSG()) claimAndExit();
        }
    }

    vector<ll> bitsGot(A, 0), msgsExp(A, 0);
    ll totMsgs = 0;
    for (int i = 1; i < A; ++i) {
        ll chars = (p[i] + 5) / 6;
        msgsExp[i] = (chars + B - 1) / B;
        totMsgs += msgsExp[i];
    }
    ll gotMsgs = 0;
    int miss = 0;
    while (gotMsgs < totMsgs) {
        wr("< ?");
        string line = rd();
        if (!line.empty() && line[0] == '-') {
            if (++miss > 300) break;  // a worker probably died
            continue;
        }
        miss = 0;
        size_t sp = line.find(' ');
        if (sp == string::npos) continue;
        int snd = atoi(line.substr(0, sp).c_str());
        if (snd < 1 || snd >= A) continue;
        ++gotMsgs;
        for (size_t ci = sp + 1; ci < line.size(); ++ci) {
            int v = VAL[(unsigned char)line[ci]];
            if (v < 0) continue;
            for (int b = 0; b < 6 && bitsGot[snd] < p[snd]; ++b, ++bitsGot[snd])
                applyBit(S[snd] + bitsGot[snd], (v >> b) & 1);
        }
        if (connectedSG()) claimAndExit();
    }

    for (ll idx = 0; idx < E; ++idx) {  // fallback
        if (knownBit[idx]) continue;
        EdgeI e = edgeInfoP(idx);
        applyBit(idx, probeCell(e.qr, e.qc));
        if (connectedSG()) claimAndExit();
    }
    claimAndExit();
}

// ================= HYBRID protocol =================

// stripe assignment: doors sorted by diagonal projection (qr+qc, Hilbert),
// cut into A-1 equal chunks; each chunk scanned band-near-diagonal first
static void buildStripes(vector<vector<int>>& assign) {
    int horder = 1;
    while (horder < N + 2) horder <<= 1;
    int W = A - 1;
    vector<pair<pair<int, ll>, int>> pk(E);
    vector<int> QR(E), QC(E);
    for (ll e = 0; e < E; ++e) {
        EdgeI ei = edgeInfoRaw(e);
        QR[e] = ei.qr;
        QC[e] = ei.qc;
        pk[e] = {{ei.qr + ei.qc, hilbertD(ei.qr, ei.qc, horder)}, (int)e};
    }
    sort(pk.begin(), pk.end());
    assign.assign(A, {});
    for (int w = 1; w <= W; ++w) {
        ll s = (ll)(w - 1) * E / W, t = (ll)w * E / W;
        auto& lst = assign[w];
        lst.reserve(t - s);
        for (ll i = s; i < t; ++i) lst.push_back(pk[i].second);
        stable_sort(lst.begin(), lst.end(), [&](int x, int y) {
            return abs(QR[x] - QC[x]) < abs(QR[y] - QC[y]);
        });
    }
}

// Milestone interval (worker turns between sends), same on all agents.
// Chosen so (a) the brain's receive load stays ~<=12% of its turns,
// (b) a message's results fit in one body even with inference surplus,
// (c) the LAST milestone lands right around the expected scan end (~0.97 of
// the share needs a query turn), so final results are not held hostage.
static ll milestoneD() {
    ll W = A - 1;
    ll share = (E + W - 1) / W;
    ll cap = 6LL * B * 4 / 5;
    ll dbase = max<ll>(64, min(8LL * W, cap));
    ll target = max<ll>(1, share * 97 / 100);
    ll k = max<ll>(1, (target + dbase / 2) / dbase);
    ll D = (target + k - 1) / k;
    return max<ll>(48, min(D, cap));
}

static void runWorkerHybrid(const vector<int>& doors) {
    ll D = milestoneD();
    Infer inf((int)(m * m));
    string buf;         // complete chars ready to send
    int acc = 0, nb = 0;
    ll myTurn = 0;
    size_t cur = 0;
    ll resultsSent = 0, resultsTotal = (ll)doors.size();
    auto flushChar = [&]() {
        if (nb > 0) {
            buf.push_back(ALPH[acc]);
            acc = 0;
            nb = 0;
        }
    };
    while (resultsSent < resultsTotal) {
        if ((myTurn + 1) % D == 0) {
            // milestone send (whatever is buffered; pad-flush only when done)
            if (cur >= doors.size()) flushChar();
            int take = min<int>(B, (int)buf.size());
            wr("> 0 " + buf.substr(0, take));
            buf.erase(0, take);
            rd();
            ++myTurn;
            resultsSent = min(resultsTotal, resultsSent + 6LL * take);
            continue;
        }
        if (cur < doors.size()) {
            // resolve until a real query consumes the turn
            bool queried = false;
            while (cur < doors.size() && !queried) {
                EdgeI e = edgeInfoRaw(doors[cur]);
                auto [open, q] = inf.resolve(e);
                queried = q;
                if (open) acc |= 1 << nb;
                if (++nb == 6) {
                    buf.push_back(ALPH[acc]);
                    acc = 0;
                    nb = 0;
                }
                ++cur;
            }
            if (queried) {
                ++myTurn;
                continue;
            }
            // range finished purely by inference; loop to milestone wait
        }
        // nothing to scan; wait for next milestone
        wr(".");
        rd();
        ++myTurn;
    }
    // exit (EOF; costs no turn)
}

struct Brain {
    int mm, rooms, W;
    ll D;
    ll myTurn = 0;
    bool connected = false;

    // closure state
    vector<int> par;
    vector<int> rootSide;
    vector<vector<int>> members;
    vector<unordered_set<int>> doorSet;
    vector<int8_t> det;
    vector<int8_t> side;
    vector<int> dist;
    deque<int> work;

    typedef pair<int, int> HE;  // (key, door)
    priority_queue<HE, vector<HE>, greater<HE>> heap[3];
    int toggle = 1;
    vector<int> spec;
    size_t specCur = 0;

    // worker streams
    vector<vector<int>>* assign;
    vector<ll> got;       // results decoded per worker
    vector<int> accBits;  // (unused; chars are always full 6 bits)

    Brain(vector<vector<int>>* as) : assign(as) {
        mm = (int)m;
        rooms = mm * mm;
        W = A - 1;
        D = milestoneD();
        par.resize(rooms);
        iota(par.begin(), par.end(), 0);
        rootSide.assign(rooms, 0);
        members.assign(rooms, {});
        for (int r = 0; r < rooms; ++r) members[r] = {r};
        doorSet.assign(rooms, {});
        det.assign(E, -1);
        side.assign(rooms, 0);
        dist.assign(rooms, 0);
        got.assign(A, 0);
        for (ll e = 0; e < E; ++e) {
            EdgeI ei = edgeInfoRaw(e);
            doorSet[ei.u].insert((int)e);
            doorSet[ei.v].insert((int)e);
        }
        // speculative order: corner blobs
        spec.resize(E);
        vector<pair<int, int>> keys(E);
        for (ll e = 0; e < E; ++e) {
            EdgeI ei = edgeInfoRaw(e);
            int ur = ei.u / mm, uc = ei.u % mm;
            int d1 = ur + uc;
            int d2 = (mm - 1 - ur) + (mm - 1 - uc);
            keys[e] = {min(d1, d2), (int)e};
        }
        sort(keys.begin(), keys.end());
        for (ll i = 0; i < E; ++i) spec[i] = keys[i].second;

        label(0, 1, 0);
        label(rooms - 1, 2, 0);
        rootSide[find(0)] = 1;
        rootSide[find(rooms - 1)] = 2;
    }
    int find(int x) {
        while (par[x] != x) x = par[x] = par[par[x]];
        return x;
    }
    int mdTo(int room, int s) {
        int r = room / mm, c = room % mm;
        if (s == 1) return (mm - 1 - r) + (mm - 1 - c);
        return r + c;
    }
    void pushDoors(int room) {
        int s = side[room];
        if (!s) return;
        int r = room / mm, c = room % mm;
        ll rowBlock = 2 * m - 1;
        auto add = [&](ll d, int nb) {
            if (det[d] != -1) return;
            heap[s].push({dist[room] + 4 * mdTo(nb, s), (int)d});
        };
        if (c + 1 < mm) add((ll)r * rowBlock + c, room + 1);
        if (c > 0) add((ll)r * rowBlock + (c - 1), room - 1);
        if (r + 1 < mm) add((ll)r * rowBlock + (m - 1) + c, room + mm);
        if (r > 0) add((ll)(r - 1) * rowBlock + (m - 1) + c, room - mm);
    }
    void label(int room, int s, int d) {
        if (side[room]) return;
        side[room] = (int8_t)s;
        dist[room] = d;
        pushDoors(room);
    }
    void setClosed(int e) {
        if (det[e] != -1) return;
        det[e] = 0;
        EdgeI ei = edgeInfoRaw(e);
        int ru = find(ei.u), rv = find(ei.v);
        doorSet[ru].erase(e);
        if (rv != ru) doorSet[rv].erase(e);
        work.push_back(ru);
        if (rv != ru) work.push_back(rv);
    }
    void setOpen(int e) {
        if (det[e] != -1) return;
        det[e] = 1;
        EdgeI ei = edgeInfoRaw(e);
        if (ei.dir == 'R')
            openR[ei.u] = 1;
        else
            openD[ei.u] = 1;
        int ru = find(ei.u), rv = find(ei.v);
        doorSet[ru].erase(e);
        if (rv != ru) doorSet[rv].erase(e);
        if (ru == rv) return;
        int su = rootSide[ru], sv = rootSide[rv];
        if (su && sv && su != sv) {
            connected = true;
            return;
        }
        int labRoom = side[ei.u] ? ei.u : (side[ei.v] ? ei.v : -1);
        int db = labRoom >= 0 ? dist[labRoom] + 1 : 0;
        int s = su ? su : sv;
        if (members[ru].size() + doorSet[ru].size() >
            members[rv].size() + doorSet[rv].size()) {
            swap(ru, rv);
            swap(su, sv);
        }
        par[ru] = rv;
        vector<int> internal;
        for (int d : doorSet[ru]) {
            auto it = doorSet[rv].find(d);
            if (it != doorSet[rv].end()) {
                doorSet[rv].erase(it);
                internal.push_back(d);
            } else
                doorSet[rv].insert(d);
        }
        doorSet[ru].clear();
        for (int d : internal)
            if (det[d] == -1) det[d] = 0;
        if (s) {
            if (su == 0)
                for (int room : members[ru]) label(room, s, db);
            else if (sv == 0)
                for (int room : members[rv]) label(room, s, db);
        }
        rootSide[rv] = s;
        if (members[ru].size() > members[rv].size()) members[ru].swap(members[rv]);
        for (int room : members[ru]) members[rv].push_back(room);
        members[ru].clear();
        work.push_back(rv);
    }
    void drain() {
        while (!work.empty()) {
            if (connected) return;
            int r = work.front();
            work.pop_front();
            r = find(r);
            if (doorSet[r].size() == 1) {
                int d = *doorSet[r].begin();
                if (det[d] == -1) setOpen(d);
            }
        }
    }
    void reveal(int e, bool open) {
        if (det[e] != -1) return;
        if (open)
            setOpen(e);
        else
            setClosed(e);
        if (!connected) drain();
    }
    // one fresh adaptive query; false if nothing left to ask
    bool freshQuery() {
        int door = -1;
        for (int attempt = 0; attempt < 2 && door < 0; ++attempt) {
            int s = toggle;
            toggle = 3 - toggle;
            auto& h = heap[s];
            while (!h.empty()) {
                auto [key, d] = h.top();
                h.pop();
                if (det[d] == -1) {
                    door = d;
                    break;
                }
            }
        }
        if (door < 0) {
            while (specCur < (size_t)E) {
                int d = spec[specCur++];
                if (det[d] == -1) {
                    door = d;
                    break;
                }
            }
        }
        if (door < 0) return false;
        EdgeI e = edgeInfoRaw(door);
        bool open = probeCell(e.qr, e.qc);
        ++myTurn;
        reveal(door, open);
        return true;
    }
    void applyMsg(int snd, const string& body) {
        if (snd < 1 || snd >= A) return;
        auto& lst = (*assign)[snd];
        for (char ch : body) {
            int v = VAL[(unsigned char)ch];
            if (v < 0) continue;
            for (int b = 0; b < 6; ++b) {
                if (got[snd] >= (ll)lst.size()) break;
                int d = lst[got[snd]++];
                if (det[d] == -1) reveal(d, (v >> b) & 1);
                if (connected) return;
            }
        }
    }
    void run() {
        ll nextWave = 1;
        ll pending = 0;
        int miss = 0;
        bool deadMode = false;
        for (;;) {
            if (connected) claimAndExit();
            if (myTurn + 1 > nextWave * D) {
                // wave boundary crossed: all live workers sent at turn kD
                if (!deadMode)
                    for (int w2 = 1; w2 < A; ++w2)
                        if (got[w2] < (ll)(*assign)[w2].size()) ++pending;
                ++nextWave;
            }
            if (pending > 0) {
                wr("< ?");
                string line = rd();
                ++myTurn;
                if (line.empty() || line[0] == '-') {
                    if (++miss > 2 * A + 8) {
                        // some worker died; stop expecting waves, go solo
                        deadMode = true;
                        pending = 0;
                        miss = 0;
                    }
                    continue;
                }
                miss = 0;
                --pending;
                size_t sp = line.find(' ');
                if (sp == string::npos) continue;
                int snd = atoi(line.substr(0, sp).c_str());
                applyMsg(snd, line.substr(sp + 1));
                continue;
            }
            if (freshQuery()) continue;
            // nothing to ask (everything determined or in workers' hands)
            if (!connected) {
                // all doors determined implies tree known & connected; if we
                // are here with undetermined doors, wait for next wave
                bool anyUndet = false;
                for (ll e2 = 0; e2 < E; ++e2)
                    if (det[e2] == -1) {
                        anyUndet = true;
                        break;
                    }
                if (!anyUndet) {
                    connected = true;
                    continue;
                }
                wr(".");
                rd();
                ++myTurn;
            }
        }
    }
};

// ================= main =================

// Measured boundary (official judge, 3 seeds per config): hybrid wins when
// each worker's stripe is large enough that the brain's fresh adaptive
// queries dominate the runtime; static wins when the scan is receive-bound.
static bool hybridMode() {
    if (A < 2) return false;
    ll share = E / max(1, A - 1);
    return share >= max<ll>(320, 16LL * A);
}

int main() {
    fill(begin(VAL), end(VAL), -1);
    for (int i = 0; i < 64; ++i) VAL[(unsigned char)ALPH[i]] = i;

    string first = rd();
    if (sscanf(first.c_str(), "%d %d %d %d", &N, &A, &ID, &B) != 4) return 0;
    m = (N + 1) / 2;
    E = 2 * m * (m - 1);
    L = 6LL * B;

    if (E == 0) {  // N == 1
        if (ID == 0) wr("! ");
        return 0;
    }

    openR.assign(m * m, 0);
    openD.assign(m * m, 0);

    if (hybridMode()) {
        vector<vector<int>> assign;
        buildStripes(assign);
        if (ID == 0) {
            Brain brain(&assign);
            brain.run();
        } else {
            runWorkerHybrid(assign[ID]);
        }
    } else {
        buildPerm();
        vector<ll> p = computeSchedule();
        if (ID == 0) {
            runRootStatic(p);
        } else {
            ll S = 0;
            for (int i = 0; i < ID; ++i) S += p[i];
            runWorkerStatic(S, p[ID]);
        }
    }
    return 0;
}