// agent_v6 — dispatcher: cooperative SHARED-DSU racing for small A (<=5),
// cooperative diagonal EARLY-STOP mapper for larger A (>=6).
//
// vs v5 this adds coop_dfs for A in [3,5]: instead of a pure zero-message race
// (min over A independent DFS), every agent runs a DISTINCT target-biased DFS and
// streams its discovered OPEN edges to agent 0, which unions its own + all received
// opens into ONE shared DSU and claims the instant s-t connect. The UNION of A
// diverse searches spans s-t in ~0.11*2T/agent vs ~0.16*2T for the best single
// search, and at small A the coordinator funnel is tiny -> measured 1.15-1.8x
// faster than v5's race/diag on real merlin (51..501, A=3..5). Any agent whose own
// DFS reaches the goal still claims directly, so a death (incl. agent 0) never
// blocks a claim (verified: kill agent 0 -> a worker claims).
//
// Key idea (measured to beat full-map v2 across the real round distribution):
// full-map v2 probes all ~2T candidate passages (2T/A per agent). But we only need
// enough OPEN edges for the coordinator to see s=(0,0) connected to t=(m-1,m-1); it
// can then claim immediately. If every agent probes candidate passages in a shared
// DIAGONAL-FIRST order (by |i-j| of the edge's room), the s->t path is spanned after
// only X ~= 0.66-0.77 T open edges, so work ~ 2X/A << 2T/A. The coordinator claims
// the instant s and t union together, over the *real* discovered edges (a subforest
// of the maze tree -> the unique path).
//
//   * small A (<= SMALL_A):  v3 speculative — every agent races a distinct target-
//     biased DFS, fastest claims, zero messages, death-tolerant. (Best at small A.)
//   * larger A: cooperative early-stop. Agent 0 = coordinator (assembles + claims);
//     agents 1..A-1 = workers. Every agent owns the sorted-edge positions p with
//     p % A == id and probes them in diagonal-first order. Workers stream discovered
//     OPEN edges to the coordinator in packed messages; the coordinator also probes
//     its own share whenever its inbox is momentarily empty, unions every open edge
//     into a DSU, and claims as soon as find(s)==find(t). If workers die/stall it
//     falls back to probing all remaining edges itself, so it never fails to claim.
//
// Room model (merlin maze.rs): rooms at (2i+1,2j+1) always empty; only passage cells
// unknown. down edge idx--(idx+m) probes cell (2i+2,2j+1); right edge idx--(idx+1)
// probes (2i+1,2j+2). Each room step doubles into two ULDR moves.
#include <bits/stdc++.h>
using namespace std;

int N, NUM_AGENTS, AGENT_ID, MAX_MSG_LEN, m;
long long T;

static string readLine() {
    string s; int c;
    while ((c = getchar()) != EOF && c != '\n') s.push_back((char)c);
    if (c == EOF && s.empty()) exit(0);
    return s;
}
static inline bool ask(int r, int c) {
    printf("? %d %d\n", r, c); fflush(stdout);
    return readLine() == "1";
}
static inline void sendMsg(int dst, const string &body) {
    printf("> %d %s\n", dst, body.c_str()); fflush(stdout);
    readLine();  // "OK"
}
static inline bool recvAny(int &sender, string &body) {
    printf("< ?\n"); fflush(stdout);
    string r = readLine();
    if (r == "- -") return false;
    size_t sp = r.find(' ');
    sender = atoi(r.c_str());
    body = (sp == string::npos) ? "" : r.substr(sp + 1);
    return true;
}

// ---- dir tables: 0=Down(i+1) 1=Right(j+1) 2=Up(i-1) 3=Left(j-1) ----
static const int DI[4] = {1, 0, -1, 0};
static const int DJ[4] = {0, 1, 0, -1};
static const char DC[4] = {'D', 'R', 'U', 'L'};

