// Problem D — Datacenter Imprisonment (Midnight Code Cup 2026 finals).
//
// This single file is the submission. It contains:
//   * MerlinBase  — abstract interface to the referee; one method call == one turn
//   * MerlinProd  — stdin/stdout implementation (used when submitted)
//   * Strategy    — the agent logic; issues exactly one Merlin command per tick()
//   * main()      — prod entry point (excluded when LOCAL_RUN is defined;
//                   local_run.cpp includes this file and provides MerlinLocal)
//
// Maze structure (from the provided generator source): N is odd, rooms are the
// odd-odd cells (always empty), even-even cells are always walls, and the only
// unknown cells are corridors between orthogonally adjacent rooms. Open
// corridors form a uniform spanning tree over the (N+1)/2 x (N+1)/2 room grid.

#include <algorithm>
#include <cassert>
#include <climits>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <deque>
#include <iostream>
#include <map>
#include <memory>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <vector>

// ---------------------------------------------------------------------------
// Merlin interface
// ---------------------------------------------------------------------------

struct Msg {
    bool ok = false;   // false == "- -" (nothing waiting)
    int sender = -1;
    std::string body;
};

class MerlinBase {
public:
    int N = 0;          // maze is N x N, 1-indexed
    int numAgents = 0;  // total agents in the run
    int agentId = 0;    // our 0-based id
    int maxMsgLen = 0;  // max message body length in bytes

    virtual ~MerlinBase() = default;

    // Every call below consumes this agent's single command for the turn.
    virtual bool query(int r, int c) = 0;                    // ? r c
    virtual void send(int to, const std::string& body) = 0;  // > P M
    virtual Msg recvFrom(int sender) = 0;                    // < Q
    virtual Msg recvAny() = 0;                               // < ?
    virtual void skip() = 0;                                 // .
    virtual void halt() = 0;                                 // halt (terminal)
    virtual void claim(const std::string& path) = 0;         // ! ULDR (terminal)
};

// ---------------------------------------------------------------------------
// Production Merlin: line-based stdio, flush after every line
// ---------------------------------------------------------------------------

class MerlinProd : public MerlinBase {
public:
    MerlinProd() {
        std::string line = readLine();
        std::istringstream ss(line);
        ss >> N >> numAgents >> agentId >> maxMsgLen;
    }

    bool query(int r, int c) override {
        emit("? " + std::to_string(r) + " " + std::to_string(c));
        return readLine() == "1";
    }
    void send(int to, const std::string& body) override {
        emit("> " + std::to_string(to) + " " + body);
        readLine();  // "OK"
    }
    Msg recvFrom(int sender) override {
        emit("< " + std::to_string(sender));
        return parseMsg(readLine());
    }
    Msg recvAny() override {
        emit("< ?");
        return parseMsg(readLine());
    }
    void skip() override {
        emit(".");
        readLine();  // "OK"
    }
    void halt() override { emit("halt"); }                       // no reply
    void claim(const std::string& path) override { emit("! " + path); }  // no reply

private:
    void emit(const std::string& s) {
        std::cout << s << '\n';
        std::cout.flush();
    }
    std::string readLine() {
        std::string line;
        if (!std::getline(std::cin, line)) std::exit(0);  // referee is gone
        if (!line.empty() && line.back() == '\r') line.pop_back();
        return line;
    }
    static Msg parseMsg(const std::string& line) {
        if (line == "- -") return {};
        Msg m;
        m.ok = true;
        size_t sp = line.find(' ');
        m.sender = std::stoi(line.substr(0, sp));
        m.body = (sp == std::string::npos) ? std::string() : line.substr(sp + 1);
        return m;
    }
};

