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

#ifndef EDGE_ORDER_STYLE
#define EDGE_ORDER_STYLE 1
#endif

#ifndef ASTAR_MAX_AGENTS
#define ASTAR_MAX_AGENTS 5
#endif

static const string BASE64_ALPHABET =
    "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/";

static bool use_dense_codec_for(int n, int num_agents) {
    if (num_agents <= ASTAR_MAX_AGENTS) return false;
    switch (n) {
        case 151:
            return num_agents == 6 || num_agents == 7;
        case 201:
            return 6 <= num_agents && num_agents <= 12;
        case 249:
            return 6 <= num_agents && num_agents <= 20 && num_agents != 10;
        case 301:
            return 6 <= num_agents && num_agents <= 24;
        case 351:
            return 6 <= num_agents && num_agents <= 30 &&
                   num_agents != 8 && num_agents != 10;
        case 401:
            return 6 <= num_agents && num_agents <= 30 && num_agents != 13;
        case 451:
            return ((7 <= num_agents && num_agents <= 21) ||
                    num_agents == 23 || num_agents == 24 ||
                    num_agents == 30 || num_agents == 50) &&
                   num_agents != 11;
        case 501:
            return (6 <= num_agents && num_agents <= 30) || num_agents == 50;
        default:
            return false;
    }
}

static string encode_bits(const vector<unsigned char> &bits, bool dense_codec) {
    if (!dense_codec) {
        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(BASE64_ALPHABET[val]);
                val = 0;
                cnt = 0;
            }
        }
        if (cnt) {
            val <<= (6 - cnt);
            out.push_back(BASE64_ALPHABET[val]);
        }
        return out;
    }

    string out;
    out.reserve(((bits.size() + 12) / 13) * 2);
    int val = 0, cnt = 0;
    for (unsigned char bit : bits) {
        val = (val << 1) | (bit & 1);
        ++cnt;
        if (cnt == 13) {
            out.push_back((char)(' ' + val / 95));
            out.push_back((char)(' ' + val % 95));
            val = 0;
            cnt = 0;
        }
    }
    if (cnt) {
        val <<= (13 - cnt);
        out.push_back((char)(' ' + val / 95));
        out.push_back((char)(' ' + val % 95));
    }
    return out;
}

