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

struct Edge {
    int a, b;
    int qr, qc;
    char dir;
};

static const string ALPH = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";

string enc3(int x) {
    string s(3, '0');
    s[2] = ALPH[x % 62]; x /= 62;
    s[1] = ALPH[x % 62]; x /= 62;
    s[0] = ALPH[x % 62];
    return s;
}

int dec3(const string &s, int pos) {
    int x = 0;
    for (int k = 0; k < 3; k++) {
        char ch = s[pos + k];
        int v = ('0' <= ch && ch <= '9') ? ch - '0'
              : ('A' <= ch && ch <= 'Z') ? ch - 'A' + 10
                                          : ch - 'a' + 36;
        x = x * 62 + v;
    }
    return x;
}

struct MazeInfo {
    int N, m, rooms;
    vector<Edge> edges;
    vector<array<int, 4>> edge_at;
};

MazeInfo build_info(int N) {
    MazeInfo z;
    z.N = N;
    z.m = (N + 1) / 2;
    z.rooms = z.m * z.m;
    z.edge_at.assign(z.rooms, {-1, -1, -1, -1});
    for (int i = 0; i < z.m; i++) {
        for (int j = 0; j < z.m; j++) {
            int u = i * z.m + j;
            if (i + 1 < z.m) {
                int v = (i + 1) * z.m + j;
                int id = (int)z.edges.size();
                z.edges.push_back({u, v, 2 * i + 2, 2 * j + 1, 'D'});
                z.edge_at[u][2] = id;
                z.edge_at[v][0] = id;
            }
            if (j + 1 < z.m) {
                int v = i * z.m + (j + 1);
                int id = (int)z.edges.size();
                z.edges.push_back({u, v, 2 * i + 1, 2 * j + 2, 'R'});
                z.edge_at[u][3] = id;
                z.edge_at[v][1] = id;
            }
        }
    }
    return z;
}

char move_between(int m, int u, int v) {
    if (v == u + m) return 'D';
    if (v == u - m) return 'U';
    if (v == u + 1) return 'R';
    return 'L';
}

char inv_move(char ch) {
    if (ch == 'U') return 'D';
    if (ch == 'D') return 'U';
    if (ch == 'L') return 'R';
    return 'L';
}

void claim_room_path(const string &rooms_path) {
    string path;
    path.reserve(rooms_path.size() * 2);
    for (char ch : rooms_path) {
        path.push_back(ch);
        path.push_back(ch);
    }
    cout << "! " << path << endl;
}

void run_greedy_search(const MazeInfo &mz, int agent_id) {
    struct Param { int prog, dev, offset; bool rev; };
    static const Param params[] = {
        {50, 20,   0, false},
        {50,  0,   0, true },
        {40, 20,   0, false},
        {50, 20, -40, false},
        {50, 20,  40, false},
        {30, 20,   0, true },
        {70,  5, -40, false},
        {70,  5,  40, true },
        {30, 10,   0, false},
        {90,  0,   0, true },
    };
    Param p = params[agent_id % (int)(sizeof(params) / sizeof(params[0]))];

    int start = p.rev ? mz.rooms - 1 : 0;
    int target = p.rev ? 0 : mz.rooms - 1;

    vector<unsigned char> reached(mz.rooms, 0), asked(mz.edges.size(), 0);
    vector<int> dist(mz.rooms, INT_MAX), parent(mz.rooms, -1);

    struct Item {
        long long score;
        int tie, from, edge_id, to;
        bool operator<(const Item &o) const {
            if (score != o.score) return score > o.score;
            if (tie != o.tie) return tie > o.tie;
            return edge_id > o.edge_id;
        }
    };
    priority_queue<Item> pq;

    auto transformed = [&](int u) {
        int i = u / mz.m, j = u % mz.m;
        if (p.rev) {
            i = mz.m - 1 - i;
            j = mz.m - 1 - j;
        }
        return pair<int, int>(i, j);
    };
    auto score_of = [&](int v, int g) {
        auto [i, j] = transformed(v);
        int s = i + j;
        int d = abs(i - j - p.offset);
        return 1LL * g - 1LL * p.prog * s + 1LL * p.dev * d;
    };
    auto push_edges = [&](int u) {
        for (int d = 0; d < 4; d++) {
            int eid = mz.edge_at[u][d];
            if (eid < 0 || asked[eid]) continue;
            const Edge &e = mz.edges[eid];
            int v = e.a ^ e.b ^ u;
            if (reached[v]) continue;
            asked[eid] = 1;
            auto [ti, tj] = transformed(v);
            int h = (mz.m - 1 - ti) + (mz.m - 1 - tj);
            pq.push({score_of(v, dist[u] + 1), h, u, eid, v});
        }
    };

    reached[start] = 1;
    dist[start] = 0;
    push_edges(start);

    while (!pq.empty()) {
        Item it = pq.top();
        pq.pop();
        if (!reached[it.from] || reached[it.to]) continue;
        const Edge &e = mz.edges[it.edge_id];
        cout << "? " << e.qr << ' ' << e.qc << endl;
        string ans;
        if (!(cin >> ans)) return;
        if (ans != "1") continue;

        reached[it.to] = 1;
        dist[it.to] = dist[it.from] + 1;
        parent[it.to] = it.from;
        if (it.to == target) {
            string s;
            for (int v = target; v != start; v = parent[v]) {
                s.push_back(move_between(mz.m, parent[v], v));
            }
            reverse(s.begin(), s.end());
            if (p.rev) {
                string t;
                t.reserve(s.size());
                for (int i = (int)s.size() - 1; i >= 0; i--) t.push_back(inv_move(s[i]));
                s.swap(t);
            }
            claim_room_path(s);
            return;
        }
        push_edges(it.to);
    }

    cout << "halt" << endl;
}

