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

static const string ALPHABET =
    "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz-_";

static string encode_bits(const vector<unsigned char> &bits) {
    string out;
    out.reserve((bits.size() + 5) / 6);
    int val = 0, cnt = 0;
    for (unsigned char bit : bits) {
        val = (val << 1) | (bit & 1);
        ++cnt;
        if (cnt == 6) {
            out.push_back(ALPHABET[val]);
            val = 0;
            cnt = 0;
        }
    }
    if (cnt) {
        val <<= (6 - cnt);
        out.push_back(ALPHABET[val]);
    }
    return out;
}

static vector<unsigned char> decode_bits(const string &text, int need) {
    static array<int, 256> dec = [] {
        array<int, 256> a{};
        a.fill(-1);
        for (int i = 0; i < (int)ALPHABET.size(); ++i) {
            a[(unsigned char)ALPHABET[i]] = i;
        }
        return a;
    }();

    vector<unsigned char> bits;
    bits.reserve(need);
    for (unsigned char ch : text) {
        int v = dec[ch];
        if (v < 0) continue;
        for (int b = 5; b >= 0 && (int)bits.size() < need; --b) {
            bits.push_back((v >> b) & 1);
        }
    }
    return bits;
}

static bool query_cell(int r, int c) {
    cout << "? " << r << ' ' << c << '\n' << flush;
    string reply;
    if (!(cin >> reply)) exit(0);
    return reply == "1";
}

static void send_msg(int to, const string &body) {
    cout << "> " << to << ' ' << body << '\n' << flush;
    string reply;
    if (!(cin >> reply)) exit(0);
}

static pair<int, string> recv_any() {
    cout << "< ?" << '\n' << flush;
    string sender;
    if (!(cin >> sender)) exit(0);
    string body;
    getline(cin, body);
    if (!body.empty() && body[0] == ' ') body.erase(body.begin());
    if (sender == "-") return {-1, ""};
    return {stoi(sender), body};
}

struct AStarEdge {
    long long score;
    uint64_t tie;
    int side;
    int from;
    int to;
    int dir_idx;
    char ch;
    bool operator<(const AStarEdge &o) const {
        if (score != o.score) return score > o.score;
        return tie > o.tie;
    }
};

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

static uint64_t splitmix64(uint64_t x) {
    x += 0x9e3779b97f4a7c15ULL;
    x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9ULL;
    x = (x ^ (x >> 27)) * 0x94d049bb133111ebULL;
    return x ^ (x >> 31);
}

