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

// Dabius.ai Merlin helper agent.
//
// Generator analysis used by this solution:
// - All odd/odd cells are rooms and are always empty.
// - Only cells between two neighbouring rooms are unknown corridors.
// - The generator shuffles all such room-graph edges and runs Kruskal, so the
//   corridors are exactly a spanning tree of the room grid.
// Therefore it is enough to query corridor cells.  Once the revealed open
// room-edges connect the top-left room to the bottom-right room, the unique
// path in those revealed edges is the real maze path.

struct DSU {
    vector<int> p, sz;
    DSU() {}
    explicit DSU(int n) { init(n); }
    void init(int n) {
        p.resize(n);
        sz.assign(n, 1);
        iota(p.begin(), p.end(), 0);
    }
    int find(int x) {
        while (p[x] != x) {
            p[x] = p[p[x]];
            x = p[x];
        }
        return x;
    }
    bool unite(int a, int b) {
        a = find(a); b = find(b);
        if (a == b) return false;
        if (sz[a] < sz[b]) swap(a, b);
        p[b] = a;
        sz[a] += sz[b];
        return true;
    }
};

struct Edge {
    int a, b;       // endpoints in the room graph, 0-based: r*m+c
    int qr, qc;     // 1-based maze cell to query: corridor between endpoints
    int X, Y;       // doubled midpoint coordinates in the room grid
    int dir;        // 0 = vertical room-edge, 1 = horizontal room-edge
};

static const string ALPH = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz+/";

int enc6(int x) { return ALPH[x & 63]; }
int dec6(char ch) {
    if ('0' <= ch && ch <= '9') return ch - '0';
    if ('A' <= ch && ch <= 'Z') return 10 + ch - 'A';
    if ('a' <= ch && ch <= 'z') return 36 + ch - 'a';
    if (ch == '+') return 62;
    if (ch == '/') return 63;
    return 0;
}

vector<Edge> build_order(int N) {
    const int m = (N + 1) / 2;
    vector<Edge> edges;
    edges.reserve(2 * m * max(0, m - 1));

    for (int r = 0; r < m; ++r) {
        for (int c = 0; c < m; ++c) {
            const int v = r * m + c;
            if (r + 1 < m) {
                edges.push_back(Edge{
                    v, v + m,
                    2 * r + 2, 2 * c + 1,
                    2 * r + 1, 2 * c,
                    0
                });
            }
            if (c + 1 < m) {
                edges.push_back(Edge{
                    v, v + 1,
                    2 * r + 1, 2 * c + 2,
                    2 * r, 2 * c + 1,
                    1
                });
            }
        }
    }

    // Empirically strongest simple prior for this randomized-Kruskal maze:
    // the corner-to-corner MST path is biased toward the main diagonal, but can
    // wander broadly.  Query by diagonal band first, then by distance from the
    // centre of the diagonal.  This preserves a deterministic full scan, so the
    // solution remains guaranteed even on unlucky mazes.
    sort(edges.begin(), edges.end(), [m](const Edge& u, const Edge& v) {
        const int target = 2 * (m - 1);
        int du = abs(u.X - u.Y), dv = abs(v.X - v.Y);
        if (du != dv) return du < dv;
        int cu = abs((u.X + u.Y) - target);
        int cv = abs((v.X + v.Y) - target);
        if (cu != cv) return cu < cv;
        int su = u.X + u.Y, sv = v.X + v.Y;
        if (su != sv) return su < sv;
        if (u.X != v.X) return u.X < v.X;
        if (u.Y != v.Y) return u.Y < v.Y;
        if (u.dir != v.dir) return u.dir < v.dir;
        if (u.a != v.a) return u.a < v.a;
        return u.b < v.b;
    });
    return edges;
}

int assigned_count_stride(int totalEdges, int first, int stride) {
    if (stride <= 0 || first < 0 || first >= totalEdges) return 0;
    return (totalEdges - 1 - first) / stride + 1;
}

string make_batch_body(const vector<unsigned char>& bits, int maxMsgLen) {
    const int cnt = (int)bits.size();
    if (maxMsgLen < 4) {
        // Degenerate fallback: one bit per message.
        return bits.empty() ? string("0") : string(1, bits[0] ? '1' : '0');
    }
    string body;
    body.reserve(3 + (cnt + 5) / 6);
    body.push_back('D');
    body.push_back((char)enc6(cnt >> 6));
    body.push_back((char)enc6(cnt & 63));
    for (int i = 0; i < cnt; i += 6) {
        int x = 0;
        for (int j = 0; j < 6 && i + j < cnt; ++j) {
            if (bits[i + j]) x |= (1 << j);
        }
        body.push_back((char)enc6(x));
    }
    return body;
}

