// D. Datacenter Imprisonment — cooperative maze-mapping agents (v3).
//
// Maze structure (from merlin-source/src/maze.rs): N is odd, rooms sit at
// odd (r,c) and are always empty; cells with both coordinates even are always
// walls; the only unknown cells are the 2*m*(m-1) "edge" cells between
// adjacent rooms (m = (N+1)/2). The empty cells form a spanning tree of the
// rooms, so the (1,1)→(N,N) path is unique.
//
// Two strategies, selected by NUM_AGENTS:
//
// 1. Full map (K > 24): static partition of the edge list; workers query
//    their share (with union-find inference: an edge whose rooms are already
//    locally connected must be a wall), pack bits 6-per-char, ship to agent 0
//    which rebuilds the grid, BFS-es, and claims. Max turns ≈ E/K.
//
// 2. Frontier search (K <= 24): grow the open-edge forest from both corners,
//    querying only edges adjacent to discovered rooms — total queries ≈ 0.3E
//    instead of ~0.9E. Leader (agent 0) holds the global forest, a seed pool,
//    and parks idle workers; workers run local best-first exploration
//    (priority = progress toward the opposite corner), donate excess frontier
//    edges, and steal when idle. Leader claims as soon as its union-find
//    connects the corners.

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

static long long N, K, ID, L;
static long long m;

static string ask(const string &cmd) {
    fputs(cmd.c_str(), stdout);
    fputc('\n', stdout);
    fflush(stdout);
    string line;
    if (!getline(cin, line)) exit(0);
    return line;
}

// ---------------------------------------------------------------- full map

static int fullmap() {
    vector<pair<int, int>> edges;
    edges.reserve(2 * m * (m - 1));
    for (long long i = 0; i < m; i++)
        for (long long j = 0; j < m; j++) {
            if (i + 1 < m) edges.push_back({(int)(2 * i + 2), (int)(2 * j + 1)});
            if (j + 1 < m) edges.push_back({(int)(2 * i + 1), (int)(2 * j + 2)});
        }
    const long long E = (long long)edges.size();
    const long long bitsPerMsg = 6 * L;

    const long long W = K - 1;
    long long El = E;
    vector<long long> cnt(K, 0);
    if (W > 0) {
        long long M = (E + bitsPerMsg - 1) / bitsPerMsg;
        long long Ew = 0;
        for (int iter = 0; iter < 4; iter++) {
            Ew = (E + M + K - 1) / K;
            El = E - W * Ew;
            if (El < 0) El = 0;
            long long rest = E - El, base = rest / W, rem = rest % W;
            M = 0;
            for (long long w = 0; w < W; w++) {
                long long c = base + (w < rem ? 1 : 0);
                M += (c + bitsPerMsg - 1) / bitsPerMsg;
            }
        }
        cnt[0] = El;
        long long rest = E - El, base = rest / W, rem = rest % W;
        for (long long w = 0; w < W; w++) cnt[w + 1] = base + (w < rem ? 1 : 0);
    } else {
        cnt[0] = E;
    }
    vector<long long> start(K + 1, 0);
    for (long long a = 0; a < K; a++) start[a + 1] = start[a] + cnt[a];

    vector<int> dsu(m * m);
    iota(dsu.begin(), dsu.end(), 0);
    function<int(int)> find = [&](int x) {
        while (dsu[x] != x) x = dsu[x] = dsu[dsu[x]];
        return x;
    };
    auto edgeRooms = [&](long long i) -> pair<int, int> {
        int r = edges[i].first, c = edges[i].second;
        if (r % 2 == 0) {
            int a = (r / 2 - 1) * (int)m + (c - 1) / 2;
            return {a, a + (int)m};
        }
        int a = ((r - 1) / 2) * (int)m + (c / 2 - 1);
        return {a, a + 1};
    };
    auto probe = [&](long long i) -> int {
        auto [u, v] = edgeRooms(i);
        int ru = find(u), rv = find(v);
        if (ru == rv) return 0; // would form a cycle -> must be wall
        string r = ask("? " + to_string(edges[i].first) + " " + to_string(edges[i].second));
        if (r == "1") {
            dsu[ru] = rv;
            return 1;
        }
        return 0;
    };

    if (ID != 0) {
        long long lo = start[ID], hi = start[ID + 1];
        if (lo >= hi) {
            fputs("halt\n", stdout);
            fflush(stdout);
            return 0;
        }
        string buf;
        int acc = 0, accn = 0;
        auto flushMsg = [&]() {
            if (buf.empty()) return;
            ask("> 0 " + buf);
            buf.clear();
        };
        for (long long i = lo; i < hi; i++) {
            int b = probe(i);
            acc = (acc << 1) | b;
            if (++accn == 6) {
                buf.push_back((char)('0' + acc));
                acc = accn = 0;
                if ((long long)buf.size() == L) flushMsg();
            }
        }
        if (accn > 0) buf.push_back((char)('0' + (acc << (6 - accn))));
        flushMsg();
        fputs("halt\n", stdout);
        fflush(stdout);
        return 0;
    }

    vector<char> bit(E, 0);
    for (long long i = 0; i < El; i++) bit[i] = (char)probe(i);
    vector<long long> nextBit(K, 0);
    long long remaining = 0;
    for (long long a = 1; a < K; a++) {
        nextBit[a] = start[a];
        remaining += (cnt[a] + 5) / 6;
    }
    while (remaining > 0) {
        string r = ask("< ?");
        if (r == "- -") continue;
        size_t sp = r.find(' ');
        long long s = stoll(r.substr(0, sp));
        string body = r.substr(sp + 1);
        for (char ch : body) {
            int v = ch - '0';
            for (int k = 5; k >= 0; k--)
                if (nextBit[s] < start[s + 1]) bit[nextBit[s]++] = (v >> k) & 1;
        }
        remaining -= (long long)body.size();
    }

    long long S = N + 2;
    vector<char> open(S * S, 0);
    for (long long i = 0; i < m; i++)
        for (long long j = 0; j < m; j++) open[(2 * i + 1) * S + (2 * j + 1)] = 1;
    for (long long i = 0; i < E; i++)
        if (bit[i]) open[(long long)edges[i].first * S + edges[i].second] = 1;

    vector<int> par(S * S, -1);
    vector<char> pmove(S * S, 0);
    deque<int> q;
    int startCell = (int)(1 * S + 1), goal = (int)(N * S + N);
    par[startCell] = startCell;
    q.push_back(startCell);
    const int dr[4] = {-1, 1, 0, 0}, dc[4] = {0, 0, -1, 1};
    const char mv[4] = {'U', 'D', 'L', 'R'};
    while (!q.empty()) {
        int cur = q.front();
        q.pop_front();
        if (cur == goal) break;
        int r = cur / (int)S, c = cur % (int)S;
        for (int d = 0; d < 4; d++) {
            int nr = r + dr[d], nc = c + dc[d];
            int nx = nr * (int)S + nc;
            if (nr < 1 || nc < 1 || nr > N || nc > N) continue;
            if (!open[nx] || par[nx] != -1) continue;
            par[nx] = cur;
            pmove[nx] = mv[d];
            q.push_back(nx);
        }
    }
    string path;
    for (int cur = goal; cur != startCell; cur = par[cur]) path.push_back(pmove[cur]);
    reverse(path.begin(), path.end());
    fputs(("! " + path + "\n").c_str(), stdout);
    fflush(stdout);
    return 0;
}

