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

struct Edge {
    int u, v;
    int r, c;
    char step;
};

static const string B64 = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+-";

string command_with_reply(const string &s) {
    cout << s << '\n' << flush;
    string reply;
    if (!getline(cin, reply)) exit(0);
    return reply;
}

void command_no_reply(const string &s) {
    cout << s << '\n' << flush;
}

vector<Edge> build_edges(int n) {
    int m = (n + 1) / 2;
    vector<Edge> edges;
    edges.reserve(2 * m * max(0, m - 1));
    for (int i = 0; i < m; ++i) {
        for (int j = 0; j < m; ++j) {
            int u = i * m + j;
            if (i + 1 < m) {
                edges.push_back({u, (i + 1) * m + j, 2 * i + 2, 2 * j + 1, 'D'});
            }
            if (j + 1 < m) {
                edges.push_back({u, i * m + j + 1, 2 * i + 1, 2 * j + 2, 'R'});
            }
        }
    }
    return edges;
}

string encode_bits(const vector<char> &bits) {
    string out;
    out.reserve((bits.size() + 5) / 6);
    for (size_t i = 0; i < bits.size(); i += 6) {
        int value = 0;
        for (int b = 0; b < 6 && i + b < bits.size(); ++b) {
            if (bits[i + b]) value |= 1 << b;
        }
        out.push_back(B64[value]);
    }
    return out;
}

vector<char> decode_bits(const string &text, int needed) {
    int inv[128];
    fill(begin(inv), end(inv), 0);
    for (int i = 0; i < (int)B64.size(); ++i) inv[(int)B64[i]] = i;
    vector<char> bits;
    bits.reserve(needed);
    for (char ch : text) {
        int value = (0 <= ch && ch < 128) ? inv[(int)ch] : 0;
        for (int b = 0; b < 6 && (int)bits.size() < needed; ++b) {
            bits.push_back((value >> b) & 1);
        }
    }
    return bits;
}

int assigned_count(int total_edges, int agents, int id) {
    if (id >= total_edges) return 0;
    return (total_edges - 1 - id) / agents + 1;
}

void claim_path(const string &path) {
    if (path.empty()) command_no_reply("!");
    else command_no_reply("! " + path);
    exit(0);
}

void full_reconstruction_mode(int n, int agents, int id, int max_msg_len) {
    int m = (n + 1) / 2;
    vector<Edge> edges = build_edges(n);
    int e = (int)edges.size();
    int chunk = max(1, max_msg_len);

    if (id != 0) {
        vector<char> bits;
        bits.reserve(assigned_count(e, agents, id));
        for (int k = id; k < e; k += agents) {
            const Edge &edge = edges[k];
            string reply = command_with_reply("? " + to_string(edge.r) + " " + to_string(edge.c));
            bits.push_back(!reply.empty() && reply[0] == '1');
        }
        string packed = encode_bits(bits);
        for (int pos = 0; pos < (int)packed.size(); pos += chunk) {
            command_with_reply("> 0 " + packed.substr(pos, chunk));
        }
        command_no_reply("halt");
        exit(0);
    }

    vector<char> open(e, 0);
    for (int k = 0; k < e; k += agents) {
        const Edge &edge = edges[k];
        string reply = command_with_reply("? " + to_string(edge.r) + " " + to_string(edge.c));
        open[k] = (!reply.empty() && reply[0] == '1');
    }

    vector<string> received(agents);
    int expected_messages = 0;
    vector<int> expected_bits(agents, 0), expected_chunks(agents, 0);
    for (int p = 1; p < agents; ++p) {
        expected_bits[p] = assigned_count(e, agents, p);
        int encoded_len = (expected_bits[p] + 5) / 6;
        expected_chunks[p] = (encoded_len + chunk - 1) / chunk;
        expected_messages += expected_chunks[p];
    }

    int got_messages = 0;
    while (got_messages < expected_messages) {
        string reply = command_with_reply("< ?");
        if (reply == "- -") continue;
        size_t sp = reply.find(' ');
        if (sp == string::npos) continue;
        int sender = stoi(reply.substr(0, sp));
        if (sender <= 0 || sender >= agents) continue;
        received[sender] += reply.substr(sp + 1);
        ++got_messages;
    }

    for (int p = 1; p < agents; ++p) {
        vector<char> bits = decode_bits(received[p], expected_bits[p]);
        int idx = 0;
        for (int k = p; k < e; k += agents) {
            open[k] = bits[idx++];
        }
    }

    int vcount = m * m;
    vector<vector<pair<int, char>>> adj(vcount);
    for (int k = 0; k < e; ++k) {
        if (!open[k]) continue;
        const Edge &edge = edges[k];
        adj[edge.u].push_back({edge.v, edge.step});
        char back = edge.step == 'D' ? 'U' : 'L';
        adj[edge.v].push_back({edge.u, back});
    }

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

    string room_path;
    for (int cur = vcount - 1; cur != 0; cur = parent[cur]) {
        room_path.push_back(parent_step[cur]);
    }
    reverse(room_path.begin(), room_path.end());

    string path;
    path.reserve(room_path.size() * 2);
    for (char ch : room_path) {
        path.push_back(ch);
        path.push_back(ch);
    }
    claim_path(path);
}

