#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;
}

void claim_path(const string &path);

void prioritize_edges(vector<Edge> &edges, int n) {
    int m = (n + 1) / 2;
    auto key = [m](const Edge &edge) {
        int i = edge.u / m, j = edge.u % m;
        int x2 = 2 * i + (edge.step == 'D');
        int y2 = 2 * j + (edge.step == 'R');
        int diagonal = abs(x2 - y2);
        int center = abs(x2 + y2 - 2 * (m - 1));
        return pair<int, int>{diagonal, center};
    };
    stable_sort(edges.begin(), edges.end(), [&](const Edge &a, const Edge &b) {
        return key(a) < key(b);
    });
}

bool known_room_path(int m, const vector<Edge> &edges, const vector<char> &open, string &room_path) {
    int vcount = m * m;
    vector<vector<pair<int, char>>> adj(vcount);
    for (int k = 0; k < (int)edges.size(); ++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);
        }
    }
    if (parent[vcount - 1] == -2) return false;

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

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

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;
}

int choose_phase_bits(int total_edges, int agents, int max_msg_len) {
    int per_agent = (total_edges + agents - 1) / agents;
    int phase;
    if (per_agent <= 1150) {
        phase = agents >= 40 ? 512 : max_msg_len * 6;
    } else if (per_agent <= 1500) {
        phase = agents >= 30 ? 768 : 960;
    } else if (per_agent <= 2800) {
        if (agents < 20) phase = max_msg_len * 6;
        else if (agents >= 48) phase = 768;
        else phase = per_agent >= 2600 ? 768 : 864;
    } else if (per_agent <= 4000) {
        phase = (30 <= agents && agents <= 47) ? 960 : max_msg_len * 6;
    } else if (agents <= 8) {
        phase = 768;
    } else if (agents <= 12) {
        phase = 512;
    } else {
        phase = 768;
    }

    if (per_agent > 720) {
        double rho = 0.55;
        double estimate = sqrt(2.0 * (agents - 1) * rho * total_edges / max(1, agents));
        int formula = (int)(estimate / 6.0 + 0.5) * 6;
        formula = max(96, min(768, formula));

        if (27 <= agents && agents <= 28 && per_agent <= 1300) {
            phase = formula;
        } else if (agents == 29 && per_agent <= 1300) {
            phase = 768;
        } else if (30 <= agents && agents <= 44 && per_agent >= 2600) {
            phase = formula;
        }
    }
    return max(1, min(max_msg_len * 6, phase));
}

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