// ---------------------------------------------------------------------------
// Strategy
// ---------------------------------------------------------------------------
//
// Cooperative coordinator/worker design.
//
// Agent 0 (coordinator) owns the world model over the m x m room lattice,
// m = (N+1)/2: corridor statuses (unknown/open/wall), a DSU of rooms with two
// inference rules (a corridor inside one component is a wall; a room with all
// other corridors walled must open its last one), and a probe priority queue:
// corridors on the boundary of the start/goal components first (bidirectional
// greedy, ordered by far room's distance to the opposite corner), then a
// speculative flood of everything else (rings around both corners) so large
// agent counts degrade gracefully into a full split-map.
//
// Workers (agents 1..K-1) are dumb: receive a batch of corridor indices
// (base-64, fixed width), probe them one per turn, send results back as
// packed bits, repeat. The coordinator pipelines two outstanding batches per
// worker and simulates each worker's turn schedule exactly (lockstep makes
// this deterministic), so it reads every result on the precise turn it
// becomes available — no wasted polling turns. Idle coordinator turns go to
// probing the best frontier corridor itself, which is what makes the small-K
// case degenerate into plain adaptive greedy.
//
// A worker that dies is detected by its result failing to arrive on schedule
// (3 retries), and its assigned corridors are recycled.

class Strategy {
public:
    explicit Strategy(MerlinBase* merlin) : M(merlin) {}

    bool done() const { return finished; }

    // Issues exactly one Merlin command per call.
    void tick() {
        if (finished) return;
        if (M->N == 1) {
            if (M->agentId == 0) M->claim("");
            else M->halt();
            finished = true;
            return;
        }
        if (!inited) init();
        if (M->agentId == 0) coordTick();
        else workerTick();
        T++;
    }

private:
    // ---- shared state ------------------------------------------------------
    MerlinBase* M;
    bool finished = false;
    bool inited = false;
    long long T = 0;  // my own turn counter == global turn index (lockstep)

    int m = 0;       // rooms per side
    int C = 0;       // total corridors = 2*m*(m-1)
    int mH = 0;      // horizontal corridors = m*(m-1)
    int idxChars = 1;  // base-64 chars per corridor index
    int K = 1, L = 0;  // NUM_AGENTS, MAX_MSG_LEN
    int Bmax = 8;      // batch size target
    bool allowSpec = true;  // may workers be given speculative probes?
    int specMinK = 0, specMode = 0;

    static int envInt(const char* name, int dflt) {
        const char* v = std::getenv(name);
        return v ? std::atoi(v) : dflt;
    }

    static constexpr char A64 = '0';  // alphabet '0'..'o' (0x30..0x6F)
    static constexpr int SPEC_BASE = 1 << 20;  // speculative prio offset

    void init() {
        inited = true;
        K = M->numAgents;
        L = M->maxMsgLen;
        m = (M->N + 1) / 2;
        mH = m * (m - 1);
        C = 2 * mH;
        idxChars = 1;
        for (int v = 64; v < C; v *= 64) idxChars++;
        int cap = (idxChars > 0) ? L / idxChars : 0;
        // Tuning knobs, env-overridable for local experiments.
        int bFloor = envInt("D_B_FLOOR", 8);
        specMinK = envInt("D_SPEC_MIN_K", 0);  // workers get spec probes if K >= this
        specMode = envInt("D_SPEC_MODE", 1);   // 0: rings from corners, 1: diagonal band
        Bmax = std::min(cap, std::max(bFloor, 2 * (K - 1)));
        allowSpec = (K >= specMinK);
        if (M->agentId == 0) coordInit();
    }

    // ---- corridor geometry -------------------------------------------------
    // H corridor idx = i*(m-1)+j       : rooms (i,j)-(i,j+1), cell (2i+1, 2j+2)
    // V corridor idx = mH + i*m + j    : rooms (i,j)-(i+1,j), cell (2i+2, 2j+1)
    std::pair<int, int> corridorCell(int idx) const {
        if (idx < mH) {
            int i = idx / (m - 1), j = idx % (m - 1);
            return {2 * i + 1, 2 * j + 2};
        }
        int t = idx - mH, i = t / m, j = t % m;
        return {2 * i + 2, 2 * j + 1};
    }
    std::pair<int, int> corridorRooms(int idx) const {  // room ids
        if (idx < mH) {
            int i = idx / (m - 1), j = idx % (m - 1);
            return {i * m + j, i * m + j + 1};
        }
        int t = idx - mH, i = t / m, j = t % m;
        return {i * m + j, (i + 1) * m + j};
    }
    int roomDeg(int room) const {
        int i = room / m, j = room % m;
        return (i > 0) + (i < m - 1) + (j > 0) + (j < m - 1);
    }
    // corridors incident to a room (-1 padded)
    void roomCorridors(int room, int out[4]) const {
        int i = room / m, j = room % m, k = 0;
        out[0] = out[1] = out[2] = out[3] = -1;
        if (j > 0) out[k++] = i * (m - 1) + (j - 1);
        if (j < m - 1) out[k++] = i * (m - 1) + j;
        if (i > 0) out[k++] = mH + (i - 1) * m + j;
        if (i < m - 1) out[k++] = mH + i * m + j;
    }
    int manh(int room, int ti, int tj) const {
        return std::abs(room / m - ti) + std::abs(room % m - tj);
    }