// ============ v3 speculative DFS (small A) — adopted from agent.cpp ============
// kind 0 = fixed priority `prio`; kind 1/2 = ADAPTIVE, ordering the two toward-goal
// dirs first (longer / shorter remaining axis first), then the two away dirs.
static string dfs(int si, int sj, int gi, int gj, int kind, const int prio[4]) {
    vector<vector<char>> vis(m, vector<char>(m, 0));
    struct Frame { int i, j, next; };
    vector<Frame> st; string moves;
    vis[si][sj] = 1; st.push_back({si, sj, 0});
    int order[4];
    while (!st.empty()) {
        Frame &f = st.back();
        if (f.i == gi && f.j == gj) break;
        if (f.next == 4) { st.pop_back(); if (!moves.empty()) moves.pop_back(); continue; }
        if (kind == 0) { for (int t = 0; t < 4; ++t) order[t] = prio[t]; }
        else {
            int vdir = (gi > f.i) ? 0 : 2;
            int hdir = (gj > f.j) ? 1 : 3;
            int av = (vdir == 0) ? 2 : 0, ah = (hdir == 1) ? 3 : 1;
            bool longV = (abs(gi - f.i) >= abs(gj - f.j));
            if (kind == 2) longV = !longV;
            if (longV) { order[0] = vdir; order[1] = hdir; order[2] = av; order[3] = ah; }
            else       { order[0] = hdir; order[1] = vdir; order[2] = ah; order[3] = av; }
        }
        int d = order[f.next++];
        int ni = f.i + DI[d], nj = f.j + DJ[d];
        if (ni < 0 || ni >= m || nj < 0 || nj >= m || vis[ni][nj]) continue;
        int pr = (2 * f.i + 1) + DI[d], pc = (2 * f.j + 1) + DJ[d];
        if (!ask(pr, pc)) continue;
        vis[ni][nj] = 1; moves.push_back(DC[d]); st.push_back({ni, nj, 0});
    }
    return moves;
}
static void run_v3() {
    struct Strat { bool back; int kind; int prio[4]; };
    static const Strat V[8] = {
        {false, 1, {0,0,0,0}}, {true, 1, {0,0,0,0}}, {false, 2, {0,0,0,0}},
        {true, 0, {3,2,0,1}},  {false, 0, {1,0,2,3}}, {false, 0, {0,1,2,3}},
        {true, 0, {2,3,0,1}},  {false, 0, {0,1,3,2}},
    };
    const Strat &s = V[AGENT_ID % 8];
    int si = s.back ? m - 1 : 0, sj = si, gi = s.back ? 0 : m - 1, gj = gi;
    string rmoves = dfs(si, sj, gi, gj, s.kind, s.prio);
    string path; path.reserve(rmoves.size() * 2);
    if (!s.back) {
        for (char c : rmoves) { path.push_back(c); path.push_back(c); }
    } else {
        for (int k = (int)rmoves.size() - 1; k >= 0; --k) {
            char c = rmoves[k];
            char iv = (c=='D')?'U':(c=='U')?'D':(c=='R')?'L':'R';
            path.push_back(iv); path.push_back(iv);
        }
    }
    printf("! %s\n", path.c_str()); fflush(stdout);
}

// ================= cooperative early-stop (larger A) =================
// sorted candidate edges, diagonal-first. edge code = room*2 + dir (dir 0=down,1=right)
static vector<int> g_edges;   // codes, sorted by (|i-j|, room, dir)
static void build_edges() {
    g_edges.reserve(2 * T);
    for (int i = 0; i < m; ++i)
        for (int j = 0; j < m; ++j) {
            int room = i * m + j;
            if (i + 1 < m) g_edges.push_back(room * 2 + 0);
            if (j + 1 < m) g_edges.push_back(room * 2 + 1);
        }
    stable_sort(g_edges.begin(), g_edges.end(), [](int a, int b) {
        int ra = a >> 1, rb = b >> 1;
        int ka = abs(ra / m - ra % m), kb = abs(rb / m - rb % m);
        if (ka != kb) return ka < kb;
        return a < b;
    });
}

// DSU
static vector<int> ufp;
static int uf(int x) { while (ufp[x] != x) { ufp[x] = ufp[ufp[x]]; x = ufp[x]; } return x; }
static inline bool un(int a, int b) { a = uf(a); b = uf(b); if (a == b) return false; ufp[a] = b; return true; }