// ---------------------------------------------------------- frontier search

// Record encoding: 4 chars = 3 base-90 digits (room id, chars '!'..'z') + op.
// op: 0..3   open-edge report (dir)             worker -> leader
//     4..11  donation, dir + 4*tag              worker -> leader
//     12     steal request                      worker -> leader
//     13..20 seed dispatch, dir + 4*tag         leader -> worker
// dir: 0=U 1=D 2=L 3=R. tag: 0=A (grown from start), 1=B (from goal).

static const int DR[4] = {-1, 1, 0, 0}, DC[4] = {0, 0, -1, 1};

static void encRoom(string &s, int room) {
    s.push_back((char)(33 + room / 8100));
    s.push_back((char)(33 + room / 90 % 90));
    s.push_back((char)(33 + room % 90));
}
static void encRec(string &s, int room, int op) {
    encRoom(s, room);
    s.push_back((char)(33 + op));
}
static pair<int, int> decRec(const string &s, size_t i) {
    int room = (s[i] - 33) * 8100 + (s[i + 1] - 33) * 90 + (s[i + 2] - 33);
    return {room, s[i + 3] - 33};
}

// Query the edge cell between room and its dir-neighbour. Returns 1 if open.
static int queryEdge(int room, int dir) {
    int i = room / (int)m, j = room % (int)m;
    int r = 2 * i + 1 + DR[dir], c = 2 * j + 1 + DC[dir];
    return ask("? " + to_string(r) + " " + to_string(c)) == "1" ? 1 : 0;
}
static int neighbour(int room, int dir) {
    int i = room / (int)m + DR[dir], j = room % (int)m + DC[dir];
    if (i < 0 || j < 0 || i >= m || j >= m) return -1;
    return i * (int)m + j;
}
// Priority: smaller is better. Tag A wants to maximise i+j, B to minimise.
static int prio(int room, int tag) {
    int s = room / (int)m + room % (int)m;
    return tag == 0 ? (2 * (int)m - 2 - s) : s;
}