struct DfsState {
    int n, m, id, max_msg_len;
    string order;
    vector<char> visited;
    vector<pair<int, int>> st;
    string room_path;

    DfsState(int n_, int id_, int max_msg_len_, string order_)
        : n(n_), m((n_ + 1) / 2), id(id_), max_msg_len(max_msg_len_), order(std::move(order_)),
          visited(m * m, 0) {
        visited[0] = 1;
        st.push_back({0, 0});
    }

    bool next_query(string &cmd, int &next_node, char &step) {
        while (!st.empty()) {
            int u = st.back().first;
            if (u == m * m - 1) return false;
            int &pos = st.back().second;
            if (pos >= (int)order.size()) {
                st.pop_back();
                if (!room_path.empty()) room_path.pop_back();
                continue;
            }
            char ch = order[pos++];
            int i = u / m, j = u % m;
            int ni = i, nj = j;
            if (ch == 'D') ++ni;
            else if (ch == 'U') --ni;
            else if (ch == 'R') ++nj;
            else --nj;
            if (ni < 0 || ni >= m || nj < 0 || nj >= m) continue;
            int v = ni * m + nj;
            if (visited[v]) continue;

            int rr = 2 * i + 1, cc = 2 * j + 1;
            if (ch == 'D') ++rr;
            else if (ch == 'U') --rr;
            else if (ch == 'R') ++cc;
            else --cc;
            cmd = "? " + to_string(rr) + " " + to_string(cc);
            next_node = v;
            step = ch;
            return true;
        }
        return false;
    }

    void accept_open(int v, char ch) {
        visited[v] = 1;
        room_path.push_back(ch);
        st.push_back({v, 0});
    }

    bool at_goal() const {
        return !st.empty() && st.back().first == m * m - 1;
    }

    string cell_path() const {
        string path;
        path.reserve(room_path.size() * 2);
        for (char ch : room_path) {
            path.push_back(ch);
            path.push_back(ch);
        }
        return path;
    }
};

void send_path_to_zero(const string &path, int max_msg_len) {
    int payload = max(1, max_msg_len - 1);
    for (int pos = 0; pos < (int)path.size(); pos += payload) {
        bool last = pos + payload >= (int)path.size();
        string body;
        body.push_back(last ? 'E' : 'P');
        body += path.substr(pos, payload);
        command_with_reply("> 0 " + body);
    }
    command_no_reply("halt");
    exit(0);
}

bool receive_worker_path(vector<string> &parts, string &out_path) {
    string reply = command_with_reply("< ?");
    if (reply == "- -") return false;
    size_t sp = reply.find(' ');
    if (sp == string::npos) return false;
    int sender = stoi(reply.substr(0, sp));
    string body = reply.substr(sp + 1);
    if (sender <= 0 || sender >= (int)parts.size() || body.empty()) return false;
    char kind = body[0];
    if (kind != 'P' && kind != 'E') return false;
    parts[sender] += body.substr(1);
    if (kind == 'E') {
        out_path = parts[sender];
        return true;
    }
    return false;
}

void three_agent_search_mode(int n, int agents, int id, int max_msg_len) {
    if (n == 1) {
        if (id == 0) claim_path("");
        command_no_reply("halt");
        exit(0);
    }

    static const vector<string> orders = {
        "DRUL", "RDLU", "UDLR"
    };
    DfsState dfs(n, id, max_msg_len, orders[id % (int)orders.size()]);
    vector<string> worker_parts(agents);
    const int poll_every = 16;
    int issued = 0;

    while (true) {
        if (id == 0 && issued > 0 && issued % poll_every == 0) {
            string received_path;
            ++issued;
            if (receive_worker_path(worker_parts, received_path)) {
                claim_path(received_path);
            }
            continue;
        }

        if (dfs.at_goal()) {
            string path = dfs.cell_path();
            if (id == 0) claim_path(path);
            send_path_to_zero(path, max_msg_len);
        }

        string cmd;
        int next_node = -1;
        char step = 0;
        if (!dfs.next_query(cmd, next_node, step)) {
            command_no_reply("halt");
            exit(0);
        }

        ++issued;
        string reply = command_with_reply(cmd);
        if (!reply.empty() && reply[0] == '1') {
            dfs.accept_open(next_node, step);
        }
    }
}

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

    int n, agents, id, max_msg_len;
    if (!(cin >> n >> agents >> id >> max_msg_len)) return 0;
    string dummy;
    getline(cin, dummy);

    if (agents == 3) {
        three_agent_search_mode(n, agents, id, max_msg_len);
    } else {
        full_reconstruction_mode(n, agents, id, max_msg_len);
    }
    return 0;
}