static vector<uint8_t> openDown, openRight;   // coordinator's known-open edges
static inline void mark_open(int code) {
    int room = code >> 1, dir = code & 1;
    if (dir == 0) { openDown[room] = 1; un(room, room + m); }
    else          { openRight[room] = 1; un(room, room + 1); }
}
static inline bool probe_edge(int code) {      // probe one candidate; return open
    int room = code >> 1, dir = code & 1, i = room / m, j = room % m;
    int pr = (2 * i + 1) + DI[dir], pc = (2 * j + 1) + DJ[dir];
    bool op = ask(pr, pc);
    if (op) mark_open(code);
    return op;
}
static void claim_from_open() {
    // BFS s->t over known-open edges (a forest) -> unique path -> claim.
    vector<int> par(T, -1); vector<char> pmove(T, 0); vector<uint8_t> seen(T, 0);
    vector<int> q; q.reserve(T); q.push_back(0); seen[0] = 1;
    for (size_t h = 0; h < q.size(); ++h) {
        int idx = q[h];
        if (idx == (int)T - 1) break;
        int i = idx / m, j = idx % m;
        // Down/Up/Right/Left using open arrays
        if (i + 1 < m && openDown[idx] && !seen[idx + m])      { seen[idx+m]=1; par[idx+m]=idx; pmove[idx+m]='D'; q.push_back(idx+m); }
        if (i - 1 >= 0 && openDown[idx - m] && !seen[idx - m]) { seen[idx-m]=1; par[idx-m]=idx; pmove[idx-m]='U'; q.push_back(idx-m); }
        if (j + 1 < m && openRight[idx] && !seen[idx + 1])     { seen[idx+1]=1; par[idx+1]=idx; pmove[idx+1]='R'; q.push_back(idx+1); }
        if (j - 1 >= 0 && openRight[idx - 1] && !seen[idx - 1]){ seen[idx-1]=1; par[idx-1]=idx; pmove[idx-1]='L'; q.push_back(idx-1); }
    }
    string rmoves;
    for (int cur = (int)T - 1; cur != 0 && par[cur] != -1; cur = par[cur]) rmoves.push_back(pmove[cur]);
    reverse(rmoves.begin(), rmoves.end());
    string path; path.reserve(rmoves.size() * 2);
    for (char c : rmoves) { path.push_back(c); path.push_back(c); }
    printf("! %s\n", path.c_str()); fflush(stdout);
}

static void run_worker() {
    // A-1 workers (id 1..A-1) partition ALL edges; worker w=id-1 owns sorted
    // positions p with p % (A-1) == w, probed diagonal-first, streaming opens.
    const int W = NUM_AGENTS - 1, w = AGENT_ID - 1;
    int CAP = max(8, min(36, (MAX_MSG_LEN - 4) / 7));  // edges per message
    // Adaptive flush. The connecting open sits buffered ~2*CAP turns in its
    // worker before the batch flushes — a fixed cost that dominates the score
    // when ideal turns are few (large A, small/mid N). Shrink CAP toward the
    // coordinator keep-up floor (~0.5*(A-1) msgs/turn) so it flushes sooner.
    // Only when A is large enough that the floor stays safe AND est turns are
    // small; else keep 36 (at large N buffering is negligible and a big CAP
    // avoids coordinator message backlog). Measured on real merlin: +4-7% at
    // A>=20 with N<=~200, 0% (no regression) elsewhere.
    {
        long est = (long)m * m * 13 / (10 * W);   // ~1.3*m^2/(A-1) ~= ideal turns
        if (est < 2500 && W >= 10)
            CAP = max(8, min(CAP, (int)(0.7 * W + 0.5)));
    }
    string buf; int cnt = 0;
    size_t P = g_edges.size();
    for (size_t p = w; p < P; p += W) {
        int code = g_edges[p];
        int room = code >> 1, dir = code & 1, i = room / m, j = room % m;
        int pr = (2 * i + 1) + DI[dir], pc = (2 * j + 1) + DJ[dir];
        if (ask(pr, pc)) {
            if (cnt) buf.push_back(' ');
            buf += to_string(code); ++cnt;
            if (cnt >= CAP) { sendMsg(0, buf); buf.clear(); cnt = 0; }
        }
    }
    if (cnt) sendMsg(0, buf);
    printf("halt\n"); fflush(stdout);
}