    // ---- base-64 message coding --------------------------------------------
    void encIdx(std::string& s, int v) const {
        for (int k = idxChars - 1; k >= 0; k--) s += char(A64 + ((v >> (6 * k)) & 63));
    }
    int decIdx(const std::string& s, int pos) const {
        int v = 0;
        for (int k = 0; k < idxChars; k++) v = (v << 6) | (s[pos + k] - A64);
        return v;
    }

    // =========================================================================
    // Coordinator
    // =========================================================================
    std::vector<int8_t> st;       // 0 unknown, 1 open, 2 wall (per corridor)
    std::vector<char> assigned;   // corridor handed to a worker, result pending
    std::vector<int> dsuP, dsuSz;
    std::vector<std::vector<int>> members;  // rooms per DSU root
    std::vector<int8_t> wallCnt, unkCnt;    // per room
    std::vector<char> inCorner;   // room is in the start- or goal-component
    std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int>>,
                        std::greater<>> pq;  // (prio, corridor)
    int startRoom = 0, goalRoom = 0;
    bool connectedSG = false;

    struct Batch {
        std::vector<int> idx;
        long long resultReady;  // first turn the result is readable
    };
    struct WorkerSim {
        std::deque<Batch> out;   // sent, result not yet applied
        long long idleFrom = 0;  // turn from which the worker idle-receives
        int misses = 0;
        bool dead = false;
    };
    std::vector<WorkerSim> ws;

    int find(int x) {
        while (dsuP[x] != x) x = dsuP[x] = dsuP[dsuP[x]];
        return x;
    }

    void coordInit() {
        st.assign(C, 0);
        assigned.assign(C, 0);
        dsuP.resize(m * m);
        std::iota(dsuP.begin(), dsuP.end(), 0);
        dsuSz.assign(m * m, 1);
        members.assign(m * m, {});
        for (int r = 0; r < m * m; r++) members[r] = {r};
        wallCnt.assign(m * m, 0);
        unkCnt.resize(m * m);
        for (int r = 0; r < m * m; r++) unkCnt[r] = (int8_t)roomDeg(r);
        inCorner.assign(m * m, 0);
        startRoom = 0;
        goalRoom = m * m - 1;
        inCorner[startRoom] = inCorner[goalRoom] = 1;
        ws.assign(K, {});
        pushRoomFrontier(startRoom);
        pushRoomFrontier(goalRoom);
        // Speculative flood: every corridor, ordered by specMode.
        for (int idx = 0; idx < C; idx++) {
            auto [a, b] = corridorRooms(idx);
            int d;
            if (specMode == 1) {  // band around the S-G diagonal, inside-out
                d = std::min(manh(a, 0, 0) + manh(a, m - 1, m - 1),
                             manh(b, 0, 0) + manh(b, m - 1, m - 1));
            } else {  // rings around both corners
                d = std::min(std::min(manh(a, 0, 0), manh(a, m - 1, m - 1)),
                             std::min(manh(b, 0, 0), manh(b, m - 1, m - 1)));
            }
            pq.push({SPEC_BASE + d, idx});
        }
    }

    void pushRoomFrontier(int room) {
        int cs[4];
        roomCorridors(room, cs);
        bool nearStart = (find(room) == find(startRoom));
        for (int k = 0; k < 4 && cs[k] >= 0; k++) {
            int idx = cs[k];
            if (st[idx] != 0) continue;
            auto [a, b] = corridorRooms(idx);
            int far = (a == room) ? b : a;
            int prio = nearStart ? manh(far, m - 1, m - 1) : manh(far, 0, 0);
            pq.push({prio, idx});
        }
    }