static vector<unsigned char> decode_bits(const string &text, int need, bool dense_codec) {
    vector<unsigned char> bits;
    bits.reserve(need);
    if (!dense_codec) {
        for (char ch : text) {
            if ((int)bits.size() >= need) break;
            size_t pos = BASE64_ALPHABET.find(ch);
            if (pos == string::npos) continue;
            int v = (int)pos;
            for (int b = 5; b >= 0 && (int)bits.size() < need; --b) {
                bits.push_back((v >> b) & 1);
            }
        }
        return bits;
    }

    for (int i = 0; i + 1 < (int)text.size() && (int)bits.size() < need; i += 2) {
        int hi = (unsigned char)text[i] - ' ';
        int lo = (unsigned char)text[i + 1] - ' ';
        if (hi < 0 || hi >= 95 || lo < 0 || lo >= 95) continue;
        int v = hi * 95 + lo;
        for (int b = 12; 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;
    }

    bool small_scan = (num_agents == 5 && n <= 75);

    if (num_agents <= ASTAR_MAX_AGENTS && !small_scan) {
        run_bidirectional_astar(n, num_agents, agent_id);
    }

    int rooms = (n + 1) / 2;
    long long total_edges = 2LL * rooms * (rooms - 1);
    bool dense_codec = max_msg_len >= 2 && use_dense_codec_for(n, num_agents);
    int bits_per_msg = dense_codec ? (max_msg_len / 2) * 13 : max_msg_len * 6;
    bits_per_msg = max(1, bits_per_msg);

    auto message_count = [&](int bits) -> int {
        return bits == 0 ? 0 : (bits + bits_per_msg - 1) / bits_per_msg;
    };

    auto estimate_finish = [&](int active_agents, int q0) {
        if (active_agents == 1) return (long long)total_edges + 1;
        long long rem = total_edges - q0;
        int workers = active_agents - 1;
        int base = (int)(rem / workers);
        int extra = (int)(rem % workers);
        vector<int> availability;
        availability.reserve(128);
        for (int id = 1; id < active_agents; ++id) {
            int q = base + (id - 1 < extra ? 1 : 0);
            int chunks = message_count(q);
            for (int k = 1; k <= chunks; ++k) {
                int queried = min(q, k * bits_per_msg);
                availability.push_back(queried + k + 1);
            }
        }
        sort(availability.begin(), availability.end());
        long long turn = (long long)q0 + 1;
        for (int ready : availability) {
            if (turn < ready) turn = ready;
            ++turn;
        }
        return turn;
    };

    auto best_q0_for = [&](int active_agents) {
        int lo = 0, hi = (int)total_edges;
        while (hi - lo > 512) {
            int m1 = lo + (hi - lo) / 3;
            int m2 = hi - (hi - lo) / 3;
            if (estimate_finish(active_agents, m1) <= estimate_finish(active_agents, m2)) {
                hi = m2;
            } else {
                lo = m1;
            }
        }
        long long best_finish = LLONG_MAX;
        int best_q0 = 0;
        for (int q0 = lo; q0 <= hi; ++q0) {
            long long finish = estimate_finish(active_agents, q0);
            if (finish < best_finish) {
                best_finish = finish;
                best_q0 = q0;
            }
        }
        return pair<long long, int>{best_finish, best_q0};
    };

    int active_agents = num_agents;
    long long active_finish = LLONG_MAX;
    for (int k = 6; k <= num_agents; ++k) {
        auto [finish, q0] = best_q0_for(k);
        (void)q0;
        if (finish < active_finish || (finish == active_finish && k > active_agents)) {
            active_finish = finish;
            active_agents = k;
        }
    }
    if (agent_id >= active_agents) {
        cout << "halt" << '\n' << flush;
        return 0;
    }

    auto make_counts = [&]() {
        vector<int> best(active_agents, 0);
        if (active_agents == 1) {
            best[0] = (int)total_edges;
            return best;
        }
        auto [best_finish, q0] = best_q0_for(active_agents);
        (void)best_finish;
        long long rem = total_edges - q0;
        int workers = active_agents - 1;
        int base = (int)(rem / workers);
        int extra = (int)(rem % workers);
        best[0] = q0;
        for (int id = 1; id < active_agents; ++id) {
            best[id] = base + (id - 1 < extra ? 1 : 0);
        }
        return best;
    };

    vector<int> counts = make_counts();
    vector<long long> starts(active_agents + 1, 0);
    for (int id = 0; id < active_agents; ++id) {
        starts[id + 1] = starts[id] + counts[id];
    }

    vector<int> edge_from;
    vector<int> edge_to;
    vector<char> edge_dir;
    edge_from.reserve((int)total_edges);
    edge_to.reserve((int)total_edges);
    edge_dir.reserve((int)total_edges);
    for (int i = 0; i < rooms; ++i) {
        for (int j = 0; j < rooms; ++j) {
            int id = i * rooms + j;
            if (i + 1 < rooms) {
                edge_from.push_back(id);
                edge_to.push_back(id + rooms);
                edge_dir.push_back('D');
            }
            if (j + 1 < rooms) {
                edge_from.push_back(id);
                edge_to.push_back(id + 1);
                edge_dir.push_back('R');
            }
        }
    }
    vector<int> edge_order((int)total_edges);
    iota(edge_order.begin(), edge_order.end(), 0);
    sort(edge_order.begin(), edge_order.end(), [&](int a, int b) {
        int ar = edge_from[a] / rooms, ac = edge_from[a] % rooms;
        int br = edge_to[a] / rooms, bc = edge_to[a] % rooms;
        int cr = edge_from[b] / rooms, cc = edge_from[b] % rooms;
        int dr2 = edge_to[b] / rooms, dc2 = edge_to[b] % rooms;
#if EDGE_ORDER_STYLE == 2
        int aband = max(abs(ar - ac), abs(br - bc));
        int bband = max(abs(cr - cc), abs(dr2 - dc2));
        if (aband != bband) return aband < bband;
        int aend = min(ar + ac, 2 * (rooms - 1) - (br + bc));
        int bend = min(cr + cc, 2 * (rooms - 1) - (dr2 + dc2));
        if (aend != bend) return aend < bend;
#elif EDGE_ORDER_STYLE == 3
        int aband = min(abs(ar - ac), abs(br - bc));
        int bband = min(abs(cr - cc), abs(dr2 - dc2));
        if (aband != bband) return aband < bband;
        int asum = min(ar + ac, br + bc);
        int bsum = min(cr + cc, dr2 + dc2);
        if (asum != bsum) return asum < bsum;
#else
        int aband = min(abs(ar - ac), abs(br - bc));
        int bband = min(abs(cr - cc), abs(dr2 - dc2));
        if (aband != bband) return aband < bband;
        int amid = min(abs(ar + ac - (rooms - 1)), abs(br + bc - (rooms - 1)));
        int bmid = min(abs(cr + cc - (rooms - 1)), abs(dr2 + dc2 - (rooms - 1)));
        if (amid != bmid) return amid < bmid;
#endif
        return a < b;
    });
    vector<int> old_from = edge_from, old_to = edge_to;
    vector<char> old_dir = edge_dir;
    for (int i = 0; i < (int)total_edges; ++i) {
        edge_from[i] = old_from[edge_order[i]];
        edge_to[i] = old_to[edge_order[i]];
        edge_dir[i] = old_dir[edge_order[i]];
    }

    vector<unsigned char> my_bits;
    my_bits.reserve(counts[agent_id]);
    vector<unsigned char> chunk_bits;
    chunk_bits.reserve(bits_per_msg);

    for (long long edge_idx = starts[agent_id]; edge_idx < starts[agent_id + 1]; ++edge_idx) {
        int from = edge_from[(int)edge_idx];
        int r = from / rooms;
        int c = from % rooms;
        int qr = 2 * r + 1 + (edge_dir[(int)edge_idx] == 'D' ? 1 : 0);
        int qc = 2 * c + 1 + (edge_dir[(int)edge_idx] == 'R' ? 1 : 0);
        unsigned char bit = query_cell(qr, qc) ? 1 : 0;
        my_bits.push_back(bit);
        if (agent_id != 0) {
            chunk_bits.push_back(bit);
            if ((int)chunk_bits.size() == bits_per_msg) {
                send_msg(0, encode_bits(chunk_bits, dense_codec));
                chunk_bits.clear();
            }
        }
    }

    if (agent_id != 0) {
        if (!chunk_bits.empty()) {
            send_msg(0, encode_bits(chunk_bits, dense_codec));
        }
        cout << "halt" << '\n' << flush;
        return 0;
    }

    int start = 0, goal = rooms * rooms - 1;
    vector<vector<pair<int, char>>> graph(rooms * rooms);
    vector<int> dsu_parent(rooms * rooms), dsu_rank(rooms * rooms, 0);
    iota(dsu_parent.begin(), dsu_parent.end(), 0);

    auto dsu_find = [&](int x) {
        int root = x;
        while (dsu_parent[root] != root) root = dsu_parent[root];
        while (dsu_parent[x] != x) {
            int next = dsu_parent[x];
            dsu_parent[x] = root;
            x = next;
        }
        return root;
    };

    auto dsu_unite = [&](int a, int b) {
        int ra = dsu_find(a), rb = dsu_find(b);
        if (ra == rb) return;
        if (dsu_rank[ra] < dsu_rank[rb]) swap(ra, rb);
        dsu_parent[rb] = ra;
        if (dsu_rank[ra] == dsu_rank[rb]) ++dsu_rank[ra];
    };

    auto claim_if_connected = [&]() {
        if (dsu_find(start) != dsu_find(goal)) return;
        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) return;

        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;
        exit(0);
    };

    vector<int> processed(active_agents, 0);
    auto process_bit = [&](int owner_id, unsigned char bit) {
        int offset = processed[owner_id]++;
        if (!bit) return;
        int edge = (int)starts[owner_id] + offset;
        int a = edge_from[edge], b = edge_to[edge];
        char dir = edge_dir[edge];
        graph[a].push_back({b, dir});
        graph[b].push_back({a, opposite_dir(dir)});
        dsu_unite(a, b);
    };

    for (unsigned char bit : my_bits) {
        process_bit(0, bit);
    }
    claim_if_connected();

    int remaining_messages = 0;
    for (int id = 1; id < active_agents; ++id) {
        remaining_messages += message_count(counts[id]);
    }

    while (remaining_messages > 0) {
        auto [sender, body] = recv_any();
        if (sender < 0) continue;
        if (sender >= 1 && sender < active_agents) {
            int need = min(bits_per_msg, counts[sender] - processed[sender]);
            vector<unsigned char> bits = decode_bits(body, need, dense_codec);
            for (unsigned char bit : bits) {
                process_bit(sender, bit);
            }
            claim_if_connected();
            --remaining_messages;
        }
    }
    claim_if_connected();
    cout << "halt" << '\n' << flush;
    return 0;
}