static void run_coordinator() {
    openDown.assign(T, 0); openRight.assign(T, 0);
    const int S = 0, G = (int)(T - 1);
    size_t P = g_edges.size();
    // Pure receiver: drain workers' streamed opens, claim the instant s-t connects.
    int idle = 0;
    while (uf(S) != uf(G)) {
        int sender; string body;
        if (recvAny(sender, body)) {
            idle = 0;
            const char *s = body.c_str();
            while (*s) {
                if (*s < '0' || *s > '9') { ++s; continue; }
                int code = 0;
                while (*s >= '0' && *s <= '9') { code = code * 10 + (*s - '0'); ++s; }
                mark_open(code);
            }
            if (uf(S) == uf(G)) break;
        } else if (++idle > 400) {   // workers' first batch always arrives well before this
            // workers stalled/dead: probe everything ourselves so we never fail.
            for (size_t p = 0; p < P; ++p) {
                int c = g_edges[p], room = c >> 1, dir = c & 1;
                if ((dir == 0 && openDown[room]) || (dir == 1 && openRight[room])) continue;
                if (probe_edge(c) && uf(S) == uf(G)) break;
            }
            break;
        }
    }
    claim_from_open();
}

// ================= cooperative SHARED-DSU racing (small A) =================
// Each agent runs a DISTINCT target-biased DFS (diverse tie-breaks), streaming the
// OPEN edges it discovers to agent 0. Agent 0 unions its own + all received opens
// into one shared DSU and claims the instant s-t connect — the UNION of A diverse
// searches links s-t in ~0.11*2T/agent, vs ~0.16*2T for the best single search
// (the race). Any agent whose own DFS reaches the goal also claims directly, so a
// death (incl. agent 0) never blocks a claim. Measured to beat both the race and
// diagonal coop for A in [3,5] (1.1-1.5x); above that diagonal coop wins.
static const int V6_KIND[8]  = {1, 1, 2, 2, 0, 0, 0, 0};
static const bool V6_BACK[8] = {false, true, false, true, false, true, false, true};
static const int V6_PRIO[8][4] = {
    {0,0,0,0},{0,0,0,0},{0,0,0,0},{0,0,0,0},
    {1,0,2,3},{2,3,0,1},{0,1,3,2},{3,2,1,0},
};
static void claim_own(const string &moves, bool back) {
    string path; path.reserve(moves.size() * 2);
    if (!back) { for (char c : moves) { path.push_back(c); path.push_back(c); } }
    else {
        for (int k = (int)moves.size() - 1; k >= 0; --k) {
            char c = moves[k];
            char iv = (c=='D')?'U':(c=='U')?'D':(c=='R')?'L':'R';
            path.push_back(iv); path.push_back(iv);
        }
    }
    printf("! %s\n", path.c_str()); fflush(stdout);
}
static void coop_dfs() {
    const int vi = AGENT_ID % 8;
    const int kind = V6_KIND[vi]; const bool back = V6_BACK[vi];
    const int *prio = V6_PRIO[vi];
    const bool isCoord = (AGENT_ID == 0);
    const int S = 0, G = (int)(T - 1);
    int si = back ? m - 1 : 0, sj = si, gi = back ? 0 : m - 1, gj = gi;
    const int RECV_EVERY = 24;
    const int CAP = max(8, min(36, (MAX_MSG_LEN - 4) / 7));

    vector<char> vis(T, 0);
    struct Frame { int i, j, next; };
    vector<Frame> st; string moves;
    vis[si * m + sj] = 1; st.push_back({si, sj, 0});
    int order[4];
    string buf; int cnt = 0; long probes = 0;

    while (!st.empty()) {
        Frame &f = st.back();
        if (f.i == gi && f.j == gj) { claim_own(moves, back); return; }   // own goal -> claim (race fallback)
        if (f.next == 4) { st.pop_back(); if (!moves.empty()) moves.pop_back(); continue; }
        if (kind == 0) { for (int t = 0; t < 4; ++t) order[t] = prio[t]; }
        else {
            int vd = (gi > f.i) ? 0 : 2, hd = (gj > f.j) ? 1 : 3;
            int av = (vd == 0) ? 2 : 0, ah = (hd == 1) ? 3 : 1;
            bool lv = (abs(gi - f.i) >= abs(gj - f.j)); if (kind == 2) lv = !lv;
            if (lv) { order[0]=vd; order[1]=hd; order[2]=av; order[3]=ah; }
            else    { order[0]=hd; order[1]=vd; order[2]=ah; order[3]=av; }
        }
        int d = order[f.next++];
        int ni = f.i + DI[d], nj = f.j + DJ[d];
        if (ni < 0 || ni >= m || nj < 0 || nj >= m) continue;
        int v = ni * m + nj;
        if (vis[v]) continue;
        int pr = (2 * f.i + 1) + DI[d], pc = (2 * f.j + 1) + DJ[d];
        ++probes;
        if (!ask(pr, pc)) continue;
        int u = f.i * m + f.j, code;
        if (d == 0) code = u * 2 + 0; else if (d == 1) code = u * 2 + 1;
        else if (d == 2) code = (u - m) * 2 + 0; else code = (u - 1) * 2 + 1;
        if (isCoord) {
            mark_open(code);
            if (uf(S) == uf(G)) { claim_from_open(); return; }
        } else {
            if (cnt) buf.push_back(' ');
            buf += to_string(code); ++cnt;
            if (cnt >= CAP) { sendMsg(0, buf); buf.clear(); cnt = 0; }
        }
        vis[v] = 1; moves.push_back(DC[d]); st.push_back({ni, nj, 0});
        if (isCoord && RECV_EVERY > 0 && (probes % RECV_EVERY) == 0) {
            int sender; string body;
            while (recvAny(sender, body)) {
                const char *s = body.c_str();
                while (*s) {
                    if (*s < '0' || *s > '9') { ++s; continue; }
                    int c = 0; while (*s >= '0' && *s <= '9') { c = c * 10 + (*s - '0'); ++s; }
                    mark_open(c);
                }
                if (uf(S) == uf(G)) { claim_from_open(); return; }
            }
        }
    }
    // DFS exhausted (tree is connected, so goal unreachable in our own view only):
    if (!isCoord) { if (cnt) sendMsg(0, buf); printf("halt\n"); fflush(stdout); return; }
    // coordinator: keep draining until connect, self-heal if workers stall.
    int idle = 0;
    while (uf(S) != uf(G)) {
        int sender; string body;
        if (recvAny(sender, body)) {
            idle = 0; const char *s = body.c_str();
            while (*s) { if (*s < '0' || *s > '9') { ++s; continue; } int c = 0; while (*s >= '0' && *s <= '9') { c = c*10 + (*s-'0'); ++s; } mark_open(c); }
        } else if (++idle > 400) {
            for (size_t p = 0; p < g_edges.size(); ++p) {
                int c = g_edges[p], room = c >> 1, dir = c & 1;
                if ((dir == 0 && openDown[room]) || (dir == 1 && openRight[room])) continue;
                if (probe_edge(c) && uf(S) == uf(G)) break;
            }
            break;
        }
    }
    claim_from_open();
}