    void forcedCheck(int room) {
        // A spanning tree touches every room: all-but-one wall => last is open.
        if (unkCnt[room] != 1 || wallCnt[room] != roomDeg(room) - 1) return;
        int cs[4];
        roomCorridors(room, cs);
        for (int k = 0; k < 4 && cs[k] >= 0; k++)
            if (st[cs[k]] == 0) {
                applyOpen(cs[k]);
                return;
            }
    }

    void applyWall(int idx) {
        if (st[idx] != 0) return;
        st[idx] = 2;
        auto [a, b] = corridorRooms(idx);
        wallCnt[a]++, unkCnt[a]--;
        wallCnt[b]++, unkCnt[b]--;
        forcedCheck(a);
        forcedCheck(b);
    }

    void applyOpen(int idx) {
        if (st[idx] != 0) return;
        st[idx] = 1;
        auto [a, b] = corridorRooms(idx);
        unkCnt[a]--, unkCnt[b]--;
        int ra = find(a), rb = find(b);
        if (ra == rb) return;  // impossible in a tree; be safe
        int rootS = find(startRoom), rootG = find(goalRoom);
        bool cornerA = (ra == rootS) || (ra == rootG);
        bool cornerB = (rb == rootS) || (rb == rootG);
        if (cornerA && cornerB) connectedSG = true;  // ra,rb are {rootS,rootG}
        // union by size, keep member lists
        int big = (dsuSz[ra] >= dsuSz[rb]) ? ra : rb;
        int small = (big == ra) ? rb : ra;
        dsuP[small] = big;
        dsuSz[big] += dsuSz[small];
        if (!connectedSG && (cornerA || cornerB)) {
            // Exactly one side was corner-connected: the other side's rooms
            // newly join a corner component; their unknown corridors become
            // frontier. (pushRoomFrontier resolves direction post-union.)
            int cornerRoot = cornerA ? ra : rb;
            std::vector<int>& newly = members[(cornerRoot == big) ? small : big];
            for (int r : newly)
                if (!inCorner[r]) {
                    inCorner[r] = 1;
                    pushRoomFrontier(r);
                }
        }
        members[big].insert(members[big].end(), members[small].begin(), members[small].end());
        members[small].clear();
        members[small].shrink_to_fit();
    }

    // Pop the best still-unknown, unassigned corridor with prio < ceiling;
    // apply cycle-rule walls for free along the way. -1 if none qualifies.
    int popValid(int ceiling = INT_MAX) {
        while (!pq.empty()) {
            auto [p, idx] = pq.top();
            if (p >= ceiling) return -1;  // best remaining is out of class
            pq.pop();
            if (st[idx] != 0 || assigned[idx]) continue;
            auto [a, b] = corridorRooms(idx);
            if (find(a) == find(b)) {
                applyWall(idx);  // same component: must be a wall
                continue;
            }
            return idx;
        }
        return -1;
    }

    void applyResult(const Batch& batch, const std::string& bits) {
        for (size_t j = 0; j < batch.idx.size(); j++) {
            int idx = batch.idx[j];
            assigned[idx] = 0;
            int ch = bits[j / 6] - A64;
            bool open = (ch >> (j % 6)) & 1;
            if (open) applyOpen(idx);
            else applyWall(idx);
        }
    }

    void killWorker(int w) {
        ws[w].dead = true;
        for (auto& b : ws[w].out)
            for (int idx : b.idx)
                if (st[idx] == 0) {
                    assigned[idx] = 0;
                    pq.push({0, idx});  // urgent: it was frontier-ish already
                }
        ws[w].out.clear();
    }

    std::string buildPath() {
        // BFS over open corridors, rooms startRoom -> goalRoom
        std::vector<int> par(m * m, -1);
        std::deque<int> q{startRoom};
        par[startRoom] = startRoom;
        while (!q.empty()) {
            int r = q.front();
            q.pop_front();
            if (r == goalRoom) break;
            int cs[4];
            roomCorridors(r, cs);
            for (int k = 0; k < 4 && cs[k] >= 0; k++) {
                if (st[cs[k]] != 1) continue;
                auto [a, b] = corridorRooms(cs[k]);
                int nxt = (a == r) ? b : a;
                if (par[nxt] == -1) {
                    par[nxt] = r;
                    q.push_back(nxt);
                }
            }
        }
        std::string path;
        int cur = goalRoom;
        while (cur != startRoom) {
            int p = par[cur];
            int ci = cur / m, cj = cur % m, pi = p / m, pj = p % m;
            char mv = (ci > pi) ? 'D' : (ci < pi) ? 'U' : (cj > pj) ? 'R' : 'L';
            path += mv;
            path += mv;
            cur = p;
        }
        std::reverse(path.begin(), path.end());
        return path;
    }

