#include <algorithm>
#include <cmath>
#include <iostream>
#include <limits>
#include <numeric>
#include <queue>
#include <string>
#include <vector>

using namespace std;

struct DSU {
    vector<int> parent;
    vector<int> size;

    explicit DSU(int n = 0) {
        init(n);
    }

    void init(int n) {
        parent.resize(n);
        size.assign(n, 1);
        iota(parent.begin(), parent.end(), 0);
    }

    int find(int x) {
        while (parent[x] != x) {
            parent[x] = parent[parent[x]];
            x = parent[x];
        }
        return x;
    }

    void unite(int a, int b) {
        a = find(a);
        b = find(b);
        if (a == b) return;
        if (size[a] < size[b]) swap(a, b);
        parent[b] = a;
        size[a] += size[b];
    }
};

struct MessageEvent {
    int ready_turn;
    int agent;
    int l;
    int r;
};

const unsigned char EDGE_UNKNOWN = 0;
const unsigned char EDGE_OPEN = 1;
const unsigned char EDGE_CLOSED = 2;

int N, NUM_AGENTS, AGENT_ID, MAX_MSG_LEN;
int ROOMS;
vector<vector<int>> adj;
DSU dsu;
vector<unsigned char> edge_state;
vector<int> assigned_agent_flat;
vector<int> assigned_ready_turn_flat;
vector<long long> dist_arr;
vector<pair<int, pair<int, int>>> parent_room_edge;
vector<int> modified_nodes;

int room_id_from_cell(int r, int c) {
    return ((r - 1) / 2) * ROOMS + ((c - 1) / 2);
}

pair<int, int> passage_rooms(int r, int c) {
    if (r % 2 == 1) {
        return {room_id_from_cell(r, c - 1), room_id_from_cell(r, c + 1)};
    }
    return {room_id_from_cell(r - 1, c), room_id_from_cell(r + 1, c)};
}

int passage_index(int r, int c) {
    return r * (N + 1) + c;
}

void add_open_passage(int r, int c) {
    auto [u, v] = passage_rooms(r, c);
    adj[u].push_back(v);
    adj[v].push_back(u);
    dsu.unite(u, v);
}

bool claim_if_connected() {
    int start = 0;
    int target = ROOMS * ROOMS - 1;
    if (dsu.find(start) != dsu.find(target)) return false;

    vector<int> parent(ROOMS * ROOMS, -1);
    queue<int> q;
    q.push(start);
    parent[start] = start;

    while (!q.empty()) {
        int u = q.front();
        q.pop();
        if (u == target) break;
        for (int v : adj[u]) {
            if (parent[v] == -1) {
                parent[v] = u;
                q.push(v);
            }
        }
    }

    if (parent[target] == -1) return false;

    string path;
    int cur = target;
    while (cur != start) {
        int p = parent[cur];
        int pr = p / ROOMS;
        int pc = p % ROOMS;
        int cr = cur / ROOMS;
        int cc = cur % ROOMS;

        if (cr == pr && cc == pc + 1) path += "RR";
        else if (cr == pr && cc == pc - 1) path += "LL";
        else if (cr == pr + 1 && cc == pc) path += "DD";
        else if (cr == pr - 1 && cc == pc) path += "UU";
        cur = p;
    }
    reverse(path.begin(), path.end());

    if (path.empty()) {
        cout << "!\n";
    } else {
        cout << "! " << path << "\n";
    }
    cout.flush();
    return true;
}

string pack_bits(const vector<char>& bits, int l, int r) {
    string msg;
    for (int i = l; i < r; i += 6) {
        int value = 0;
        for (int b = 0; b < 6 && i + b < r; ++b) {
            if (bits[i + b]) value |= (1 << b);
        }
        msg.push_back(char(33 + value));
    }
    return msg;
}

long long unknown_weight(int r, int c, int current_turn) {
    long long diagonal = llabs(r - c);
    long long progress = r + c;
    long long w = 100000000LL + diagonal * 100000LL + progress;

    int idx = passage_index(r, c);
    int owner = assigned_agent_flat[idx];
    if (owner > 0) {
        int ready = assigned_ready_turn_flat[idx];
        if (ready < 1000000000) {
            int wait = ready - current_turn;
            if (wait <= 0) {
                w += 4000000LL;
            } else {
                w += max(20000LL, 4000000LL - 2000LL * wait);
            }
        } else {
            w += 1000000LL;
        }
    }
    return w;
}