int main() {
    if (scanf("%d %d %d %d", &N, &NUM_AGENTS, &AGENT_ID, &MAX_MSG_LEN) != 4) return 0;
    { int ch; while ((ch = getchar()) != '\n' && ch != EOF) {} }
    m = (N + 1) / 2;
    if (m <= 1) {
        if (AGENT_ID == 0) printf("! \n"); else printf("halt\n");
        fflush(stdout); return 0;
    }
    T = (long long)m * m;

    // coop_dfs (shared-DSU diverse racing) beats diagonal coop while the diagonal
    // per-worker cost 0.66*2T/(A-1) stays above coop_dfs's ~flat ~0.11*2T. That
    // holds for A<=5 at every N, and for A in [6,8] only at smaller N — the empirical
    // crossover on real merlin is ~ (A-1)*m <= 1100 (A=6:N<=~440, A=7:<=~350,
    // each 1.04-1.6x). Above that the diagonal's zero-coordination perfect division
    // wins; use it. (A==8 is a coin-flip even at small N — measured -11% at 301/8
    // over 4 seeds — so cap the coop_dfs window at A<=7.)
    bool use_coop_dfs = (NUM_AGENTS <= 5) ||
                        (NUM_AGENTS <= 7 && (long)(NUM_AGENTS - 1) * m <= 1100);
    if (use_coop_dfs) {
        if (AGENT_ID == 0) {
            ufp.resize(T); for (long long i = 0; i < T; ++i) ufp[i] = (int)i;
            openDown.assign(T, 0); openRight.assign(T, 0);
            build_edges();
        }
        coop_dfs();
        return 0;
    }

    ufp.resize(T); for (long long i = 0; i < T; ++i) ufp[i] = (int)i;
    build_edges();
    if (AGENT_ID == 0) run_coordinator();
    else run_worker();
    return 0;
}