vector<char> query_assigned_bits(const vector<Edge> &edges, int agents, int id) {
    vector<char> bits;
    bits.reserve(assigned_count((int)edges.size(), agents, id));
    for (int k = id; k < (int)edges.size(); 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');
    }
    return bits;
}

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);
    prioritize_edges(edges, n);
    int e = (int)edges.size();
    int chunk = max(1, max_msg_len);

    vector<int> encoded_len(agents, 0);
    int max_worker_encoded = 0;
    int max_worker_bits = 0;
    for (int p = 1; p < agents; ++p) {
        int worker_bits = assigned_count(e, agents, p);
        encoded_len[p] = (worker_bits + 5) / 6;
        max_worker_encoded = max(max_worker_encoded, encoded_len[p]);
        max_worker_bits = max(max_worker_bits, worker_bits);
    }

    int workers = agents - 1;
    int group_size = 1;
    bool prefer_grouped = max_worker_bits <= 720;
    if (workers >= 4 && prefer_grouped && max_worker_encoded > 0 && max_worker_encoded <= chunk) {
        int cap = max(1, chunk / max_worker_encoded);
        int best_cost = workers;
        for (int s = 2; s <= min(workers, cap); ++s) {
            int cost = (s - 1) + (workers + s - 1) / s;
            if (cost < best_cost) {
                best_cost = cost;
                group_size = s;
            }
        }
    }

    vector<vector<int>> groups;
    if (group_size > 1) {
        for (int p = 1; p < agents; p += group_size) {
            vector<int> group;
            int total = 0;
            for (int q = p; q < agents && (int)group.size() < group_size; ++q) {
                if (total + encoded_len[q] > chunk && !group.empty()) break;
                group.push_back(q);
                total += encoded_len[q];
            }
            groups.push_back(group);
        }
    }

    if (!groups.empty()) {
        if (id != 0) {
            vector<char> bits = query_assigned_bits(edges, agents, id);
            string packed = encode_bits(bits);

            const vector<int> *my_group = nullptr;
            for (const auto &group : groups) {
                if (find(group.begin(), group.end(), id) != group.end()) {
                    my_group = &group;
                    break;
                }
            }
            int collector = (*my_group)[0];
            if (id != collector) {
                command_with_reply("> " + to_string(collector) + " " + packed);
                command_no_reply("halt");
                exit(0);
            }

            vector<string> part(agents);
            vector<char> got(agents, 0);
            part[id] = packed;
            got[id] = 1;
            int need = (int)my_group->size() - 1;
            int received = 0;
            while (received < need) {
                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 || got[sender]) continue;
                if (find(my_group->begin(), my_group->end(), sender) == my_group->end()) continue;
                part[sender] = reply.substr(sp + 1);
                got[sender] = 1;
                ++received;
            }

            string payload;
            for (int p : *my_group) payload += part[p];
            command_with_reply("> 0 " + payload);
            command_no_reply("halt");
            exit(0);
        }

        vector<char> open(e, 0);
        vector<char> own_bits = query_assigned_bits(edges, agents, 0);
        int own_idx = 0;
        for (int k = 0; k < e; k += agents) open[k] = own_bits[own_idx++];

        int expected_messages = (int)groups.size();
        int got_messages = 0;
        vector<char> got_group(agents, 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 || got_group[sender]) continue;
            const vector<int> *group_ptr = nullptr;
            for (const auto &group : groups) {
                if (group[0] == sender) {
                    group_ptr = &group;
                    break;
                }
            }
            if (!group_ptr) continue;
            got_group[sender] = 1;
            ++got_messages;

            string payload = reply.substr(sp + 1);
            int pos = 0;
            for (int p : *group_ptr) {
                string piece = payload.substr(pos, encoded_len[p]);
                pos += encoded_len[p];
                vector<char> bits = decode_bits(piece, assigned_count(e, agents, p));
                int idx = 0;
                for (int k = p; k < e; k += agents) open[k] = bits[idx++];
            }
        }

        string room_path;
        known_room_path(m, edges, open, room_path);
        claim_room_path(room_path);
    }

    int bits_per_message = choose_phase_bits(e, agents, chunk);
    vector<int> assigned(agents, 0);
    int phases = 0;
    for (int p = 0; p < agents; ++p) {
        assigned[p] = assigned_count(e, agents, p);
        phases = max(phases, (assigned[p] + bits_per_message - 1) / bits_per_message);
    }

    if (id != 0) {
        for (int phase = 0; phase < phases; ++phase) {
            int lo = phase * bits_per_message;
            if (lo >= assigned[id]) continue;
            int hi = min(assigned[id], lo + bits_per_message);
            vector<char> bits;
            bits.reserve(hi - lo);
            for (int j = lo; j < hi; ++j) {
                int k = id + j * 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');
            }
            command_with_reply("> 0 " + encode_bits(bits));
        }
        command_no_reply("halt");
        exit(0);
    }

    int vcount = m * m;
    vector<int> dsu(vcount), dsu_rank(vcount, 0);
    iota(dsu.begin(), dsu.end(), 0);
    auto find_root = [&](int x) {
        int y = x;
        while (dsu[y] != y) y = dsu[y];
        while (dsu[x] != x) {
            int p = dsu[x];
            dsu[x] = y;
            x = p;
        }
        return y;
    };
    auto add_known_open = [&](const Edge &edge) {
        int a = find_root(edge.u), b = find_root(edge.v);
        if (a == b) return;
        if (dsu_rank[a] < dsu_rank[b]) swap(a, b);
        dsu[b] = a;
        if (dsu_rank[a] == dsu_rank[b]) ++dsu_rank[a];
    };
    auto connected_known = [&]() {
        return find_root(0) == find_root(vcount - 1);
    };

    vector<char> open(e, 0);
    string room_path;
    for (int phase = 0; phase < phases; ++phase) {
        int lo = phase * bits_per_message;
        if (lo < assigned[0]) {
            int hi = min(assigned[0], lo + bits_per_message);
            for (int j = lo; j < hi; ++j) {
                int k = j * 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';
                if (open[k]) {
                    add_known_open(edge);
                    if (connected_known()) {
                        known_room_path(m, edges, open, room_path);
                        claim_room_path(room_path);
                    }
                }
            }
        }

        for (int p = 1; p < agents; ++p) {
            if (lo >= assigned[p]) continue;
            int hi = min(assigned[p], lo + bits_per_message);
            int need = hi - lo;
            string payload;
            while (true) {
                string reply = command_with_reply("< " + to_string(p));
                if (reply == "- -") continue;
                size_t sp = reply.find(' ');
                if (sp == string::npos) continue;
                int sender = stoi(reply.substr(0, sp));
                if (sender != p) continue;
                payload = reply.substr(sp + 1);
                break;
            }

            vector<char> bits = decode_bits(payload, need);
            int idx = 0;
            for (int j = lo; j < hi; ++j) {
                int k = p + j * agents;
                open[k] = bits[idx++];
                if (open[k]) add_known_open(edges[k]);
            }
            if (connected_known()) {
                known_room_path(m, edges, open, room_path);
                claim_room_path(room_path);
            }
        }
    }

    known_room_path(m, edges, open, room_path);
    claim_room_path(room_path);
}

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

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

    bool next_query(string &cmd, int &next_node, char &step) {
        while (!st.empty()) {
            int u = st.back().first;
            int target = side == 'G' ? 0 : m * m - 1;
            if (u == target) 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 {
        int target = side == 'G' ? 0 : m * m - 1;
        return !st.empty() && st.back().first == target;
    }

    string cell_path() const {
        string claim_room_path;
        if (side == 'S') {
            claim_room_path = room_path;
        } else {
            for (auto it = room_path.rbegin(); it != room_path.rend(); ++it) {
                char ch = *it;
                if (ch == 'D') claim_room_path.push_back('U');
                else if (ch == 'U') claim_room_path.push_back('D');
                else if (ch == 'R') claim_room_path.push_back('L');
                else claim_room_path.push_back('R');
            }
        }
        string path;
        path.reserve(claim_room_path.size() * 2);
        for (char ch : claim_room_path) {
            path.push_back(ch);
            path.push_back(ch);
        }
        return path;
    }
};

struct BestFirstState {
    struct Item {
        double key;
        int tie;
        int u, v, edge_id;
        char step;
        bool operator<(const Item &other) const {
            if (key != other.key) return key > other.key;
            return tie > other.tie;
        }
    };

    int n, m;
    char side;
    double weight, beta;
    vector<char> discovered;
    vector<char> queried;
    vector<int> parent;
    vector<int> depth;
    vector<char> parent_step;
    priority_queue<Item> pq;
    int seq = 0;

    BestFirstState(int n_, char side_, double weight_, double beta_)
        : n(n_), m((n_ + 1) / 2), side(side_), weight(weight_), beta(beta_),
          discovered(m * m, 0), queried(2 * m * max(0, m - 1), 0),
          parent(m * m, -1), depth(m * m, 0), parent_step(m * m, 0) {
        int root = side == 'G' ? m * m - 1 : 0;
        discovered[root] = 1;
        push_neighbors(root);
    }

    int target() const {
        return side == 'G' ? 0 : m * m - 1;
    }

    int edge_index(int u, int v) const {
        int a = min(u, v), b = max(u, v);
        int ai = a / m, aj = a % m;
        int bi = b / m, bj = b % m;
        if (ai != bi) return min(ai, bi) * m + aj;
        return (m - 1) * m + ai * (m - 1) + min(aj, bj);
    }

    double priority_key(int from, int to) const {
        int i = to / m, j = to % m;
        int ti = target() / m, tj = target() % m;
        int h = abs(i - ti) + abs(j - tj);
        int diagonal = abs(i - j);
        return (double)(depth[from] + 1) + weight * h + beta * diagonal;
    }

    void push_neighbors(int u) {
        static const array<pair<char, pair<int, int>>, 4> dirs = {{
            {'D', {1, 0}}, {'R', {0, 1}}, {'U', {-1, 0}}, {'L', {0, -1}}
        }};
        int i = u / m, j = u % m;
        for (auto [step, delta] : dirs) {
            int ni = i + delta.first, nj = j + delta.second;
            if (ni < 0 || ni >= m || nj < 0 || nj >= m) continue;
            int v = ni * m + nj;
            if (discovered[v]) continue;
            int eid = edge_index(u, v);
            if (queried[eid]) continue;
            pq.push({priority_key(u, v), seq++, u, v, eid, step});
        }
    }

    bool next_query(string &cmd, int &from, int &to, int &eid, char &step) {
        while (!pq.empty()) {
            Item item = pq.top();
            pq.pop();
            if (queried[item.edge_id] || discovered[item.v]) continue;
            queried[item.edge_id] = 1;
            int i = item.u / m, j = item.u % m;
            int rr = 2 * i + 1, cc = 2 * j + 1;
            if (item.step == 'D') ++rr;
            else if (item.step == 'U') --rr;
            else if (item.step == 'R') ++cc;
            else --cc;
            cmd = "? " + to_string(rr) + " " + to_string(cc);
            from = item.u;
            to = item.v;
            eid = item.edge_id;
            step = item.step;
            return true;
        }
        return false;
    }

    void accept_open(int from, int to, char step) {
        if (discovered[to]) return;
        discovered[to] = 1;
        parent[to] = from;
        parent_step[to] = step;
        depth[to] = depth[from] + 1;
        push_neighbors(to);
    }

    bool at_goal() const {
        return discovered[target()];
    }

    string cell_path() const {
        string room_path;
        if (side == 'S') {
            for (int cur = target(); cur != 0; cur = parent[cur]) room_path.push_back(parent_step[cur]);
            reverse(room_path.begin(), room_path.end());
        } else {
            for (int cur = 0; cur != m * m - 1; cur = parent[cur]) {
                char ch = parent_step[cur];
                if (ch == 'D') room_path.push_back('U');
                else if (ch == 'U') room_path.push_back('D');
                else if (ch == 'R') room_path.push_back('L');
                else room_path.push_back('R');
            }
        }
        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);
    }

    if (false && agents == 3 && id == 2) {
        BestFirstState search(n, 'S', 1.75, 0.10);
        while (true) {
            if (search.at_goal()) {
                claim_path(search.cell_path());
            }

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

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

    static const vector<pair<char, string>> strategies = {
        {'G', "LURD"}, {'S', "DRUL"}, {'S', "RDUL"}, {'G', "ULDR"},
        {'S', "DULR"}, {'G', "LDUR"}, {'S', "DLRU"}, {'S', "RDLU"}
    };
    DfsState dfs(n, id, max_msg_len, strategies[id % (int)strategies.size()].first,
                 strategies[id % (int)strategies.size()].second);
    while (true) {
        if (dfs.at_goal()) {
            claim_path(dfs.cell_path());
        }

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

        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 (n == 1) {
        if (id == 0) claim_path("");
        command_no_reply("halt");
        return 0;
    }

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