char room_move(int from, int to, int m) {
    if (to == from + 1) return 'R';
    if (to == from - 1) return 'L';
    if (to == from + m) return 'D';
    if (to == from - m) return 'U';
    return '?';
}
char opposite_move(char ch) {
    if (ch == 'R') return 'L';
    if (ch == 'L') return 'R';
    if (ch == 'D') return 'U';
    return 'D';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, NUM_AGENTS, ID, MAX_MSG_LEN;
    if (!(cin >> N >> NUM_AGENTS >> ID >> MAX_MSG_LEN)) return 0;
    string startup_rest;
    getline(cin, startup_rest);

    const int m = (N + 1) / 2;
    const int V = m * m;

    if (N == 1) {
        if (ID == 0) cout << "!" << '\n' << flush;
        else cout << "halt" << '\n' << flush;
        return 0;
    }

    vector<Edge> edges = build_order(N);
    const int E = (int)edges.size();

    // Too many agents on a small maze create more message overhead than useful
    // queries.  sqrt(E) is a good crossover and still uses every finals agent
    // on the largest mazes.
    int activeAgents = NUM_AGENTS;
    if (E > 0) {
        int s = max(1, (int)floor(sqrt((double)E) + 0.5));
        activeAgents = min(NUM_AGENTS, s);
    }
    if (MAX_MSG_LEN < 1) activeAgents = 1;

    if (ID >= activeAgents) {
        cout << "halt" << '\n' << flush;
        return 0;
    }

    int capacityBits = 1;
    if (MAX_MSG_LEN >= 4) capacityBits = min(4095, (MAX_MSG_LEN - 3) * 6);

    // New scheduling improvement over the previous version:
    // for many agents, agent 0 becomes a pure collector and every other active
    // agent scans the whole ordered edge list in a (A-1)-way split.  This avoids
    // the collector falling behind on both its own queries and a bursty message
    // queue.  Random testing shows it is consistently faster for high agent
    // counts, especially NUM_AGENTS around 30..50.
    const bool readerOnly = (activeAgents >= 21 && MAX_MSG_LEN >= 1);
    const int workerStride = readerOnly ? max(1, activeAgents - 1) : activeAgents;

    int BATCH;
    if (MAX_MSG_LEN < 4) {
        BATCH = 1;
    } else if (readerOnly) {
        int W = max(1, activeAgents - 1);
        int tuned = (2300 + W / 2) / W;       // about 115 for W=20, 48 for W>=28
        if (W >= 28) tuned = 48;
        else tuned = max(tuned, 32);
        if (E <= 2500) tuned = 32;
        tuned = min(tuned, 128);
        BATCH = max(1, min(capacityBits, tuned));
    } else {
        int targetBatch = max(16, (int)floor(sqrt((double)max(1, E)) + 0.5));
        BATCH = max(1, min(capacityBits, targetBatch));
    }
    const int READ_PERIOD = max(8, BATCH / 2);

    auto send_batch_to_zero = [&](vector<unsigned char>& bits) {
        if (bits.empty()) return;
        string body = make_batch_body(bits, MAX_MSG_LEN);
        cout << "> 0 " << body << '\n' << flush;
        string ok;
        if (!getline(cin, ok)) exit(0);
        bits.clear();
    };

    if (ID != 0) {
        vector<unsigned char> bits;
        bits.reserve(BATCH);

        if (readerOnly) {
            const int W = activeAgents - 1;
            const int first = ID - 1; // worker 1 owns global positions 0,W,2W,...
            int firstBatch = BATCH;
            if (W >= 25 || E <= 30000) {
                // Spread first reports over time to avoid one large delivery burst.
                firstBatch = 1 + ((ID - 1) * BATCH) / max(1, W);
                firstBatch = max(1, min(BATCH, firstBatch));
            }
            int currentLimit = firstBatch;
            for (int pos = first; pos < E; pos += W) {
                const Edge& e = edges[pos];
                cout << "? " << e.qr << ' ' << e.qc << '\n' << flush;
                string reply;
                if (!getline(cin, reply)) return 0;
                bits.push_back((!reply.empty() && reply[0] == '1') ? 1 : 0);
                if ((int)bits.size() >= currentLimit) {
                    send_batch_to_zero(bits);
                    currentLimit = BATCH;
                }
            }
        } else {
            for (int pos = ID; pos < E; pos += activeAgents) {
                const Edge& e = edges[pos];
                cout << "? " << e.qr << ' ' << e.qc << '\n' << flush;
                string reply;
                if (!getline(cin, reply)) return 0;
                bits.push_back((!reply.empty() && reply[0] == '1') ? 1 : 0);
                if ((int)bits.size() >= BATCH) send_batch_to_zero(bits);
            }
        }

        send_batch_to_zero(bits);
        cout << "halt" << '\n' << flush;
        return 0;
    }

    DSU dsu(V);
    vector<signed char> known(E, -1);
    vector<int> got(activeAgents, 0), total(activeAgents, 0);
    if (readerOnly) {
        total[0] = 0;
        const int W = activeAgents - 1;
        for (int sender = 1; sender < activeAgents; ++sender) {
            total[sender] = assigned_count_stride(E, sender - 1, W);
        }
    } else {
        for (int a = 0; a < activeAgents; ++a) {
            total[a] = assigned_count_stride(E, a, activeAgents);
        }
    }

    vector<vector<pair<int,char>>> adj(V);
    bool connected = false;

    auto mark_edge = [&](int pos, bool open) {
        if (pos < 0 || pos >= E) return;
        if (known[pos] != -1) return;
        known[pos] = open ? 1 : 0;
        if (!open) return;
        const Edge& e = edges[pos];
        char ch = room_move(e.a, e.b, m);
        adj[e.a].push_back({e.b, ch});
        adj[e.b].push_back({e.a, opposite_move(ch)});
        dsu.unite(e.a, e.b);
        if (dsu.find(0) == dsu.find(V - 1)) connected = true;
    };

    auto decode_message = [&](int sender, const string& body) {
        if (sender <= 0 || sender >= activeAgents) return;
        if (body.empty()) return;
        const int base = got[sender];
        auto global_pos = [&](int localIndex) -> int {
            if (readerOnly) return (sender - 1) + localIndex * (activeAgents - 1);
            return sender + localIndex * activeAgents;
        };

        if (body[0] == 'D' && (int)body.size() >= 3) {
            int cnt = dec6(body[1]) * 64 + dec6(body[2]);
            for (int i = 0; i < cnt; ++i) {
                int chIndex = 3 + i / 6;
                if (chIndex >= (int)body.size()) break;
                int x = dec6(body[chIndex]);
                bool bit = ((x >> (i % 6)) & 1) != 0;
                mark_edge(global_pos(base + i), bit);
            }
            got[sender] += cnt;
        } else if (body[0] == '0' || body[0] == '1') {
            mark_edge(global_pos(base), body[0] == '1');
            got[sender]++;
        }
        if (got[sender] > total[sender]) got[sender] = total[sender];
    };

    auto claim_and_exit = [&]() {
        vector<int> parent(V, -1);
        vector<char> pmove(V, 0);
        deque<int> q;
        parent[0] = 0;
        q.push_back(0);
        while (!q.empty() && parent[V - 1] == -1) {
            int v = q.front();
            q.pop_front();
            for (auto [to, ch] : adj[v]) {
                if (parent[to] == -1) {
                    parent[to] = v;
                    pmove[to] = ch;
                    q.push_back(to);
                    if (to == V - 1) break;
                }
            }
        }
        if (parent[V - 1] == -1) return;
        string roomPath;
        for (int cur = V - 1; cur != 0; cur = parent[cur]) roomPath.push_back(pmove[cur]);
        reverse(roomPath.begin(), roomPath.end());

        string path;
        path.reserve(roomPath.size() * 2);
        for (char ch : roomPath) {
            path.push_back(ch);
            path.push_back(ch);
        }
        cout << "! " << path << '\n' << flush;
        exit(0);
    };

    auto all_received = [&]() {
        for (int a = 0; a < activeAgents; ++a) {
            if (got[a] < total[a]) return false;
        }
        return true;
    };

    auto read_one_message = [&]() -> bool {
        cout << "< ?" << '\n' << flush;
        string reply;
        if (!getline(cin, reply)) exit(0);
        if (reply == "- -") return false;
        size_t sp = reply.find(' ');
        if (sp == string::npos) return true;
        int sender = atoi(reply.substr(0, sp).c_str());
        string body = reply.substr(sp + 1);
        decode_message(sender, body);
        return true;
    };

    if (readerOnly) {
        while (true) {
            if (connected) claim_and_exit();
            read_one_message();
            if (connected) claim_and_exit();
            if (all_received() && dsu.find(0) == dsu.find(V - 1)) {
                connected = true;
                claim_and_exit();
            }
        }
    }

    auto drain_messages = [&]() {
        while (true) {
            bool gotMsg = read_one_message();
            if (connected) claim_and_exit();
            if (!gotMsg) break;
        }
    };

    int ownQueriesSinceRead = 0;
    for (int pos = 0; ; ) {
        if (connected) claim_and_exit();

        if (pos < E) {
            const Edge& e = edges[pos];
            cout << "? " << e.qr << ' ' << e.qc << '\n' << flush;
            string reply;
            if (!getline(cin, reply)) return 0;
            mark_edge(pos, (!reply.empty() && reply[0] == '1'));
            got[0]++;
            ownQueriesSinceRead++;
            pos += activeAgents;

            if (connected) claim_and_exit();
            if (ownQueriesSinceRead >= READ_PERIOD) {
                ownQueriesSinceRead = 0;
                drain_messages();
            }
        } else {
            if (connected) claim_and_exit();
            if (all_received() && dsu.find(0) == dsu.find(V - 1)) {
                connected = true;
                claim_and_exit();
            }
            drain_messages();
        }
    }
}