#include <algorithm>
#include <cstdlib>
#include <iostream>
#include <cmath>
#include <queue>
#include <string>
#include <tuple>
#include <vector>

using namespace std;

namespace {

struct Edge {
    int a, b;
    int r, c;
    char step;
};

struct Arc {
    int to;
    int edge_id;
};

struct Dsu {
    vector<int> parent, size;

    Dsu(int n = 0) : parent(n), size(n, 1) {
        for (int i = 0; i < n; ++i) parent[i] = i;
    }

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

    bool same(int a, int b) {
        return find(a) == find(b);
    }
};

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

string read_line() {
    string s;
    if (!getline(cin, s)) exit(0);
    return s;
}

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

string encode_bits(const vector<unsigned char> &bits, int start, int max_chars) {
    int remaining = static_cast<int>(bits.size()) - start;
    int pairs = min(max_chars / 2, (remaining + 12) / 13);
    string encoded;
    encoded.reserve(pairs * 2);

    for (int i = 0; i < pairs; ++i) {
        int val = 0;
        for (int b = 0; b < 13; ++b) {
            int pos = start + i * 13 + b;
            if (pos < static_cast<int>(bits.size()) && bits[pos]) val |= 1 << b;
        }
        encoded.push_back(static_cast<char>(32 + val % 95));
        encoded.push_back(static_cast<char>(32 + val / 95));
    }

    return encoded;
}

void send_message_to_zero(const string &body) {
    send_line("> 0 " + body);
    read_line();
}

vector<unsigned char> decode_bits(const string &payload, int bit_count) {
    vector<unsigned char> bits(bit_count, 0);
    int out = 0;
    for (int i = 0; i + 1 < static_cast<int>(payload.size()) && out < bit_count; i += 2) {
        int lo = static_cast<unsigned char>(payload[i]) - 32;
        int hi = static_cast<unsigned char>(payload[i + 1]) - 32;
        if (lo < 0 || lo >= 95 || hi < 0 || hi >= 95) break;

        int val = lo + hi * 95;
        for (int b = 0; b < 13 && out < bit_count; ++b, ++out) {
            bits[out] = (val >> b) & 1;
        }
    }
    return bits;
}

int room_id(int cols, int rr, int cc) {
    return rr * cols + cc;
}

vector<Edge> build_edges(int n) {
    int rows = (n + 1) / 2;
    int cols = rows;
    vector<Edge> edges;
    edges.reserve(2 * rows * (cols - 1));

    for (int r = 0; r < rows; ++r) {
        for (int c = 0; c < cols; ++c) {
            int a = room_id(cols, r, c);
            if (c + 1 < cols) {
                int b = room_id(cols, r, c + 1);
                edges.push_back({a, b, 2 * r + 1, 2 * c + 2, 'R'});
            }
            if (r + 1 < rows) {
                int b = room_id(cols, r + 1, c);
                edges.push_back({a, b, 2 * r + 2, 2 * c + 1, 'D'});
            }
        }
    }

    return edges;
}

vector<int> build_priority_order(int n, const vector<Edge> &edges) {
    int rows = (n + 1) / 2;
    int edge_count = static_cast<int>(edges.size());
    vector<int> order(edge_count);
    for (int i = 0; i < edge_count; ++i) order[i] = i;

    auto score = [&](int id) {
        const Edge &e = edges[id];
        int ar = e.a / rows, ac = e.a % rows;
        int br = e.b / rows, bc = e.b % rows;
        int mr2 = ar + br;
        int mc2 = ac + bc;
        int diag = abs(mr2 - mc2);
        int anti = abs(mr2 + mc2 - 2 * (rows - 1));
        int end_bias = min(mr2 + mc2, 4 * (rows - 1) - mr2 - mc2);
        int jitter = static_cast<int>((id * 1103515245u + 12345u) & 1023);
        return tuple<int, int, int, int>(diag * 100 + end_bias, anti, jitter, id);
    };

    sort(order.begin(), order.end(), [&](int a, int b) {
        return score(a) < score(b);
    });
    return order;
}

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

string rooms_to_path(int cols, const vector<int> &rooms) {
    string path;
    path.reserve(rooms.size() * 2);
    for (int i = 1; i < static_cast<int>(rooms.size()); ++i) {
        int a = rooms[i - 1], b = rooms[i];
        int ar = a / cols, ac = a % cols;
        int br = b / cols, bc = b % cols;
        char ch = '?';
        if (br == ar + 1) ch = 'D';
        else if (br == ar - 1) ch = 'U';
        else if (bc == ac + 1) ch = 'R';
        else if (bc == ac - 1) ch = 'L';
        path.push_back(ch);
        path.push_back(ch);
    }
    return path;
}

int tie_value(int edge_id, int from, int to, int cols, int variant) {
    unsigned h = static_cast<unsigned>(edge_id) * 1103515245u +
                 static_cast<unsigned>(from) * 1000003u +
                 static_cast<unsigned>(to) * 9176u +
                 static_cast<unsigned>(variant) * 2654435761u;
    int r = to / cols;
    int c = to % cols;
    switch (variant % 6) {
        case 0:
            return edge_id;
        case 1:
            return -edge_id;
        case 2:
            return static_cast<int>(h & 0x7fffffff);
        case 3:
            return r * 1024 + c;
        case 4:
            return c * 1024 + r;
        default:
            return -static_cast<int>(h & 0x7fffffff);
    }
}

bool better_candidate(int dist, int tie, int best_dist, int best_tie) {
    return dist < best_dist || (dist == best_dist && tie < best_tie);
}

string bidirectional_search(int n, int agent_id, const vector<Edge> &edges) {
    int rows = (n + 1) / 2;
    int cols = rows;
    int room_count = rows * cols;
    int edge_count = static_cast<int>(edges.size());

    vector<vector<Arc>> adj(room_count);
    for (int i = 0; i < edge_count; ++i) {
        adj[edges[i].a].push_back({edges[i].b, i});
        adj[edges[i].b].push_back({edges[i].a, i});
    }

    vector<unsigned char> asked(edge_count, 0);
    vector<int> parent0(room_count, -2), parent1(room_count, -2);
    vector<int> depth0(room_count, 0), depth1(room_count, 0);

    int start = 0;
    int goal = room_count - 1;
    parent0[start] = -1;
    parent1[goal] = -1;

    using Item = tuple<double, int, int, int, int>;  // score, seq, side, from, arc index
    priority_queue<Item, vector<Item>, greater<Item>> pq;
    int seq = 0;

    auto score = [&](int side, int from, int to, int edge_id) {
        int target = (side == 0 ? goal : start);
        int tr = target / cols, tc = target % cols;
        int r = to / cols, c = to % cols;
        int man = abs(r - tr) + abs(c - tc);
        int diag = abs(r - c);
        int depth = (side == 0 ? depth0[from] : depth1[from]);
        int mode = agent_id % 3;

        double value = 0.0;
        if (mode == 0) {
            value = man - 0.05 * depth + 0.10 * diag;
        } else if (mode == 1) {
            value = man + 0.05 * depth + 0.40 * diag;
        } else {
            value = man + 0.30 * depth;
        }
        int jitter = (edge_id * 1103515245u + agent_id * 1000003u + side * 9176u) & 1023;
        if (mode != 0) value += jitter * 1e-6;
        return value;
    };

    auto push_from = [&](int side, int v) {
        const vector<int> &parent = (side == 0 ? parent0 : parent1);
        for (int i = 0; i < static_cast<int>(adj[v].size()); ++i) {
            const Arc &arc = adj[v][i];
            if (asked[arc.edge_id] || parent[arc.to] != -2) continue;
            pq.push({score(side, v, arc.to, arc.edge_id), seq++, side, v, i});
        }
    };

    auto build_answer = [&](int meet) {
        vector<int> rooms;
        for (int v = meet; v != -1; v = parent0[v]) rooms.push_back(v);
        reverse(rooms.begin(), rooms.end());
        for (int v = parent1[meet]; v != -1; v = parent1[v]) rooms.push_back(v);
        return rooms_to_path(cols, rooms);
    };

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

    while (!pq.empty()) {
        auto [_, __, side, from, arc_index] = pq.top();
        pq.pop();
        if (arc_index >= static_cast<int>(adj[from].size())) continue;

        Arc arc = adj[from][arc_index];
        if (asked[arc.edge_id]) continue;
        if ((side == 0 ? parent0[arc.to] : parent1[arc.to]) != -2) continue;

        asked[arc.edge_id] = 1;
        send_line("? " + to_string(edges[arc.edge_id].r) + " " + to_string(edges[arc.edge_id].c));
        string reply = read_line();
        if (reply.empty() || reply[0] != '1') continue;

        if (side == 0) {
            parent0[arc.to] = from;
            depth0[arc.to] = depth0[from] + 1;
            if (parent1[arc.to] != -2) return build_answer(arc.to);
            push_from(0, arc.to);
        } else {
            parent1[arc.to] = from;
            depth1[arc.to] = depth1[from] + 1;
            if (parent0[arc.to] != -2) return build_answer(arc.to);
            push_from(1, arc.to);
        }
    }

    return "";
}

vector<int> distances_without_closed(const vector<vector<Arc>> &adj,
                                     const vector<unsigned char> &closed,
                                     const vector<int> &sources) {
    vector<int> dist(adj.size(), -1);
    queue<int> q;
    for (int s : sources) {
        if (dist[s] != -1) continue;
        dist[s] = 0;
        q.push(s);
    }

    while (!q.empty()) {
        int v = q.front();
        q.pop();
        for (const Arc &arc : adj[v]) {
            if (closed[arc.edge_id] || dist[arc.to] != -1) continue;
            dist[arc.to] = dist[v] + 1;
            q.push(arc.to);
        }
    }
    return dist;
}

string frontier_one_sided_search(int n, bool from_goal, bool exact_distance, int variant,
                                 const vector<Edge> &edges) {
    int rows = (n + 1) / 2;
    int cols = rows;
    int room_count = rows * cols;
    int edge_count = static_cast<int>(edges.size());

    vector<vector<Arc>> adj(room_count);
    for (int i = 0; i < edge_count; ++i) {
        adj[edges[i].a].push_back({edges[i].b, i});
        adj[edges[i].b].push_back({edges[i].a, i});
    }

    int start = 0;
    int goal = room_count - 1;
    int root = from_goal ? goal : start;
    int target = from_goal ? start : goal;

    vector<unsigned char> closed(edge_count, 0), inside(room_count, 0);
    vector<int> parent(room_count, -2), nodes;
    inside[root] = 1;
    parent[root] = -1;
    nodes.push_back(root);

    vector<int> dist;
    if (exact_distance) dist = distances_without_closed(adj, closed, {target});
    auto target_distance = [&](int v) {
        if (exact_distance) return dist[v];
        int vr = v / cols, vc = v % cols;
        int tr = target / cols, tc = target % cols;
        return abs(vr - tr) + abs(vc - tc);
    };

    while (!inside[target]) {
        int best_edge = -1;
        int best_from = -1;
        int best_to = -1;
        int best_dist = room_count + 1;
        int best_tie = 0;

        for (int v : nodes) {
            for (const Arc &arc : adj[v]) {
                if (closed[arc.edge_id] || inside[arc.to]) continue;
                int d = target_distance(arc.to);
                if (d < 0) continue;
                int tie = tie_value(arc.edge_id, v, arc.to, cols, variant);
                if (best_edge < 0 || better_candidate(d, tie, best_dist, best_tie)) {
                    best_dist = d;
                    best_tie = tie;
                    best_edge = arc.edge_id;
                    best_from = v;
                    best_to = arc.to;
                }
            }
        }

        if (best_edge < 0) return "";

        send_line("? " + to_string(edges[best_edge].r) + " " + to_string(edges[best_edge].c));
        string reply = read_line();
        if (!reply.empty() && reply[0] == '1') {
            inside[best_to] = 1;
            parent[best_to] = best_from;
            nodes.push_back(best_to);
        } else {
            closed[best_edge] = 1;
            if (exact_distance) dist = distances_without_closed(adj, closed, {target});
        }
    }

    vector<int> rooms;
    if (from_goal) {
        for (int v = start; v != -1; v = parent[v]) rooms.push_back(v);
    } else {
        for (int v = goal; v != -1; v = parent[v]) rooms.push_back(v);
        reverse(rooms.begin(), rooms.end());
    }
    return rooms_to_path(cols, rooms);
}

string frontier_two_sided_search(int n, bool exact_distance, int variant, const vector<Edge> &edges) {
    int rows = (n + 1) / 2;
    int cols = rows;
    int room_count = rows * cols;
    int edge_count = static_cast<int>(edges.size());

    vector<vector<Arc>> adj(room_count);
    for (int i = 0; i < edge_count; ++i) {
        adj[edges[i].a].push_back({edges[i].b, i});
        adj[edges[i].b].push_back({edges[i].a, i});
    }

    int start = 0;
    int goal = room_count - 1;

    vector<unsigned char> closed(edge_count, 0), side(room_count, 0);
    vector<int> parent0(room_count, -2), parent1(room_count, -2);
    vector<int> nodes[2];
    side[start] |= 1;
    side[goal] |= 2;
    parent0[start] = -1;
    parent1[goal] = -1;
    nodes[0].push_back(start);
    nodes[1].push_back(goal);

    vector<int> dist[2];
    if (exact_distance) {
        dist[0] = distances_without_closed(adj, closed, nodes[1]);
        dist[1] = distances_without_closed(adj, closed, nodes[0]);
    }

    auto target_distance = [&](int side_index, int v) {
        if (exact_distance) return dist[side_index][v];
        int target = side_index == 0 ? goal : start;
        int vr = v / cols, vc = v % cols;
        int tr = target / cols, tc = target % cols;
        return abs(vr - tr) + abs(vc - tc);
    };

    auto build_answer = [&](int meet) {
        vector<int> rooms;
        for (int v = meet; v != -1; v = parent0[v]) rooms.push_back(v);
        reverse(rooms.begin(), rooms.end());
        for (int v = parent1[meet]; v != -1; v = parent1[v]) rooms.push_back(v);
        return rooms_to_path(cols, rooms);
    };

    auto best_edge = [&](int side_index) {
        unsigned char bit = static_cast<unsigned char>(1u << side_index);
        int best_dist = room_count + 1;
        int best_edge_id = -1;
        int best_to = -1;
        int best_from = -1;
        int best_tie = 0;

        for (int v : nodes[side_index]) {
            for (const Arc &arc : adj[v]) {
                if (closed[arc.edge_id] || (side[arc.to] & bit)) continue;
                int d = target_distance(side_index, arc.to);
                if (d < 0) continue;
                int tie = tie_value(arc.edge_id, v, arc.to, cols, variant);
                if (best_edge_id < 0 || better_candidate(d, tie, best_dist, best_tie)) {
                    best_dist = d;
                    best_tie = tie;
                    best_edge_id = arc.edge_id;
                    best_from = v;
                    best_to = arc.to;
                }
            }
        }

        return tuple<int, int, int, int>(best_dist, best_edge_id, best_from, best_to);
    };

    int turn = 0;
    while (true) {
        auto [d0, e0, from0, to0] = best_edge(0);
        auto [d1, e1, from1, to1] = best_edge(1);

        int side_policy = variant % 3;
        int side_index = turn & 1;
        if (side_policy == 1 && e0 >= 0 && e1 >= 0) {
            side_index = (d0 <= d1 ? 0 : 1);
        } else if (side_policy == 2 && e0 >= 0 && e1 >= 0) {
            side_index = (static_cast<int>(nodes[0].size()) <= static_cast<int>(nodes[1].size()) ? 0 : 1);
        }
        int edge_id = side_index == 0 ? e0 : e1;
        int from = side_index == 0 ? from0 : from1;
        int to = side_index == 0 ? to0 : to1;
        if (edge_id < 0) {
            side_index ^= 1;
            edge_id = side_index == 0 ? e0 : e1;
            from = side_index == 0 ? from0 : from1;
            to = side_index == 0 ? to0 : to1;
        }
        if (edge_id < 0) return "";

        send_line("? " + to_string(edges[edge_id].r) + " " + to_string(edges[edge_id].c));
        string reply = read_line();
        ++turn;

        if (!reply.empty() && reply[0] == '1') {
            unsigned char bit = static_cast<unsigned char>(1u << side_index);
            if (side_index == 0) parent0[to] = from;
            else parent1[to] = from;

            side[to] |= bit;
            nodes[side_index].push_back(to);
            if (side[to] == 3) return build_answer(to);

            if (exact_distance) {
                dist[side_index ^ 1] = distances_without_closed(adj, closed, nodes[side_index]);
            }
        } else {
            closed[edge_id] = 1;
            if (exact_distance) {
                dist[0] = distances_without_closed(adj, closed, nodes[1]);
                dist[1] = distances_without_closed(adj, closed, nodes[0]);
            }
        }
    }
}

string build_path_from_edges(int n, const vector<Edge> &edges,
                             const vector<unsigned char> &open_edge) {
    int rows = (n + 1) / 2;
    int cols = rows;
    int room_count = rows * cols;

    vector<vector<pair<int, char>>> g(room_count);
    for (int i = 0; i < static_cast<int>(edges.size()); ++i) {
        if (!open_edge[i]) continue;
        const Edge &e = edges[i];
        g[e.a].push_back({e.b, e.step});
        g[e.b].push_back({e.a, invert_step(e.step)});
    }

    vector<int> parent(room_count, -1);
    vector<char> step(room_count, 0);
    queue<int> q;
    parent[0] = 0;
    q.push(0);

    while (!q.empty() && parent[room_count - 1] == -1) {
        int v = q.front();
        q.pop();

        for (auto [to, ch] : g[v]) {
            if (parent[to] != -1) continue;
            parent[to] = v;
            step[to] = ch;
            q.push(to);
        }
    }

    if (parent[room_count - 1] == -1) return "";

    string compressed;
    for (int v = room_count - 1; v != 0; v = parent[v]) {
        compressed.push_back(step[v]);
    }
    reverse(compressed.begin(), compressed.end());

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

void prioritized_streaming_scan(int n, int num_agents, int agent_id, int max_msg_len,
                                const vector<Edge> &edges) {
    const int chunk_bits = 64;
    int rows = (n + 1) / 2;
    int room_count = rows * rows;
    int edge_count = static_cast<int>(edges.size());
    vector<int> order = build_priority_order(n, edges);
    int workers = num_agents - 1;

    if (agent_id != 0) {
        int worker = agent_id - 1;
        for (int phase = 0;; ++phase) {
            int base = (1 + phase * workers + worker) * chunk_bits;
            int count = min(chunk_bits, edge_count - base);
            if (count < 0) count = 0;

            vector<unsigned char> bits;
            bits.reserve(count);
            for (int j = 0; j < count; ++j) {
                int edge_id = order[base + j];
                send_line("? " + to_string(edges[edge_id].r) + " " + to_string(edges[edge_id].c));
                string reply = read_line();
                bits.push_back(!reply.empty() && reply[0] == '1');
            }

            bool is_final = base + workers * chunk_bits >= edge_count;
            string header = string(1, is_final ? 'F' : 'S') + to_string(phase) + ":";
            string payload = encode_bits(bits, 0, max_msg_len - static_cast<int>(header.size()));
            send_message_to_zero(header + payload);
            if (is_final) {
                send_line("halt");
                return;
            }
        }
    }

    vector<unsigned char> open_edge(edge_count, 0);
    Dsu dsu(room_count);
    vector<unsigned char> finished(num_agents, 0);
    finished[0] = 1;
    int done = 1;

    int local_count = min(chunk_bits, edge_count);
    for (int j = 0; j < local_count; ++j) {
        int edge_id = order[j];
        send_line("? " + to_string(edges[edge_id].r) + " " + to_string(edges[edge_id].c));
        string reply = read_line();
        if (!reply.empty() && reply[0] == '1') {
            open_edge[edge_id] = 1;
            dsu.unite(edges[edge_id].a, edges[edge_id].b);
        }
    }
    if (dsu.same(0, room_count - 1)) {
        string path = build_path_from_edges(n, edges, open_edge);
        send_line("! " + path);
        return;
    }

    while (done < num_agents && !dsu.same(0, room_count - 1)) {
        send_line("< ?");
        string reply = read_line();
        if (reply == "- -") continue;

        size_t space = reply.find(' ');
        if (space == string::npos) continue;
        int sender = stoi(reply.substr(0, space));
        if (sender <= 0 || sender >= num_agents) continue;

        string body = reply.substr(space + 1);
        if (body.empty() || (body[0] != 'S' && body[0] != 'F')) continue;

        bool is_final = body[0] == 'F';
        if (is_final && !finished[sender]) {
            finished[sender] = 1;
            ++done;
        }

        size_t colon = body.find(':');
        if (colon == string::npos) continue;
        int phase = stoi(body.substr(1, colon - 1));
        int worker = sender - 1;
        int base = (1 + phase * workers + worker) * chunk_bits;
        int count = min(chunk_bits, edge_count - base);
        if (count <= 0) continue;

        string payload = body.substr(colon + 1);
        vector<unsigned char> bits = decode_bits(payload, count);
        for (int j = 0; j < count; ++j) {
            if (!bits[j]) continue;
            int edge_id = order[base + j];
            open_edge[edge_id] = 1;
            dsu.unite(edges[edge_id].a, edges[edge_id].b);
        }
    }

    string path = build_path_from_edges(n, edges, open_edge);
    if (!path.empty()) {
        send_line("! " + path);
        return;
    }

    // The prioritized stream covers all edges, so this is only a defensive fallback.
    vector<unsigned char> all_open(edge_count, 0);
    for (int idx = 0; idx < edge_count; ++idx) {
        send_line("? " + to_string(edges[idx].r) + " " + to_string(edges[idx].c));
        string reply = read_line();
        all_open[idx] = !reply.empty() && reply[0] == '1';
    }
    path = build_path_from_edges(n, edges, all_open);
    send_line("! " + path);
}

string build_path_from_cells(int n, const vector<unsigned char> &open) {
    int total = n * n;
    vector<int> parent(total, -1);
    vector<char> step(total, 0);
    queue<int> q;

    parent[0] = 0;
    q.push(0);

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

    while (!q.empty() && parent[total - 1] == -1) {
        int v = q.front();
        q.pop();
        int r = v / n;
        int c = v % n;

        for (int k = 0; k < 4; ++k) {
            int nr = r + dr[k];
            int nc = c + dc[k];
            if (nr < 0 || nr >= n || nc < 0 || nc >= n) continue;

            int to = nr * n + nc;
            if (!open[to] || parent[to] != -1) continue;

            parent[to] = v;
            step[to] = dir[k];
            q.push(to);
        }
    }

    if (parent[total - 1] == -1) return "";

    string path;
    for (int v = total - 1; v != 0; v = parent[v]) {
        path.push_back(step[v]);
    }
    reverse(path.begin(), path.end());
    return path;
}

}  // namespace

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;
    string startup_rest;
    getline(cin, startup_rest);