void run_full_restore(const MazeInfo &mz, int num_agents, int agent_id, int max_msg_len) {
    vector<int> mine;
    for (int e = agent_id; e < (int)mz.edges.size(); e += num_agents) {
        const Edge &ed = mz.edges[e];
        cout << "? " << ed.qr << ' ' << ed.qc << endl;
        string ans;
        if (!(cin >> ans)) return;
        if (ans == "1") mine.push_back(e);
    }

    if (agent_id != 0) {
        int per_msg = max(1, max_msg_len / 3);
        for (int i = 0; i < (int)mine.size(); i += per_msg) {
            string body;
            int lim = min((int)mine.size(), i + per_msg);
            body.reserve(3 * (lim - i));
            for (int j = i; j < lim; j++) body += enc3(mine[j]);
            cout << "> 0 " << body << endl;
            string ok;
            if (!(cin >> ok)) return;
        }
        cout << "> 0 ~" << endl;
        string ok;
        if (cin >> ok) cout << "halt" << endl;
        return;
    }

    vector<vector<pair<int, char>>> adj(mz.rooms);
    auto add_edge = [&](int idx) {
        const Edge &ed = mz.edges[idx];
        if (ed.dir == 'D') {
            adj[ed.a].push_back({ed.b, 'D'});
            adj[ed.b].push_back({ed.a, 'U'});
        } else {
            adj[ed.a].push_back({ed.b, 'R'});
            adj[ed.b].push_back({ed.a, 'L'});
        }
    };

    for (int idx : mine) add_edge(idx);

    int finished = 0;
    while (finished < num_agents - 1) {
        cout << "< ?" << endl;
        string sender, body;
        if (!(cin >> sender >> body)) return;
        if (sender == "-" && body == "-") continue;
        if (body == "~") {
            finished++;
            continue;
        }
        for (int pos = 0; pos + 2 < (int)body.size(); pos += 3) {
            int idx = dec3(body, pos);
            if (0 <= idx && idx < (int)mz.edges.size()) add_edge(idx);
        }
    }

    vector<int> parent(mz.rooms, -1);
    vector<char> step(mz.rooms, 0);
    queue<int> q;
    parent[0] = 0;
    q.push(0);
    while (!q.empty() && parent[mz.rooms - 1] == -1) {
        int u = q.front();
        q.pop();
        for (auto [v, ch] : adj[u]) {
            if (parent[v] != -1) continue;
            parent[v] = u;
            step[v] = ch;
            q.push(v);
            if (v == mz.rooms - 1) break;
        }
    }

    string room_path;
    for (int v = mz.rooms - 1; v != 0; v = parent[v]) {
        if (v < 0) return;
        room_path.push_back(step[v]);
    }
    reverse(room_path.begin(), room_path.end());
    claim_room_path(room_path);
}

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

    int N, NUM_AGENTS, AGENT_ID, MAX_MSG_LEN;
    if (!(cin >> N >> NUM_AGENTS >> AGENT_ID >> MAX_MSG_LEN)) return 0;

    if (N == 1) {
        if (AGENT_ID == 0) cout << "!" << endl;
        else cout << "halt" << endl;
        return 0;
    }

    MazeInfo mz = build_info(N);

    if (NUM_AGENTS <= 5) {
        run_greedy_search(mz, AGENT_ID);
    } else {
        run_full_restore(mz, NUM_AGENTS, AGENT_ID, MAX_MSG_LEN);
    }
    return 0;
}