    void coordTick() {
        if (connectedSG) {
            M->claim(buildPath());
            finished = true;
            return;
        }
        // 1. A worker result is due: read it (earliest due first).
        int due = -1;
        long long dueT = LLONG_MAX;
        for (int w = 1; w < K; w++)
            if (!ws[w].dead && !ws[w].out.empty() && ws[w].out.front().resultReady <= T &&
                ws[w].out.front().resultReady < dueT) {
                due = w;
                dueT = ws[w].out.front().resultReady;
            }
        if (due != -1) {
            Msg r = M->recvFrom(due);
            if (r.ok) {
                applyResult(ws[due].out.front(), r.body);
                ws[due].out.pop_front();
                ws[due].misses = 0;
            } else {
#ifdef LOCAL_RUN
                std::cerr << "coord: unexpected miss from worker " << due << " at turn " << T
                          << "\n";
#endif
                if (++ws[due].misses > 3) killWorker(due);
            }
            return;
        }
        // 2. Keep worker pipelines full (2 outstanding batches each).
        if (Bmax >= 1) {
            int pick = -1;
            long long best = LLONG_MAX;
            for (int w = 1; w < K; w++)
                if (!ws[w].dead && (int)ws[w].out.size() < 2 && ws[w].idleFrom < best) {
                    pick = w;
                    best = ws[w].idleFrom;
                }
            if (pick != -1) {
                Batch b;
                std::string payload;
                while ((int)b.idx.size() < Bmax) {
                    int idx = popValid(allowSpec ? INT_MAX : SPEC_BASE);
                    if (idx < 0) break;
                    assigned[idx] = 1;
                    b.idx.push_back(idx);
                    encIdx(payload, idx);
                }
                if (!b.idx.empty()) {
                    long long r = std::max(ws[pick].idleFrom, T + 1);
                    long long s = r + (long long)b.idx.size() + 1;
                    b.resultReady = s + 1;
                    ws[pick].idleFrom = s + 1;
                    ws[pick].out.push_back(std::move(b));
                    M->send(pick, payload);
                    return;
                }
            }
        }
        // 3. Probe the best frontier corridor myself.
        int idx = popValid();
        if (idx >= 0) {
            auto [r, c] = corridorCell(idx);
            if (M->query(r, c)) applyOpen(idx);
            else applyWall(idx);
            return;
        }
        // 4. Nothing to do (results in flight will wake us up).
        M->skip();
    }

    // =========================================================================
    // Worker
    // =========================================================================
    std::vector<int> wIdx;   // active batch corridor indices
    size_t wPos = 0;         // next probe position
    std::string wBits;       // accumulated result chars

    void workerTick() {
        if (wPos < wIdx.size()) {  // probing
            auto [r, c] = corridorCell(wIdx[wPos]);
            bool open = M->query(r, c);
            if (open) wBits[wPos / 6] = char(wBits[wPos / 6] + (1 << (wPos % 6)));
            wPos++;
            return;
        }
        if (!wIdx.empty()) {  // batch done: report
            M->send(0, wBits);
            wIdx.clear();
            wBits.clear();
            wPos = 0;
            return;
        }
        Msg a = M->recvFrom(0);  // idle: wait for an assignment
        if (a.ok) {
            int n = (int)a.body.size() / idxChars;
            wIdx.resize(n);
            for (int j = 0; j < n; j++) wIdx[j] = decIdx(a.body, j * idxChars);
            wBits.assign((n + 5) / 6, A64);
            wPos = 0;
        }
    }
};

// ---------------------------------------------------------------------------
// Prod entry point
// ---------------------------------------------------------------------------

#ifndef LOCAL_RUN
int main() {
    MerlinProd merlin;
    Strategy strategy(&merlin);
    while (!strategy.done()) strategy.tick();
    return 0;
}
#endif