    if (N == 1) {
        if (AGENT_ID == 0) send_line("!");
        else send_line("halt");
        return 0;
    }

    vector<Edge> edges = build_edges(N);
    int edge_count = static_cast<int>(edges.size());

    if (NUM_AGENTS >= 8 && (N >= 151 || (N >= 101 && NUM_AGENTS >= 25))) {
        prioritized_streaming_scan(N, NUM_AGENTS, AGENT_ID, MAX_MSG_LEN, edges);
        return 0;
    }

    bool use_search_portfolio = NUM_AGENTS <= 6 || (NUM_AGENTS == 7 && 181 <= N && N <= 351);
    if (use_search_portfolio) {
        string path;
        bool use_frontier = N <= 351;
        bool exact_frontier = N <= 301;
        if (use_frontier && AGENT_ID == 0) {
            path = frontier_one_sided_search(N, false, exact_frontier, 0, edges);
        } else if (use_frontier && AGENT_ID == 1) {
            path = frontier_one_sided_search(N, true, exact_frontier, 0, edges);
        } else if (use_frontier && AGENT_ID == 2) {
            path = frontier_two_sided_search(N, exact_frontier, 0, edges);
        } else {
            path = bidirectional_search(N, AGENT_ID, edges);
        }
        if (!path.empty()) {
            send_line("! " + path);
            return 0;
        }
    }