struct Seed {
    int room, dir, tag;
};

static int frontierWorker() {
    // Local best-first exploration; tiny frontier kept as a flat vector.
    vector<pair<int, Seed>> heap; // (prio, seed)
    unordered_set<long long> queried;
    // Visited per tag: a room explored by the *other* component must still be
    // probed — the unique A–B meet edge would otherwise be dropped (deadlock).
    unordered_set<int> visited[2];
    string buf;
    int donations = 0;
    const size_t FLUSH = (size_t)max(16LL, min(55LL, K));
    auto edgeKey = [](int room, int dir) -> long long {
        int n0 = neighbour(room, dir);
        return (long long)min(room, n0) * 4 + (dir < 2 ? 0 : 1);
    };
    auto flushMsg = [&](bool steal) {
        if (steal) encRec(buf, 0, 12);
        if (buf.empty()) return;
        ask("> 0 " + buf);
        buf.clear();
        donations = 0;
    };
    auto pushEdge = [&](int room, int dir, int tag) {
        int n0 = neighbour(room, dir);
        if (n0 < 0 || visited[tag].count(n0) || queried.count(edgeKey(room, dir))) return;
        heap.push_back({prio(n0, tag), {room, dir, tag}});
    };

    while (true) {
        // pick the best pending frontier edge, if any
        int best = -1;
        for (size_t i = 0; i < heap.size(); i++) {
            int n0 = neighbour(heap[i].second.room, heap[i].second.dir);
            if (visited[heap[i].second.tag].count(n0) ||
                queried.count(edgeKey(heap[i].second.room, heap[i].second.dir))) {
                heap[i] = heap.back();
                heap.pop_back();
                i--;
                continue;
            }
            if (best < 0 || heap[i].first < heap[best].first) best = (int)i;
        }
        if (best < 0) {
            flushMsg(true);
            // poll for seeds
            while (true) {
                string r = ask("< 0");
                if (r == "- -") continue;
                size_t sp = r.find(' ');
                string body = r.substr(sp + 1);
                for (size_t i = 0; i + 3 < body.size(); i += 4) {
                    auto [room, op] = decRec(body, i);
                    if (op >= 13 && op <= 20) {
                        int v = op - 13;
                        pushEdge(room, v & 3, v >> 2);
                    }
                }
                break;
            }
            continue;
        }
        Seed sd = heap[best].second;
        heap[best] = heap.back();
        heap.pop_back();
        queried.insert(edgeKey(sd.room, sd.dir));
        int n0 = neighbour(sd.room, sd.dir);
        if (queryEdge(sd.room, sd.dir)) {
            encRec(buf, sd.room, sd.dir); // open report
            if (!visited[sd.tag].count(n0)) {
                visited[sd.tag].insert(n0);
                for (int d = 0; d < 4; d++) {
                    if (neighbour(n0, d) == sd.room) continue;
                    pushEdge(n0, d, sd.tag);
                }
            }
        }
        // donate worst edges beyond capacity (deeper local heaps pay off
        // when there are few workers to share with)
        const size_t CAP = (size_t)max(16LL, 128 / K);
        while (heap.size() > CAP) {
            int worst = 0;
            for (size_t i = 1; i < heap.size(); i++)
                if (heap[i].first > heap[worst].first) worst = (int)i;
            Seed w = heap[worst].second;
            heap[worst] = heap.back();
            heap.pop_back();
            encRec(buf, w.room, 4 + w.dir + 4 * w.tag);
            donations++;
        }
        if (buf.size() / 4 >= FLUSH || donations >= 4) flushMsg(false);
    }
}