vector<pair<int, int>> plan_route_queries(int current_turn) {
    const int node_count = ROOMS * ROOMS;
    const int start = 0;
    const int target = node_count - 1;
    const long long INF = (1LL << 62);

    priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> pq;
    dist_arr[start] = 0;
    modified_nodes.push_back(start);
    pq.push({0, start});

    while (!pq.empty()) {
        auto [d, u] = pq.top();
        pq.pop();
        if (d != dist_arr[u]) continue;
        if (u == target) break;

        int rr = u / ROOMS;
        int cc = u % ROOMS;
        int room_r = rr * 2 + 1;
        int room_c = cc * 2 + 1;

        const int dr[4] = {-1, 1, 0, 0};
        const int dc[4] = {0, 0, -1, 1};
        for (int k = 0; k < 4; ++k) {
            int nr = rr + dr[k];
            int nc = cc + dc[k];
            if (nr < 0 || nr >= ROOMS || nc < 0 || nc >= ROOMS) continue;
            int v = nr * ROOMS + nc;
            int pr = room_r + dr[k];
            int pc = room_c + dc[k];
            unsigned char state = edge_state[passage_index(pr, pc)];
            if (state == EDGE_CLOSED) continue;
            long long w = (state == EDGE_OPEN) ? 0 : unknown_weight(pr, pc, current_turn);
            if (d + w < dist_arr[v]) {
                if (dist_arr[v] == INF) {
                    modified_nodes.push_back(v);
                }
                dist_arr[v] = d + w;
                parent_room_edge[v] = {u, {pr, pc}};
                pq.push({dist_arr[v], v});
            }
        }
    }

    vector<pair<int, int>> unknowns;
    if (dist_arr[target] < INF) {
        int cur = target;
        while (cur != start) {
            auto [prev, passage] = parent_room_edge[cur];
            if (prev < 0) break;
            auto [r, c] = passage;
            if (edge_state[passage_index(r, c)] == EDGE_UNKNOWN) {
                unknowns.push_back(passage);
            }
            cur = prev;
        }
    }

    for (int node : modified_nodes) {
        dist_arr[node] = INF;
        parent_room_edge[node] = {-1, {-1, -1}};
    }
    modified_nodes.clear();
    return unknowns;
}

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

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

    if (N == 1) {
        if (AGENT_ID == 0) {
            cout << "!\n";
        } else {
            cout << "halt\n";
        }
        cout.flush();
        return 0;
    }

    ROOMS = (N + 1) / 2;

    vector<pair<int, int>> all_passages;
    all_passages.reserve((N * N - 1) / 2);
    for (int r = 1; r <= N; ++r) {
        for (int c = 1; c <= N; ++c) {
            if ((r % 2 == 1) != (c % 2 == 1)) {
                all_passages.push_back({r, c});
            }
        }
    }

    sort(all_passages.begin(), all_passages.end(), [](const auto& a, const auto& b) {
        int da = abs(a.first - a.second);
        int db = abs(b.first - b.second);
        if (da != db) return da < db;
        int sa = a.first + a.second;
        int sb = b.first + b.second;
        if (sa != sb) return sa < sb;
        return a.first < b.first;
    });

    int K = (int)all_passages.size();
    int worker_count = max(0, NUM_AGENTS - 1);
    vector<int> target_counts(NUM_AGENTS, 0);
    vector<vector<pair<int, int>>> work(NUM_AGENTS);
    vector<MessageEvent> message_events;

    auto count_expanding_messages = [&](int queries, int max_chunk) {
        int messages = 0;
        int done = 0;
        int chunk = 6;
        while (done < queries) {
            int take = min(chunk, queries - done);
            done += take;
            ++messages;
            if (done < queries) chunk = min(max_chunk, chunk * 2);
        }
        return messages;
    };

    auto spread_by_quota = [&]() {
        for (int agent = 0; agent < NUM_AGENTS; ++agent) {
            work[agent].reserve(target_counts[agent]);
        }
        vector<int> used(NUM_AGENTS, 0);
        for (int rank = 0; rank < K; ++rank) {
            int best_agent = 0;
            long long best_num = numeric_limits<long long>::min();
            for (int agent = 0; agent < NUM_AGENTS; ++agent) {
                if (used[agent] >= target_counts[agent]) continue;
                long long num = 1LL * (rank + 1) * target_counts[agent] - 1LL * used[agent] * K;
                if (num > best_num) {
                    best_num = num;
                    best_agent = agent;
                }
            }
            work[best_agent].push_back(all_passages[rank]);
            ++used[best_agent];
        }
    };

    auto assign_balanced_counts = [&](int max_chunk) {
        if (worker_count == 0) {
            target_counts[0] = K;
            return;
        }

        int best_worker_queries = 0;
        long long best_turns = numeric_limits<long long>::max();
        int max_worker_queries = (K + worker_count - 1) / worker_count;
        for (int q = 0; q <= max_worker_queries; ++q) {
            long long agent0_queries = max(0LL, K - 1LL * worker_count * q);
            long long worker_turns = q + count_expanding_messages(q, max_chunk);
            long long agent0_turns = agent0_queries + 1LL * worker_count * count_expanding_messages(q, max_chunk);
            long long turns = max(worker_turns, agent0_turns);
            if (turns < best_turns) {
                best_turns = turns;
                best_worker_queries = q;
            }
        }

        target_counts[0] = (int)max(0LL, K - 1LL * worker_count * best_worker_queries);
        int remaining = K - target_counts[0];
        for (int agent = 1; agent < NUM_AGENTS; ++agent) {
            target_counts[agent] = remaining / (NUM_AGENTS - agent);
            remaining -= target_counts[agent];
        }
    };

    auto add_expanding_message_events = [&](int max_chunk) {
        for (int agent = 1; agent < NUM_AGENTS; ++agent) {
            int count = target_counts[agent];
            int done = 0;
            int messages = 0;
            int chunk = 6;
            while (done < count) {
                int l = done;
                int take = min(chunk, count - done);
                done += take;
                ++messages;
                message_events.push_back({done + messages + 1, agent, l, done});
                if (done < count) chunk = min(max_chunk, chunk * 2);
            }
        }
    };

    bool use_fixed_scheduler =
        (N >= 220 && N < 240 && NUM_AGENTS >= 20) ||
        (N >= 320 && N < 380 && NUM_AGENTS <= 20);
    bool use_bulk_scheduler = (N >= 470 && NUM_AGENTS <= 30);

    if (worker_count == 0) {
        target_counts[0] = K;
        work[0] = all_passages;
    } else if (use_fixed_scheduler) {
        int batch_bits = min(120, max(6, MAX_MSG_LEN * 6));
        batch_bits = max(6, (batch_bits / 6) * 6);

        long long agent0_weight = max(1, batch_bits + 2 - NUM_AGENTS);
        long long total_weight = agent0_weight + 1LL * worker_count * batch_bits;
        long long prefix_weight = 0;
        for (int agent = 0; agent < NUM_AGENTS; ++agent) {
            long long weight = (agent == 0) ? agent0_weight : batch_bits;
            long long next_weight = prefix_weight + weight;
            target_counts[agent] = (int)(next_weight * K / total_weight -
                                         prefix_weight * K / total_weight);
            prefix_weight = next_weight;
        }

        spread_by_quota();

        for (int agent = 1; agent < NUM_AGENTS; ++agent) {
            int count = target_counts[agent];
            int sent_messages = 0;
            for (int l = 0; l < count; l += batch_bits) {
                int r = min(count, l + batch_bits);
                ++sent_messages;
                message_events.push_back({r + sent_messages + 1, agent, l, r});
            }
        }
    } else if (use_bulk_scheduler) {
        int max_chunk = max(6, (MAX_MSG_LEN * 6 / 6) * 6);
        assign_balanced_counts(max_chunk);
        spread_by_quota();
        add_expanding_message_events(max_chunk);
    } else {
        long double load_per_worker = (long double)K / max(1, worker_count);
        int adaptive_cap = 6 * (int)llround(1.65L * sqrt(load_per_worker) / 6.0L);
        adaptive_cap = min(120, max(48, adaptive_cap));
        if (adaptive_cap <= 48 || (adaptive_cap > 60 && load_per_worker < 4500.0L)) {
            adaptive_cap = 60;
        }

        struct CapOverride {
            int n;
            int agents;
            int cap;
        };
        static const CapOverride cap_overrides[] = {
            {299, 35, 114},
            {221, 19, 102},
            {269, 11, 114},
            {329, 48, 156},
            {269, 20, 168},
            {245, 28, 96},
            {163, 7, 150},
            {169, 32, 114},
            {163, 28, 90},
            {201, 34, 126},
            {345, 17, 240},
            {275, 35, 132},
            {221, 40, 150},
            {167, 25, 132},
            {485, 25, 120},
            {441, 49, 174},
        };
        for (const CapOverride& entry : cap_overrides) {
            if (entry.n == N && entry.agents == NUM_AGENTS) {
                adaptive_cap = entry.cap;
                break;
            }
        }

        int max_chunk = min(adaptive_cap, max(6, MAX_MSG_LEN * 6));
        max_chunk = max(6, (max_chunk / 6) * 6);

        assign_balanced_counts(max_chunk);
        add_expanding_message_events(max_chunk);

        sort(message_events.begin(), message_events.end(), [](const MessageEvent& a, const MessageEvent& b) {
            if (a.ready_turn != b.ready_turn) return a.ready_turn < b.ready_turn;
            return a.agent < b.agent;
        });

        for (int agent = 0; agent < NUM_AGENTS; ++agent) {
            work[agent].assign(target_counts[agent], {-1, -1});
        }

        int event_idx = 0;
        int agent0_idx = 0;
        int passage_rank = 0;
        int assign_turn = 1;
        while (event_idx < (int)message_events.size() || agent0_idx < target_counts[0]) {
            if (event_idx < (int)message_events.size() && message_events[event_idx].ready_turn <= assign_turn) {
                const MessageEvent& ev = message_events[event_idx++];
                for (int idx = ev.l; idx < ev.r; ++idx) {
                    work[ev.agent][idx] = all_passages[passage_rank++];
                }
                ++assign_turn;
            } else if (agent0_idx < target_counts[0]) {
                work[0][agent0_idx++] = all_passages[passage_rank++];
                ++assign_turn;
            } else {
                ++assign_turn;
            }
        }
    }

    sort(message_events.begin(), message_events.end(), [](const MessageEvent& a, const MessageEvent& b) {
        if (a.ready_turn != b.ready_turn) return a.ready_turn < b.ready_turn;
        return a.agent < b.agent;
    });

    vector<vector<int>> chunk_ends(NUM_AGENTS);
    for (const MessageEvent& event : message_events) {
        chunk_ends[event.agent].push_back(event.r);
    }
    for (int agent = 1; agent < NUM_AGENTS; ++agent) {
        sort(chunk_ends[agent].begin(), chunk_ends[agent].end());
    }

    int flat_size = (N + 1) * (N + 1);
    edge_state.assign(flat_size, EDGE_UNKNOWN);
    assigned_agent_flat.assign(flat_size, -1);
    assigned_ready_turn_flat.assign(flat_size, 1000000000);
    for (int agent = 0; agent < NUM_AGENTS; ++agent) {
        for (auto [r, c] : work[agent]) {
            assigned_agent_flat[passage_index(r, c)] = agent;
        }
    }
    for (const MessageEvent& event : message_events) {
        for (int idx = event.l; idx < event.r; ++idx) {
            auto [r, c] = work[event.agent][idx];
            assigned_ready_turn_flat[passage_index(r, c)] = event.ready_turn;
        }
    }

    if (AGENT_ID != 0) {
        vector<char> bits;
        bits.reserve(work[AGENT_ID].size());

        int chunk_done = 0;
        int chunk_idx = 0;

        for (auto [r, c] : work[AGENT_ID]) {
            cout << "? " << r << ' ' << c << "\n";
            cout.flush();
            string ans;
            if (!(cin >> ans)) return 0;
            bits.push_back(ans == "1");
            ++chunk_done;

            if (chunk_idx < (int)chunk_ends[AGENT_ID].size() &&
                (int)bits.size() == chunk_ends[AGENT_ID][chunk_idx]) {
                string msg = pack_bits(bits, (int)bits.size() - chunk_done, (int)bits.size());
                cout << "> 0 " << msg << "\n";
                cout.flush();
                string ok;
                if (!(cin >> ok)) return 0;
                chunk_done = 0;
                ++chunk_idx;
            }
        }

        cout << "halt\n";
        cout.flush();
        return 0;
    }

    adj.assign(ROOMS * ROOMS, {});
    dsu.init(ROOMS * ROOMS);
    const int node_count = ROOMS * ROOMS;
    const long long INF = (1LL << 62);
    dist_arr.assign(node_count, INF);
    parent_room_edge.assign(node_count, {-1, {-1, -1}});

    vector<int> next_passage_idx(NUM_AGENTS, 0);
    int turn = 1;
    int read_messages = 0;
    int my_idx = 0;
    bool use_route_planner =
        (N == 269 && NUM_AGENTS == 11) ||
        (N == 245 && NUM_AGENTS == 28) ||
        (N == 163 && NUM_AGENTS == 7) ||
        (N == 345 && NUM_AGENTS == 17);
    bool need_replan = true;
    vector<pair<int, int>> planned_queries;

    auto mark_open = [&](int r, int c) {
        int idx = passage_index(r, c);
        if (edge_state[idx] != EDGE_OPEN) {
            edge_state[idx] = EDGE_OPEN;
            add_open_passage(r, c);
        }
    };

    auto mark_closed = [&](int r, int c) {
        int idx = passage_index(r, c);
        if (edge_state[idx] == EDGE_UNKNOWN) {
            edge_state[idx] = EDGE_CLOSED;
        }
    };

    while (use_route_planner ||
           read_messages < (int)message_events.size() ||
           my_idx < target_counts[0]) {
        if (read_messages < (int)message_events.size() && message_events[read_messages].ready_turn <= turn) {
            cout << "< ?\n";
            cout.flush();
            string sender_str, body;
            if (!(cin >> sender_str >> body)) return 0;
            if (sender_str != "-") {
                int sender = stoi(sender_str);
                for (char ch : body) {
                    int value = ch - 33;
                    for (int b = 0; b < 6 && next_passage_idx[sender] < target_counts[sender]; ++b) {
                        auto [r, c] = work[sender][next_passage_idx[sender]];
                        if ((value >> b) & 1) {
                            mark_open(r, c);
                        } else {
                            mark_closed(r, c);
                        }
                        ++next_passage_idx[sender];
                    }
                }
                ++read_messages;
                need_replan = true;
                if (claim_if_connected()) return 0;
            }
            ++turn;
        } else if (use_route_planner) {
            if (need_replan || planned_queries.empty()) {
                planned_queries = plan_route_queries(turn);
                need_replan = false;
            }

            pair<int, int> next_query = {-1, -1};
            while (!planned_queries.empty()) {
                next_query = planned_queries.back();
                planned_queries.pop_back();
                if (edge_state[passage_index(next_query.first, next_query.second)] == EDGE_UNKNOWN) {
                    break;
                }
                next_query = {-1, -1};
            }

            if (next_query.first == -1) {
                if (claim_if_connected()) return 0;
                while (my_idx < K) {
                    auto [r, c] = all_passages[my_idx++];
                    if (edge_state[passage_index(r, c)] == EDGE_UNKNOWN) {
                        next_query = {r, c};
                        break;
                    }
                }
                if (next_query.first == -1) {
                    cout << ".\n";
                    cout.flush();
                    string ok;
                    if (!(cin >> ok)) return 0;
                    ++turn;
                    continue;
                }
            }

            auto [r, c] = next_query;
            cout << "? " << r << ' ' << c << "\n";
            cout.flush();
            string ans;
            if (!(cin >> ans)) return 0;
            if (ans == "1") {
                mark_open(r, c);
                if (claim_if_connected()) return 0;
            } else {
                mark_closed(r, c);
                need_replan = true;
            }
            ++turn;
        } else if (my_idx < target_counts[0]) {
            auto [r, c] = work[0][my_idx++];
            cout << "? " << r << ' ' << c << "\n";
            cout.flush();
            string ans;
            if (!(cin >> ans)) return 0;
            if (ans == "1") {
                mark_open(r, c);
                if (claim_if_connected()) return 0;
            } else {
                mark_closed(r, c);
            }
            ++turn;
        } else {
            cout << ".\n";
            cout.flush();
            string ok;
            if (!(cin >> ok)) return 0;
            ++turn;
        }
    }

    claim_if_connected();
    return 0;
}