    int my_count = assigned_count(edge_count, NUM_AGENTS, AGENT_ID);
    vector<unsigned char> local_bits;
    local_bits.reserve(my_count);

    for (int idx = AGENT_ID; idx < edge_count; idx += NUM_AGENTS) {
        send_line("? " + to_string(edges[idx].r) + " " + to_string(edges[idx].c));
        string reply = read_line();
        local_bits.push_back(!reply.empty() && reply[0] == '1');
    }

    if (AGENT_ID != 0) {
        int pos = 0;
        while (pos < my_count || pos == 0) {
            string header = "C" + to_string(pos) + ":";
            int room = MAX_MSG_LEN - static_cast<int>(header.size());
            if (room <= 0) {
                send_message_to_zero("F0:");
                send_line("halt");
                return 0;
            }

            int capacity_bits = (room / 2) * 13;
            bool is_final = pos + capacity_bits >= my_count;
            header[0] = is_final ? 'F' : 'C';
            string payload = encode_bits(local_bits, pos, room);
            send_message_to_zero(header + payload);
            pos += static_cast<int>(payload.size() / 2) * 13;
            if (is_final) break;
        }

        send_line("halt");
        return 0;
    }

    vector<unsigned char> open_edge(edge_count, 0);
    for (int i = 0; i < my_count; ++i) {
        int idx = i * NUM_AGENTS;
        open_edge[idx] = local_bits[i];
    }

