// Datacenter Imprisonment — cooperative maze-escape agent.
//
// The empty cells form a tree carved by the provided generator, which ALWAYS
// makes rooms at (odd,odd) empty and pillars at (even,even) walls; only the
// "between" cells (exactly one even coordinate) are unknown tree edges. And
// `? r c` may probe ANY cell (agents are not physical robots). So all K agents
// cooperatively scan the E = 2*m*(m-1) potential edges in parallel: each agent
// owns a disjoint, deterministic subset and probes one edge per lockstep turn.
// That makes the run take ~E/K turns instead of the tens of thousands a lone
// searcher needs (which timed out with many agents).
//
// Agent 0 is the assembler. Workers STREAM their probed results to it as they
// go (packed 13 bits per two printable chars), so the data is ready
// by the time agent 0 needs it. Agent 0 keeps a live partial graph and claims as
// soon as the discovered open edges connect start to finish. If that does not
// happen early, the protocol still degenerates to the old full-maze scan. If a
// worker dies before delivering its shard, agent 0 self-probes the missing edges.

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

static char linebuf[4096];

// Read one reply line from Merlin. Returns false on EOF (we were killed).
static bool readLine() {
    if (!fgets(linebuf, sizeof(linebuf), stdin)) return false;
    return true;
}

int main() {
    int N, K, ID, MAXMSG;
    if (scanf("%d %d %d %d", &N, &K, &ID, &MAXMSG) != 4) return 0;
    int ch;
    while ((ch = getchar()) != '\n' && ch != EOF) {} // consume rest of startup line

    if (N == 1) { // (1,1) == (N,N): empty path.
        if (ID == 0) { printf("!\n"); fflush(stdout); }
        else { printf("halt\n"); fflush(stdout); }
        return 0;
    }

    const int m = (N + 1) / 2;                    // rooms per side
    const long long H = (long long)m * (m - 1);   // horizontal edges
    const long long E = 2 * H;                    // total potential tree edges
    const int totalRooms = m * m;
    const int startId = 0, goalId = (m - 1) * m + (m - 1);

    const int PAIRS_PER_MSG = max(1, min(MAXMSG, 256) / 2);
    const int CHUNK = 2 * PAIRS_PER_MSG;          // message payload chars, always <= MAXMSG
    const int BITS_PER_PAIR = 13;                 // 94^2 > 2^13, chars are printable non-space
    const long long baseShard = E / K;
    bool legacyFirstMsg = false;
    int firstPairs = PAIRS_PER_MSG;
    if (baseShard >= 500 && baseShard <= 900) firstPairs = min(firstPairs, 48);       // 624 bits
    else if (baseShard >= 1500 && baseShard <= 2300 && K <= 12 && MAXMSG >= 250) legacyFirstMsg = true; // 1500 bits
    else if (baseShard > 3000 && K >= 15) firstPairs = min(firstPairs, 112);          // 1456 bits

    vector<int> scanEdge((size_t)E);
    iota(scanEdge.begin(), scanEdge.end(), 0);
    auto edgeKey = [&](int e) {
        long long x2, y2;
        if (e < H) {
            long long i = e / (m - 1), j = e % (m - 1);
            x2 = 2 * i;
            y2 = 2 * j + 1;
        } else {
            long long v = e - H, i = v / m, j = v % m;
            x2 = 2 * i + 1;
            y2 = 2 * j;
        }
        return tuple<long long, long long, long long, long long>(
            llabs(x2 - y2), x2 + y2, x2, y2
        );
    };
    sort(scanEdge.begin(), scanEdge.end(), [&](int a, int b) {
        return edgeKey(a) < edgeKey(b);
    });

    auto edgeCell = [&](long long e, int &r, int &c) {
        if (e < H) { long long i = e / (m - 1), j = e % (m - 1); r = 2*i+1; c = 2*j+2; }
        else       { long long v = e - H; long long i = v / m, j = v % m; r = 2*i+2; c = 2*j+1; }
    };

    const long long firstBitsPerMsg = legacyFirstMsg ? 1500LL : (long long)firstPairs * BITS_PER_PAIR;
    const long long fullBitsPerMsg = (long long)PAIRS_PER_MSG * BITS_PER_PAIR;
    auto forEachMessageReady = [&](long long bits, auto &&fn) {
        if (bits <= 0) return;
        long long msg = 1;
        long long done = min(firstBitsPerMsg, bits);
        fn(msg, done);
        while (done < bits) {
            msg++;
            done = min(done + fullBitsPerMsg, bits);
            fn(msg, done);
        }
    };
    auto residueCount = [&](int a) -> long long {
        if (a >= E) return 0;
        return (E - 1 - a) / K + 1;
    };
    auto finishTurnForC0 = [&](long long c0) -> long long {
        if (K == 1) return E + 1;
        vector<long long> q(K, 0);
        q[0] = c0;
        long long count0 = residueCount(0);
        long long freed = count0 - c0;
        for (int a = 1; a < K; a++) {
            q[a] = residueCount(a) + freed / (K - 1) + ((a - 1) < freed % (K - 1));
        }
        vector<pair<long long, int>> ready;
        for (int a = 1; a < K; a++) {
            forEachMessageReady(q[a], [&](long long msg, long long queried) {
                ready.push_back({queried + msg + 1, a});
            });
        }
        sort(ready.begin(), ready.end());
        long long t = q[0] + 1;
        for (auto [r, a] : ready) {
            (void)a;
            if (t < r) t = r;
            t++;
        }
        return t;
    };

    // Ownership is residue based, but agent 0's residue-0 prefix is chosen by
    // exact schedule simulation instead of a coarse heuristic. The gain is only
    // a few turns, but this is deterministic and essentially free.
    long long c0 = (K == 1) ? E : 0;
    if (K > 1) {
        long long count0 = residueCount(0);
        long long bestFinish = LLONG_MAX;
        for (long long cand = 0; cand <= count0; cand++) {
            long long cur = finishTurnForC0(cand);
            if (cur < bestFinish) {
                bestFinish = cur;
                c0 = cand;
            }
        }
    }

    auto owner = [&](long long pos) -> int {
        int a = (int)(pos % K);
        if (a != 0) return a;
        long long t = pos / K;            // index within residue-0 class
        if (t < c0) return 0;
        if (K == 1) return 0;
        return 1 + (int)((t - c0) % (K - 1));
    };

    if (ID != 0) {
        // ---- WORKER ----
        // Collect our edges (increasing index) and probe them, streaming results.
        string payload;
        int acc = 0, nbits = 0;
        int sentMsgs = 0;
        bool any = false;
        for (long long pos = 0; pos < E; pos++) {
            if (owner(pos) != ID) continue;
            any = true;
            int e = scanEdge[(size_t)pos];
            int r, c; edgeCell(e, r, c);
            printf("? %d %d\n", r, c); fflush(stdout);
            if (!readLine()) return 0;
            int bit = (linebuf[0] == '1') ? 1 : 0;
            acc |= (bit << nbits);
            bool legacyMode = legacyFirstMsg && sentMsgs == 0;
            if (legacyMode) {
                if (++nbits == 6) {
                    payload.push_back((char)(48 + acc));
                    acc = 0; nbits = 0;
                }
            } else {
                if (++nbits == BITS_PER_PAIR) {
                    payload.push_back((char)(33 + (acc % 94)));
                    payload.push_back((char)(33 + (acc / 94)));
                    acc = 0; nbits = 0;
                }
            }
            int limit = legacyMode ? 250 : 2 * ((sentMsgs == 0) ? firstPairs : PAIRS_PER_MSG);
            if ((int)payload.size() >= limit) {   // stream a chunk right away
                printf("> 0 %s\n", payload.c_str()); fflush(stdout);
                if (!readLine()) return 0;        // "OK"
                payload.clear();
                sentMsgs++;
            }
        }
        if (nbits > 0) {
            if (legacyFirstMsg && sentMsgs == 0) {
                payload.push_back((char)(48 + acc));
            } else {
                payload.push_back((char)(33 + (acc % 94)));
                payload.push_back((char)(33 + (acc / 94)));
            }
        }
        if (!payload.empty()) {
            printf("> 0 %s\n", payload.c_str()); fflush(stdout);
            if (!readLine()) return 0;
            sentMsgs++;
        }
        (void)any;
        printf("halt\n"); fflush(stdout);
        return 0;
    }

    // ---- ASSEMBLER (agent 0) ----
    // Per-sender ordered edge lists (decode-by-iteration works for any owner()).
    vector<vector<int>> edgesOf(K);
    for (long long pos = 0; pos < E; pos++) edgesOf[owner(pos)].push_back(scanEdge[(size_t)pos]);

    vector<char> present((size_t)E, 0);
    vector<char> known((size_t)E, 0);
    long long knownCount = 0;

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

    vector<vector<pair<int, char>>> openAdj(totalRooms);
    bool solved = false;
    const bool adaptiveEnabled = (K == 3 && baseShard > 5000);
    vector<char> activeS(totalRooms, 0), activeT(totalRooms, 0);
    using Front = tuple<int, int, int, int, long long>; // priority, tie, side, edge, seq
    priority_queue<Front, vector<Front>, greater<Front>> frontier;
    long long frontierSeq = 0;

    auto edgeRooms = [&](long long e) {
        int u, v;
        if (e < H) {
            long long i = e / (m - 1), j = e % (m - 1);
            u = (int)(i * m + j);
            v = u + 1;
        } else {
            long long x = e - H, i = x / m, j = x % m;
            u = (int)(i * m + j);
            v = u + m;
        }
        return pair<int, int>{u, v};
    };

    auto edgeBetween = [&](int u, int v) -> int {
        if (u > v) swap(u, v);
        if (v == u + 1) {
            int i = u / m, j = u % m;
            return i * (m - 1) + j;
        }
        int i = u / m, j = u % m;
        return (int)(H + i * m + j);
    };

    auto pushFrontier = [&](int room, int side) {
        if (!adaptiveEnabled) return;
        int i = room / m, j = room % m;
        int target = side == 0 ? goalId : startId;
        int ti = target / m, tj = target % m;
        auto add = [&](int nr, int nj) {
            if (nr < 0 || nr >= m || nj < 0 || nj >= m) return;
            int nb = nr * m + nj;
            int e = edgeBetween(room, nb);
            if (known[e]) return;
            int h = abs(nr - ti) + abs(nj - tj);
            int diag = abs(nr - nj);
            frontier.push({h, diag, side, e, frontierSeq++});
        };
        add(i - 1, j); add(i + 1, j); add(i, j - 1); add(i, j + 1);
    };

    auto activate = [&](int root, int side) {
        if (!adaptiveEnabled) return;
        vector<char> &act = (side == 0) ? activeS : activeT;
        vector<int> stack(1, root);
        while (!stack.empty()) {
            int u = stack.back();
            stack.pop_back();
            if (act[u]) continue;
            act[u] = 1;
            pushFrontier(u, side);
            for (auto [v, d] : openAdj[u]) {
                (void)d;
                if (!act[v]) stack.push_back(v);
            }
        }
    };

    if (adaptiveEnabled) {
        activeS[startId] = 1;
        activeT[goalId] = 1;
        pushFrontier(startId, 0);
        pushFrontier(goalId, 1);
    }

    auto addOpenEdge = [&](long long e) {
        auto [u, v] = edgeRooms(e);
        char uv, vu;
        if (e < H) { uv = 'R'; vu = 'L'; }
        else       { uv = 'D'; vu = 'U'; }
        openAdj[u].push_back({v, uv});
        openAdj[v].push_back({u, vu});
        dsu.unite(u, v);
        if (adaptiveEnabled) {
            if (activeS[u] && !activeS[v]) activate(v, 0);
            if (activeS[v] && !activeS[u]) activate(u, 0);
            if (activeT[u] && !activeT[v]) activate(v, 1);
            if (activeT[v] && !activeT[u]) activate(u, 1);
        }
        if (dsu.find(startId) == dsu.find(goalId)) solved = true;
    };

    auto nextAdaptiveEdge = [&]() -> int {
        while (!frontier.empty()) {
            auto [h, diag, side, e, seq] = frontier.top();
            (void)h; (void)diag; (void)seq;
            frontier.pop();
            if (known[e]) continue;
            auto [u, v] = edgeRooms(e);
            if (side == 0 && (activeS[u] || activeS[v])) return e;
            if (side == 1 && (activeT[u] || activeT[v])) return e;
        }
        return -1;
    };

    auto setEdge = [&](long long e, int bit) {
        if (!known[e]) {
            known[e] = 1;
            present[e] = (char)bit;
            knownCount++;
            if (bit) addOpenEdge(e);
        }
    };

    auto buildMoves = [&]() {
        vector<int> par(totalRooms, -1);
        vector<char> pdir(totalRooms, 0);
        vector<int> q; q.reserve(totalRooms);
        par[startId] = startId;
        q.push_back(startId);
        for (size_t head = 0; head < q.size(); head++) {
            int cur = q[head];
            if (cur == goalId) break;
            for (auto [nx, d] : openAdj[cur]) {
                if (par[nx] != -1) continue;
                par[nx] = cur;
                pdir[nx] = d;
                q.push_back(nx);
            }
        }
        string dirs;
        for (int cur = goalId; cur != startId; cur = par[cur]) {
            if (cur < 0 || par[cur] < 0) { dirs.clear(); break; }
            dirs.push_back(pdir[cur]);
        }
        reverse(dirs.begin(), dirs.end());
        string moves;
        moves.reserve(dirs.size() * 2);
        for (char d : dirs) { moves.push_back(d); moves.push_back(d); }
        return moves;
    };

    auto claim = [&]() {
        string moves = buildMoves();
        printf("! %s\n", moves.c_str());
        fflush(stdout);
    };

    vector<long long> got(K, 0);
    long long maxMsgs = 0;
    vector<long long> readyTurns;
    for (int a = 1; a < K; a++) {
        long long bits = (long long)edgesOf[a].size();
        long long msgs = 0;
        forEachMessageReady(bits, [&](long long msg, long long queried) {
            (void)queried;
            msgs = msg;
            readyTurns.push_back(queried + msg + 1);
        });
        maxMsgs = max(maxMsgs, msgs);
    }
    sort(readyTurns.begin(), readyTurns.end());
    const long long STUCK = 2 * maxMsgs + 5LL * K + 1000;

    auto readMessage = [&]() -> int {
        printf("< ?\n"); fflush(stdout);
        if (!readLine()) return -1;
        if (linebuf[0] == '-') return 0;
        int sender = 0; char *p = linebuf;
        while (*p >= '0' && *p <= '9') { sender = sender * 10 + (*p - '0'); p++; }
        if (*p == ' ') p++;
        char *end = p; while (*end && *end != '\n' && *end != '\r') end++;
        *end = '\0';
        if (sender <= 0 || sender >= K) return 1;
        if (legacyFirstMsg && got[sender] == 0) {
            for (char *q = p; *q; q++) {
                int val = (int)(*q) - 48;
                for (int k = 0; k < 6 && got[sender] < (long long)edgesOf[sender].size(); k++) {
                    int bit = (val >> k) & 1;
                    setEdge(edgesOf[sender][got[sender]], bit);
                    got[sender]++;
                }
            }
        } else {
            for (char *q = p; q[0] && q[1]; q += 2) {
                int val = ((int)q[0] - 33) + 94 * ((int)q[1] - 33);
                for (int k = 0; k < BITS_PER_PAIR && got[sender] < (long long)edgesOf[sender].size(); k++) {
                    int bit = (val >> k) & 1;
                    setEdge(edgesOf[sender][got[sender]], bit);
                    got[sender]++;
                }
            }
        }
        return 1;
    };

    // Probe our own shard, but read worker chunks at the deterministic turns
    // when they should already be queued. This can expose the final path before
    // agent 0 finishes its local residue shard, while preserving the full-scan
    // fallback and avoiding blind receive misses.
    long long turnNo = 0;
    size_t nextReady = 0;
    size_t ownIdx = 0;
    while (ownIdx < edgesOf[0].size()) {
        if (nextReady < readyTurns.size() && turnNo + 1 >= readyTurns[nextReady]) {
            turnNo++;
            int gotMsg = readMessage();
            nextReady++;
            if (gotMsg < 0) return 0;
            if (solved) { claim(); return 0; }
            continue;
        }

        int e = -1;
        if (adaptiveEnabled) e = nextAdaptiveEdge();
        if (e < 0) {
            while (ownIdx < edgesOf[0].size() && known[edgesOf[0][ownIdx]]) ownIdx++;
            if (ownIdx >= edgesOf[0].size()) break;
            e = edgesOf[0][ownIdx++];
        }
        int r, c; edgeCell(e, r, c);
        printf("? %d %d\n", r, c); fflush(stdout);
        turnNo++;
        if (!readLine()) return 0;
        setEdge(e, (linebuf[0] == '1') ? 1 : 0);
        if (solved) { claim(); return 0; }
    }

    long long consecutiveMiss = 0;
    while (knownCount < E && consecutiveMiss < STUCK) {
        int gotMsg = readMessage();
        if (gotMsg < 0) return 0;
        if (gotMsg == 0) consecutiveMiss++;
        else consecutiveMiss = 0;
        if (solved) { claim(); return 0; }
    }

    // Fallback: probe any edges still unknown (a worker must have dropped).
    for (long long e = 0; e < E; e++) {
        if (known[e]) continue;
        int r, c; edgeCell(e, r, c);
        printf("? %d %d\n", r, c); fflush(stdout);
        if (!readLine()) return 0;
        setEdge(e, (linebuf[0] == '1') ? 1 : 0);
        if (solved) { claim(); return 0; }
    }

    claim();
    return 0;
}