static void run_bidirectional_astar(int n, int num_agents, int agent_id) {
    (void)num_agents;
    int rooms = (n + 1) / 2;
    int total = rooms * rooms;
    auto node_id = [rooms](int r, int c) { return r * rooms + c; };
    auto row = [rooms](int v) { return v / rooms; };
    auto col = [rooms](int v) { return v % rooms; };

    const int dr[4] = {-1, 1, 0, 0};
    const int dc[4] = {0, 0, -1, 1};
    const char dch[4] = {'U', 'D', 'L', 'R'};
    const int rev[4] = {1, 0, 3, 2};

    vector<pair<int, int>> profiles = {
        {1000000, 1}, {262144, 4096}, {65536, 4096},
        {16384, 4096}, {4096, 4096},
    };
    auto [weight, noise] = profiles[agent_id % (int)profiles.size()];
    uint64_t salt =
        splitmix64(0xA57A5A7A0DDF00DULL + (uint64_t)agent_id * 0x9e3779b97f4a7c15ULL);

    vector<array<signed char, 4>> edge_state(total);
    for (auto &a : edge_state) a.fill(-1);
    vector<array<unsigned char, 2>> seen(total);
    vector<array<int, 2>> parent(total);
    vector<array<char, 2>> parent_dir(total);
    vector<array<int, 2>> dist(total);
    for (int i = 0; i < total; ++i) {
        seen[i] = {0, 0};
        parent[i] = {-1, -1};
        parent_dir[i] = {0, 0};
        dist[i] = {0, 0};
    }

    int start = node_id(0, 0);
    int goal = node_id(rooms - 1, rooms - 1);
    seen[start][0] = 1;
    seen[goal][1] = 1;
    parent[start][0] = start;
    parent[goal][1] = goal;

    auto heuristic = [&](int side, int v) {
        int tr = side == 0 ? rooms - 1 : 0;
        int tc = side == 0 ? rooms - 1 : 0;
        return abs(row(v) - tr) + abs(col(v) - tc);
    };

    priority_queue<AStarEdge> pq;

    auto push_from = [&](int side, int v) {
        int r = row(v), c = col(v);
        for (int k = 0; k < 4; ++k) {
            int nr = r + dr[k], nc = c + dc[k];
            if (nr < 0 || nr >= rooms || nc < 0 || nc >= rooms) continue;
            int to = node_id(nr, nc);
            if (seen[to][side]) continue;
            if (edge_state[v][k] == 0) continue;
            uint64_t tie =
                splitmix64(salt ^ (uint64_t)(side * 2000003 + v * 37 + k * 10007 + to));
            long long score = (long long)(dist[v][side] + 1) * 1024LL +
                              (long long)heuristic(side, to) * weight;
            if (noise) score += (long long)(tie % (uint64_t)noise);
            pq.push({score, tie, side, v, to, k, dch[k]});
        }
    };

    auto side_path = [&](int side, int v) {
        string path;
        while (parent[v][side] != v) {
            path.push_back(parent_dir[v][side]);
            v = parent[v][side];
        }
        reverse(path.begin(), path.end());
        return path;
    };

    auto claim = [&](int meet) {
        string a = side_path(0, meet);
        string b = side_path(1, meet);
        string room_moves = a;
        for (int i = (int)b.size() - 1; i >= 0; --i) {
            room_moves.push_back(opposite_dir(b[i]));
        }
        string moves;
        moves.reserve(room_moves.size() * 2);
        for (char ch : room_moves) {
            moves.push_back(ch);
            moves.push_back(ch);
        }
        cout << "! " << moves << '\n' << flush;
        exit(0);
    };

    push_from(0, start);
    push_from(1, goal);

    while (!pq.empty()) {
        AStarEdge e = pq.top();
        pq.pop();
        if (!seen[e.from][e.side] || seen[e.to][e.side]) continue;
        signed char open = edge_state[e.from][e.dir_idx];
        if (open < 0) {
            int r = row(e.from), c = col(e.from);
            open = query_cell(2 * r + 1 + dr[e.dir_idx], 2 * c + 1 + dc[e.dir_idx]) ? 1 : 0;
            edge_state[e.from][e.dir_idx] = open;
            edge_state[e.to][rev[e.dir_idx]] = open;
        }
        if (!open) continue;
        seen[e.to][e.side] = 1;
        parent[e.to][e.side] = e.from;
        parent_dir[e.to][e.side] = e.ch;
        dist[e.to][e.side] = dist[e.from][e.side] + 1;
        if (seen[e.to][e.side ^ 1]) claim(e.to);
        push_from(e.side, e.to);
    }

    cout << "halt" << '\n' << flush;
    exit(0);
}

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 << "! " << '\n' << flush;
        } else {
            cout << "halt" << '\n' << flush;
        }
        return 0;
    }

    if (num_agents <= 5) {
        run_bidirectional_astar(n, num_agents, agent_id);
    }

    int rooms = (n + 1) / 2;
    long long total_edges = 2LL * rooms * (rooms - 1);

    auto owner_count = [&](int owner) -> int {
        if (owner >= total_edges) return 0;
        return (int)((total_edges - 1 - owner) / num_agents + 1);
    };

    vector<unsigned char> my_bits;
    my_bits.reserve(owner_count(agent_id));

    long long edge_idx = 0;
    for (int i = 0; i < rooms; ++i) {
        for (int j = 0; j < rooms; ++j) {
            int r = 2 * i + 1;
            int c = 2 * j + 1;
            if (i + 1 < rooms) {
                if (edge_idx % num_agents == agent_id) {
                    my_bits.push_back(query_cell(r + 1, c) ? 1 : 0);
                }
                ++edge_idx;
            }
            if (j + 1 < rooms) {
                if (edge_idx % num_agents == agent_id) {
                    my_bits.push_back(query_cell(r, c + 1) ? 1 : 0);
                }
                ++edge_idx;
            }
        }
    }

    if (agent_id != 0) {
        string encoded = encode_bits(my_bits);
        int chunk = max(1, max_msg_len);
        for (int pos = 0; pos < (int)encoded.size(); pos += chunk) {
            send_msg(0, encoded.substr(pos, chunk));
        }
        cout << "halt" << '\n' << flush;
        return 0;
    }

    vector<string> encoded_by_agent(num_agents);
    encoded_by_agent[0] = encode_bits(my_bits);

    vector<int> expected_chars(num_agents, 0);
    int remaining_messages = 0;
    for (int id = 1; id < num_agents; ++id) {
        int chars = (owner_count(id) + 5) / 6;
        expected_chars[id] = chars;
        remaining_messages += (chars + max(1, max_msg_len) - 1) / max(1, max_msg_len);
    }

    while (remaining_messages > 0) {
        auto [sender, body] = recv_any();
        if (sender < 0) continue;
        if (sender >= 1 && sender < num_agents) {
            encoded_by_agent[sender] += body;
            --remaining_messages;
        }
    }

    vector<vector<unsigned char>> bits_by_agent(num_agents);
    vector<int> bit_pos(num_agents, 0);
    for (int id = 0; id < num_agents; ++id) {
        bits_by_agent[id] = decode_bits(encoded_by_agent[id], owner_count(id));
    }

    vector<vector<pair<int, char>>> graph(rooms * rooms);
    auto add_edge = [&](int a, int b, char dir) {
        graph[a].push_back({b, dir});
        char rev = (dir == 'D' ? 'U' : dir == 'U' ? 'D' : dir == 'R' ? 'L' : 'R');
        graph[b].push_back({a, rev});
    };

    edge_idx = 0;
    for (int i = 0; i < rooms; ++i) {
        for (int j = 0; j < rooms; ++j) {
            int id = i * rooms + j;
            if (i + 1 < rooms) {
                int owner = (int)(edge_idx % num_agents);
                bool open = bit_pos[owner] < (int)bits_by_agent[owner].size() &&
                            bits_by_agent[owner][bit_pos[owner]++];
                if (open) add_edge(id, id + rooms, 'D');
                ++edge_idx;
            }
            if (j + 1 < rooms) {
                int owner = (int)(edge_idx % num_agents);
                bool open = bit_pos[owner] < (int)bits_by_agent[owner].size() &&
                            bits_by_agent[owner][bit_pos[owner]++];
                if (open) add_edge(id, id + 1, 'R');
                ++edge_idx;
            }
        }
    }

    int start = 0, goal = rooms * rooms - 1;
    vector<int> parent(rooms * rooms, -1);
    vector<char> parent_dir(rooms * rooms, 0);
    queue<int> q;
    parent[start] = start;
    q.push(start);
    while (!q.empty() && parent[goal] == -1) {
        int v = q.front();
        q.pop();
        for (auto [to, dir] : graph[v]) {
            if (parent[to] == -1) {
                parent[to] = v;
                parent_dir[to] = dir;
                q.push(to);
            }
        }
    }

    if (parent[goal] == -1) {
        cout << "halt" << '\n' << flush;
        return 0;
    }

    string room_path;
    for (int v = goal; v != start; v = parent[v]) {
        room_path.push_back(parent_dir[v]);
    }
    reverse(room_path.begin(), room_path.end());

    string moves;
    moves.reserve(room_path.size() * 2);
    for (char dir : room_path) {
        moves.push_back(dir);
        moves.push_back(dir);
    }

    cout << "! " << moves << '\n' << flush;
    return 0;
}