static int frontierLeader() {
    const int startRoom = 0, goalRoom = (int)(m * m - 1);
    vector<int> dsu(m * m);
    iota(dsu.begin(), dsu.end(), 0);
    function<int(int)> find = [&](int x) {
        while (dsu[x] != x) x = dsu[x] = dsu[dsu[x]];
        return x;
    };
    vector<array<char, 4>> openAdj(m * m, {0, 0, 0, 0});
    unordered_map<int, char> tagOf; // first tag a room was reached under
    tagOf[startRoom] = 0;
    tagOf[goalRoom] = 1;
    // pool of seeds, ordered by priority
    multimap<int, Seed> pool;
    deque<int> parked;
    // A seed is stale only if its target is already in the *same* component;
    // a target in the other component is the meet candidate and must be kept.
    auto stale = [&](int n0, int tag) {
        auto it = tagOf.find(n0);
        return it != tagOf.end() && it->second == (char)tag;
    };
    // No dedupe: a dispatched seed may be re-donated by its recipient and
    // must re-enter the pool (dropping it can strand the only frontier edge).
    // Duplicates just cost the odd wasted query.
    auto poolPush = [&](int room, int dir, int tag) {
        int n0 = neighbour(room, dir);
        if (n0 < 0 || stale(n0, tag)) return;
        pool.insert({prio(n0, tag), {room, dir, tag}});
    };
    auto claim = [&]() {
        // BFS over open adjacency from startRoom
        vector<int> par(m * m, -1), pdir(m * m, -1);
        deque<int> q;
        par[startRoom] = startRoom;
        q.push_back(startRoom);
        while (!q.empty()) {
            int cur = q.front();
            q.pop_front();
            if (cur == goalRoom) break;
            for (int d = 0; d < 4; d++) {
                if (!openAdj[cur][d]) continue;
                int n0 = neighbour(cur, d);
                if (n0 < 0 || par[n0] != -1) continue;
                par[n0] = cur;
                pdir[n0] = d;
                q.push_back(n0);
            }
        }
        const char mv[4] = {'U', 'D', 'L', 'R'};
        string path;
        for (int cur = goalRoom; cur != startRoom; cur = par[cur]) {
            path.push_back(mv[pdir[cur]]);
            path.push_back(mv[pdir[cur]]);
        }
        reverse(path.begin(), path.end());
        fputs(("! " + path + "\n").c_str(), stdout);
        fflush(stdout);
        exit(0);
    };
    // Add a known-open edge; claims and exits if corners become connected.
    auto addOpen = [&](int room, int dir, int tag) {
        int n0 = neighbour(room, dir);
        if (n0 < 0) return;
        openAdj[room][dir] = 1;
        for (int d = 0; d < 4; d++)
            if (neighbour(n0, d) == room) openAdj[n0][d] = 1;
        int ra = find(room), rb = find(n0);
        if (ra != rb) dsu[ra] = rb;
        if (!tagOf.count(n0)) tagOf[n0] = (char)tag;
        if (find(startRoom) == find(goalRoom)) claim();
    };

    poolPush(startRoom, 1, 0);
    poolPush(startRoom, 3, 0);
    poolPush(goalRoom, 0, 1);
    poolPush(goalRoom, 2, 1);

    bool recvBias = true;
    while (true) {
        if (!parked.empty() && !pool.empty()) {
            // dispatch up to 12 best still-valid seeds to one parked worker
            int w = parked.front();
            parked.pop_front();
            string msg;
            int t = 0;
            while (t < 12 && !pool.empty()) {
                auto it = pool.begin();
                Seed sd = it->second;
                pool.erase(it);
                int n0 = neighbour(sd.room, sd.dir);
                if (n0 < 0 || stale(n0, sd.tag)) continue;
                encRec(msg, sd.room, 13 + sd.dir + 4 * sd.tag);
                t++;
            }
            if (msg.empty()) {
                parked.push_back(w);
                continue; // pool exhausted by stale seeds; fall through next loop
            }
            ask("> " + to_string(w) + " " + msg);
            continue;
        }
        bool doRecv = recvBias || pool.empty();
        if (K == 1) doRecv = false;
        if (doRecv) {
            string r = ask("< ?");
            if (r == "- -") {
                recvBias = false;
                continue;
            }
            recvBias = true;
            size_t sp = r.find(' ');
            int s = (int)stoll(r.substr(0, sp));
            string body = r.substr(sp + 1);
            for (size_t i = 0; i + 3 < body.size(); i += 4) {
                auto [room, op] = decRec(body, i);
                if (op <= 3) {
                    int tag = tagOf.count(room) ? tagOf[room] : 0;
                    addOpen(room, op, tag);
                } else if (op <= 11) {
                    int v = op - 4;
                    poolPush(room, v & 3, v >> 2);
                } else if (op == 12) {
                    parked.push_back(s);
                }
            }
            continue;
        }
        // walk: query the best pool seed ourselves
        auto it = pool.begin();
        Seed sd = it->second;
        pool.erase(it);
        int n0 = neighbour(sd.room, sd.dir);
        if (n0 < 0 || stale(n0, sd.tag)) continue;
        if (queryEdge(sd.room, sd.dir)) {
            addOpen(sd.room, sd.dir, sd.tag);
            for (int d = 0; d < 4; d++) {
                if (neighbour(n0, d) == sd.room) continue;
                poolPush(n0, d, sd.tag);
            }
        }
        recvBias = (K > 1);
    }
}

int main() {
    if (!(cin >> N >> K >> ID >> L)) return 0;
    cin.ignore(numeric_limits<streamsize>::max(), '\n');
    m = (N + 1) / 2;

    if (N == 1) {
        fputs(ID == 0 ? "!\n" : "halt\n", stdout);
        fflush(stdout);
        return 0;
    }
    if (K > 24) return fullmap();
    return ID == 0 ? frontierLeader() : frontierWorker();
}