    vector<unsigned char> finished(NUM_AGENTS, 0);
    finished[0] = 1;
    int done = 1;

    while (done < NUM_AGENTS) {
        send_line("< ?");
        string reply = read_line();
        if (reply == "- -") continue;

        size_t space = reply.find(' ');
        if (space == string::npos) continue;

        int sender = stoi(reply.substr(0, space));
        string body = reply.substr(space + 1);

        if (!body.empty() && body[0] == 'F') {
            if (!finished[sender]) {
                finished[sender] = 1;
                ++done;
            }
        }

        if (body.empty() || (body[0] != 'C' && body[0] != 'F')) continue;

        size_t colon = body.find(':');
        if (colon == string::npos) continue;

        int start = stoi(body.substr(1, colon - 1));
        string payload = body.substr(colon + 1);
        int sender_count = assigned_count(edge_count, NUM_AGENTS, sender);

        for (int i = 0; i + 1 < static_cast<int>(payload.size()); i += 2) {
            int lo = static_cast<unsigned char>(payload[i]) - 32;
            int hi = static_cast<unsigned char>(payload[i + 1]) - 32;
            if (lo < 0 || lo >= 95 || hi < 0 || hi >= 95) continue;

            int val = lo + hi * 95;
            for (int b = 0; b < 13; ++b) {
                int local_pos = start + (i / 2) * 13 + b;
                if (local_pos >= sender_count) break;

                int idx = sender + local_pos * NUM_AGENTS;
                if (idx < edge_count) open_edge[idx] = (val >> b) & 1;
            }
        }
    }

    string path = build_path_from_edges(N, edges, open_edge);
    if (path.empty()) {
        vector<unsigned char> open(N * N, 0);
        for (int idx = 0; idx < N * N; ++idx) {
            int r = idx / N + 1;
            int c = idx % N + 1;
            send_line("? " + to_string(r) + " " + to_string(c));
            string reply = read_line();
            open[idx] = !reply.empty() && reply[0] == '1';
        }
        path = build_path_from_cells(N, open);
    }
    send_line("! " + path);
    return 0;
}