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

void send_message_to(int target, const string &body) {
    send_line("> " + to_string(target) + " " + 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, int num_agents, const vector<Edge> &edges,
                                 int forced_mode = -1) {
    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;
    bool use_bridge_band = (num_agents == 7 && 181 <= n && n <= 187);
    bool use_bridge_order = use_bridge_band ||
                            (num_agents == 16 && 200 <= n && n <= 260) ||
                            (num_agents == 17 && 340 <= n && n <= 349) ||
                            (32 <= num_agents && num_agents <= 33 && 401 <= n && n <= 451);
    bool use_center_order = (num_agents == 40 && 200 <= n && n <= 230) ||
                            (num_agents == 43 && 400 <= n && n <= 450);

    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);
        if (forced_mode < 0 && use_bridge_order) {
            int den = end_bias + rows / 8 + 8;
            int bridge = (diag * diag * 1200) / den + end_bias / 2;
            return tuple<int, int, int, int>(bridge, diag, anti, jitter);
        }
        if (forced_mode < 0 && use_center_order) return tuple<int, int, int, int>(diag * 100 - end_bias, anti, jitter, id);
        int mode = forced_mode;
#ifdef D_ORDER_MODE
        if (mode < 0) mode = D_ORDER_MODE;
#endif
        if (mode == 1) return tuple<int, int, int, int>(anti * 100 + end_bias, diag, jitter, id);
        if (mode == 2) return tuple<int, int, int, int>(end_bias * 100 + diag, anti, jitter, id);
        if (mode == 3) return tuple<int, int, int, int>(diag * 100 - end_bias, anti, jitter, id);
        if (mode == 4) return tuple<int, int, int, int>((diag + anti) * 100 + end_bias, diag, jitter, id);
        if (mode == 5) return tuple<int, int, int, int>((min(diag, anti)) * 100 + end_bias, max(diag, anti), jitter, id);
        if (mode == 6) {
            int den = end_bias + rows / 8 + 8;
            int bridge = (diag * diag * 1200) / den + end_bias / 2;
            return tuple<int, int, int, int>(bridge, diag, anti, jitter);
        }
        if (mode == 7) {
            int den = end_bias + rows / 6 + 6;
            int bridge = (diag * diag * 800) / den - end_bias;
            return tuple<int, int, int, int>(bridge, anti, diag, jitter);
        }
        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;
}

int choose_chunk_bits(int n, int num_agents) {
#ifdef D_CHUNK_OVERRIDE
    return D_CHUNK_OVERRIDE;
#endif
    if (n <= 105 && num_agents >= 35) return 38;
    if (n <= 145 && num_agents >= 35) return 40;
    if (n <= 147 && num_agents >= 25 && num_agents <= 32) return 40;
    if (num_agents == 28 && 200 <= n && n < 250) return 80;
    if (num_agents >= 25 && num_agents <= 28 && 299 <= n && n <= 350) return 128;
    if (num_agents >= 29 && num_agents <= 32 && 200 <= n && n <= 350) return 80;
    if (num_agents == 25 && n >= 470) return 160;
    if (num_agents == 25 && n >= 450) return 80;
    if (num_agents == 7 && 181 <= n && n <= 241) return 96;
    if (num_agents == 7 && 151 <= n && n <= 301) return 64;
    if (num_agents <= 14) return 96;
    return 64;
}

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

int exact_rebuild_period(int n) {
    if (n <= 253) return 1;
#ifdef D_EXACT_REBUILD_PERIOD
    return D_EXACT_REBUILD_PERIOD;
#endif
    return 12;
}

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

void compute_distances_without_closed(const vector<vector<Arc>> &adj,
                                      const vector<unsigned char> &closed,
                                      const vector<int> &sources,
                                      vector<int> &dist,
                                      vector<int> &q) {
    dist.resize(adj.size());
    fill(dist.begin(), dist.end(), -1);
    q.clear();
    for (int s : sources) {
        if (dist[s] != -1) continue;
        dist[s] = 0;
        q.push_back(s);
    }

    for (size_t head = 0; head < q.size(); ++head) {
        int v = q[head];
        for (const Arc &arc : adj[v]) {
            if (closed[arc.edge_id] || dist[arc.to] != -1) continue;
            dist[arc.to] = dist[v] + 1;
            q.push_back(arc.to);
        }
    }
}

vector<unsigned char> bridges_without_closed(const vector<vector<Arc>> &adj,
                                             const vector<unsigned char> &closed,
                                             int edge_count) {
    int n = static_cast<int>(adj.size());
    vector<int> tin(n, -1), low(n, 0);
    vector<unsigned char> bridge(edge_count, 0);
    int timer = 0;

    auto dfs = [&](auto &&self, int v, int parent_edge) -> void {
        tin[v] = low[v] = timer++;
        for (const Arc &arc : adj[v]) {
            if (closed[arc.edge_id] || arc.edge_id == parent_edge) continue;
            int to = arc.to;
            if (tin[to] != -1) {
                low[v] = min(low[v], tin[to]);
                continue;
            }

            self(self, to, arc.edge_id);
            low[v] = min(low[v], low[to]);
            if (low[to] > tin[v]) bridge[arc.edge_id] = 1;
        }
    };

    for (int v = 0; v < n; ++v) {
        if (tin[v] == -1) dfs(dfs, v, -1);
    }
    return bridge;
}

string frontier_one_sided_search(int n, bool from_goal, bool exact_distance, int variant,
                                 const vector<Edge> &edges, bool use_forced = false) {
    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<unsigned char> forced(edge_count, 0);
    vector<int> parent(room_count, -2), nodes;
    inside[root] = 1;
    parent[root] = -1;
    nodes.push_back(root);

    vector<int> dist, distance_queue;
    vector<int> target_source = {target};
    if (exact_distance) compute_distances_without_closed(adj, closed, target_source, dist, distance_queue);
    int rebuild_period = exact_distance ? exact_rebuild_period(n) : 0;
    int rebuild_events = 0;
    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);
    };

    using Candidate = tuple<int, int, int, int, int, int>;  // dist, tie, seq, edge, from, to
    priority_queue<Candidate, vector<Candidate>, greater<Candidate>> heap;
    int heap_seq = 0;

    auto push_frontier = [&](int v) {
        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);
            heap.push({d, tie, heap_seq++, arc.edge_id, v, arc.to});
        }
    };

    auto rebuild_heap = [&]() {
        heap = priority_queue<Candidate, vector<Candidate>, greater<Candidate>>();
        heap_seq = 0;
        for (int v : nodes) push_frontier(v);
    };

    push_frontier(root);

    auto absorb_forced = [&]() {
        if (!use_forced) return false;
        bool changed = false;
        for (size_t i = 0; i < nodes.size(); ++i) {
            int v = nodes[i];
            for (const Arc &arc : adj[v]) {
                if (!forced[arc.edge_id] || closed[arc.edge_id] || inside[arc.to]) continue;
                inside[arc.to] = 1;
                parent[arc.to] = v;
                nodes.push_back(arc.to);
                push_frontier(arc.to);
                changed = true;
            }
        }
        return changed;
    };

    while (!inside[target]) {
        absorb_forced();
        if (inside[target]) break;

        int best_edge = -1;
        int best_from = -1;
        int best_to = -1;

        while (!heap.empty()) {
            auto [d, tie, seq, edge_id, from, to] = heap.top();
            heap.pop();
            if (closed[edge_id] || !inside[from] || inside[to]) continue;
            if (target_distance(to) != d || tie_value(edge_id, from, to, cols, variant) != tie) continue;
            best_edge = edge_id;
            best_from = from;
            best_to = to;
            break;
        }

        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);
            push_frontier(best_to);
        } else {
            closed[best_edge] = 1;
            if (use_forced) {
                forced = bridges_without_closed(adj, closed, edge_count);
                absorb_forced();
            }
            if (exact_distance && (++rebuild_events >= rebuild_period)) {
                rebuild_events = 0;
                compute_distances_without_closed(adj, closed, target_source, dist, distance_queue);
                rebuild_heap();
            }
        }
    }

    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,
                                 bool use_forced = false) {
    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<unsigned char> forced(edge_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], distance_queue[2];
    if (exact_distance) {
        compute_distances_without_closed(adj, closed, nodes[1], dist[0], distance_queue[0]);
        compute_distances_without_closed(adj, closed, nodes[0], dist[1], distance_queue[1]);
    }
    int rebuild_period = exact_distance ? exact_rebuild_period(n) : 0;
    int rebuild_events = 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);
    };

#ifdef D_USE_TWO_HEAP
    using SideCandidate = tuple<int, int, int, int, int, int>;  // dist, tie, seq, edge, from, to
    priority_queue<SideCandidate, vector<SideCandidate>, greater<SideCandidate>> heaps[2];
    int heap_seq[2] = {0, 0};

    auto push_frontier_side = [&](int side_index, int v) {
        unsigned char bit = static_cast<unsigned char>(1u << 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);
            heaps[side_index].push({d, tie, heap_seq[side_index]++, arc.edge_id, v, arc.to});
        }
    };

    auto rebuild_heap_side = [&](int side_index) {
        heaps[side_index] = priority_queue<SideCandidate, vector<SideCandidate>, greater<SideCandidate>>();
        heap_seq[side_index] = 0;
        for (int v : nodes[side_index]) push_frontier_side(side_index, v);
    };

    rebuild_heap_side(0);
    rebuild_heap_side(1);
#endif

    auto absorb_forced = [&]() -> int {
        if (!use_forced) return -1;
        int meet = -1;
        for (int side_index = 0; side_index < 2 && meet < 0; ++side_index) {
            unsigned char bit = static_cast<unsigned char>(1u << side_index);
            for (size_t i = 0; i < nodes[side_index].size() && meet < 0; ++i) {
                int v = nodes[side_index][i];
                for (const Arc &arc : adj[v]) {
                    if (!forced[arc.edge_id] || closed[arc.edge_id] || (side[arc.to] & bit)) continue;
                    if (side_index == 0) parent0[arc.to] = v;
                    else parent1[arc.to] = v;

                    side[arc.to] |= bit;
                    nodes[side_index].push_back(arc.to);
#ifdef D_USE_TWO_HEAP
                    push_frontier_side(side_index, arc.to);
#endif
                    if (side[arc.to] == 3) {
                        meet = arc.to;
                        break;
                    }
                }
            }
        }
        return meet;
    };

    auto best_edge = [&](int side_index) {
        unsigned char bit = static_cast<unsigned char>(1u << side_index);
#ifdef D_USE_TWO_HEAP
        while (!heaps[side_index].empty()) {
            auto [d, tie, seq, edge_id, from, to] = heaps[side_index].top();
            if (closed[edge_id] || !(side[from] & bit) || (side[to] & bit)) {
                heaps[side_index].pop();
                continue;
            }
            if (target_distance(side_index, to) != d ||
                tie_value(edge_id, from, to, cols, variant) != tie) {
                heaps[side_index].pop();
                continue;
            }
            return tuple<int, int, int, int>(d, edge_id, from, to);
        }
        return tuple<int, int, int, int>(room_count + 1, -1, -1, -1);
#else
        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);
#endif
    };

    int turn = 0;
    while (true) {
        int forced_meet = absorb_forced();
        if (forced_meet >= 0) return build_answer(forced_meet);

        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 "";
#ifdef D_USE_TWO_HEAP
        heaps[side_index].pop();
#endif

        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);
#ifdef D_USE_TWO_HEAP
            push_frontier_side(side_index, to);
#endif
            if (side[to] == 3) return build_answer(to);

            if (exact_distance && (++rebuild_events >= rebuild_period)) {
                rebuild_events = 0;
                compute_distances_without_closed(adj, closed, nodes[side_index],
                                                 dist[side_index ^ 1], distance_queue[side_index ^ 1]);
#ifdef D_USE_TWO_HEAP
                rebuild_heap_side(side_index ^ 1);
#endif
            }
        } else {
            closed[edge_id] = 1;
            if (use_forced) {
                forced = bridges_without_closed(adj, closed, edge_count);
                forced_meet = absorb_forced();
                if (forced_meet >= 0) return build_answer(forced_meet);
            }
            if (exact_distance && (++rebuild_events >= rebuild_period)) {
                rebuild_events = 0;
                compute_distances_without_closed(adj, closed, nodes[1], dist[0], distance_queue[0]);
                compute_distances_without_closed(adj, closed, nodes[0], dist[1], distance_queue[1]);
#ifdef D_USE_TWO_HEAP
                rebuild_heap_side(0);
                rebuild_heap_side(1);
#endif
            }
        }
    }
}

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 = choose_chunk_bits(n, num_agents);
    int rows = (n + 1) / 2;
    int room_count = rows * rows;
    int edge_count = static_cast<int>(edges.size());
    vector<vector<int>> orders;
#ifdef D_MULTI_ORDER
    int order_classes = max(1, D_MULTI_ORDER);
    int order_modes[4] = {-1, 3, 5, 6};
    orders.reserve(order_classes);
    for (int cls = 0; cls < order_classes; ++cls) {
        orders.push_back(build_priority_order(n, num_agents, edges, order_modes[cls % 4]));
    }
#else
    int order_classes = 1;
    orders.push_back(build_priority_order(n, num_agents, edges));
#endif
    int workers = num_agents - 1;
    bool use_group_collect =
#ifdef D_STREAM_GROUP_COLLECT
        (num_agents >= 30 && max_msg_len >= 180)
#else
        (((n <= 151 && num_agents >= 37) || (n <= 166 && num_agents >= 45)) &&
         max_msg_len >= 180)
#endif
        ;
#ifdef D_MULTI_ORDER
    use_group_collect = false;
#endif
    int group_size =
#ifdef D_STREAM_GROUP_SIZE
        D_STREAM_GROUP_SIZE;
#else
        4;
#endif
    auto group_leader = [&](int id) {
        return 1 + ((id - 1) / group_size) * group_size;
    };
    auto worker_final = [&](int id, int phase) {
        int worker = id - 1;
        int base = (1 + phase * workers + worker) * chunk_bits;
        return base + workers * chunk_bits >= edge_count;
    };
    auto worker_active = [&](int id, int phase) {
        return phase == 0 || !worker_final(id, phase - 1);
    };
    auto append_group_entry = [&](string &body, int sender, const string &payload) {
        body += to_string(sender);
        body.push_back(',');
        body += to_string(static_cast<int>(payload.size()));
        body.push_back(',');
        body += payload;
    };
    auto order_class = [&](int id) {
        return id % order_classes;
    };
    auto class_worker_count = [&](int cls) {
        int count = 0;
        for (int id = 1; id < num_agents; ++id) {
            if (order_class(id) == cls) ++count;
        }
        return count;
    };
    auto class_worker_pos = [&](int id) {
        int cls = order_class(id);
        int count = 0;
        for (int other = 1; other < id; ++other) {
            if (order_class(other) == cls) ++count;
        }
        return count;
    };
    auto worker_base = [&](int id, int phase) {
#ifdef D_MULTI_ORDER
        int cls = order_class(id);
        int offset = (cls == 0 ? 1 : 0);
        int count = class_worker_count(cls);
        return (offset + phase * count + class_worker_pos(id)) * chunk_bits;
#else
        int worker = id - 1;
        return (1 + phase * workers + worker) * chunk_bits;
#endif
    };
    auto worker_stride = [&](int id) {
#ifdef D_MULTI_ORDER
        return class_worker_count(order_class(id)) * chunk_bits;
#else
        return workers * chunk_bits;
#endif
    };
    auto edge_at = [&](int id, int pos) {
        return orders[order_class(id)][pos];
    };

    if (agent_id != 0) {
        for (int phase = 0;; ++phase) {
            int base = worker_base(agent_id, phase);
            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 = edge_at(agent_id, 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 + worker_stride(agent_id) >= 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()));
            if (use_group_collect) {
                string member_body = header + payload;
                int leader = group_leader(agent_id);
                if (agent_id != leader) {
                    send_message_to(leader, "A" + member_body);
                    if (is_final) {
                        send_line("halt");
                        return;
                    }
                    continue;
                }

                string group_body = "H";
                append_group_entry(group_body, agent_id, member_body);
                int group_end = min(num_agents - 1, leader + group_size - 1);
                int need = 0;
                for (int member = leader + 1; member <= group_end; ++member) {
                    if (worker_active(member, phase)) ++need;
                }

                int got = 0;
                while (got < need) {
                    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] != 'A') continue;
                    append_group_entry(group_body, sender, body.substr(1));
                    ++got;
                }

                send_message_to_zero(group_body);
                if (is_final) {
                    send_line("halt");
                    return;
                }
                continue;
            }

            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;

    auto apply_stream_body = [&](int sender, const string &body) {
        if (body.empty() || (body[0] != 'S' && body[0] != 'F')) return;

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

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

        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 = edge_at(sender, base + j);
            open_edge[edge_id] = 1;
            dsu.unite(edges[edge_id].a, edges[edge_id].b);
        }
    };

    int local_count = min(chunk_bits, edge_count);
    for (int j = 0; j < local_count; ++j) {
        int edge_id = orders[0][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 (use_group_collect && !body.empty() && body[0] == 'H') {
            size_t pos = 1;
            while (pos < body.size()) {
                size_t comma1 = body.find(',', pos);
                if (comma1 == string::npos) break;
                size_t comma2 = body.find(',', comma1 + 1);
                if (comma2 == string::npos) break;
                int original_sender = stoi(body.substr(pos, comma1 - pos));
                int len = stoi(body.substr(comma1 + 1, comma2 - comma1 - 1));
                size_t payload_start = comma2 + 1;
                if (payload_start + len > body.size()) break;
                apply_stream_body(original_sender, body.substr(payload_start, len));
                pos = payload_start + len;
            }
            continue;
        }
        if (body.empty() || (body[0] != 'S' && body[0] != 'F')) continue;

        apply_stream_body(sender, body);
    }

    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());
    int search_agent_cap =
#ifdef D_SEARCH_AGENT_CAP
        D_SEARCH_AGENT_CAP
#else
        6
#endif
        ;

    if (!(NUM_AGENTS <= search_agent_cap) &&
        (NUM_AGENTS == 7 ||
        (NUM_AGENTS >= 8 &&
#ifdef D_STREAM_ALL_HIGH
         (N >= D_STREAM_ALL_HIGH || N >= 151 || N >= 101 || (N >= 93 && NUM_AGENTS >= 10))
#else
         (N >= 151 || N >= 101 || (N >= 93 && NUM_AGENTS >= 10))
#endif
        ))) {
        prioritized_streaming_scan(N, NUM_AGENTS, AGENT_ID, MAX_MSG_LEN, edges);
        return 0;
    }

    bool use_search_portfolio = NUM_AGENTS <= search_agent_cap;
    if (use_search_portfolio) {
        string path;
        bool use_frontier = N <=
#ifdef D_FRONTIER_LIMIT
            D_FRONTIER_LIMIT
#else
            351
#endif
            ;
        bool exact_frontier = N <=
#ifdef D_EXACT_LIMIT
            D_EXACT_LIMIT
#else
            351
#endif
            ;
        int frontier_variant = (NUM_AGENTS == 3 ? 5 : 0);
        if (NUM_AGENTS == 4 && AGENT_ID == 0) frontier_variant = 3;
        if (use_frontier) {
            int role = -1;  // 0: from start, 1: from goal, 2: two-sided
            int variant = frontier_variant;
            bool use_forced = false;

            if (AGENT_ID == 0) {
                role = 0;
            } else if (AGENT_ID == 1) {
                role = 1;
                variant = 5;
            } else if (AGENT_ID == 2) {
                role = 2;
                if (NUM_AGENTS == 4) variant = 3;
            } else if (AGENT_ID == 3) {
                role = 2;
                variant = 5;
            } else if (AGENT_ID == 4) {
                role = 2;
                variant = 3;
            } else if (AGENT_ID == 5) {
                role = 1;
                variant = 5;
            }

#ifdef D_ROLE_0
            if (AGENT_ID == 0) { role = D_ROLE_0; variant = D_VARIANT_0; }
#endif
#ifdef D_ROLE_1
            if (AGENT_ID == 1) { role = D_ROLE_1; variant = D_VARIANT_1; }
#endif
#ifdef D_ROLE_2
            if (AGENT_ID == 2) { role = D_ROLE_2; variant = D_VARIANT_2; }
#endif
#ifdef D_ROLE_3
            if (AGENT_ID == 3) { role = D_ROLE_3; variant = D_VARIANT_3; }
#endif
#ifdef D_ROLE_4
            if (AGENT_ID == 4) { role = D_ROLE_4; variant = D_VARIANT_4; }
#endif
#ifdef D_ROLE_5
            if (AGENT_ID == 5) { role = D_ROLE_5; variant = D_VARIANT_5; }
#endif
#ifdef D_FORCED_0
            if (AGENT_ID == 0) use_forced = D_FORCED_0;
#endif
#ifdef D_FORCED_1
            if (AGENT_ID == 1) use_forced = D_FORCED_1;
#endif
#ifdef D_FORCED_2
            if (AGENT_ID == 2) use_forced = D_FORCED_2;
#endif
#ifdef D_FORCED_3
            if (AGENT_ID == 3) use_forced = D_FORCED_3;
#endif
#ifdef D_FORCED_4
            if (AGENT_ID == 4) use_forced = D_FORCED_4;
#endif
#ifdef D_FORCED_5
            if (AGENT_ID == 5) use_forced = D_FORCED_5;
#endif

            if (role == 0) {
                path = frontier_one_sided_search(N, false, exact_frontier, variant, edges, use_forced);
            } else if (role == 1) {
                path = frontier_one_sided_search(N, true, exact_frontier, variant, edges, use_forced);
            } else if (role == 2) {
                path = frontier_two_sided_search(N, exact_frontier, variant, edges, use_forced);
            }
        }
        if (path.empty()) {
            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);
    bool use_priority_fallback =
#ifdef D_FALLBACK_PRIORITY
        D_FALLBACK_PRIORITY
#else
        (NUM_AGENTS >= 30 && N < 93)
#endif
        ;
    vector<int> scan_order;
    if (use_priority_fallback) {
        scan_order = build_priority_order(N, NUM_AGENTS, edges);
    } else {
        scan_order.resize(edge_count);
        for (int i = 0; i < edge_count; ++i) scan_order[i] = i;
    }
    bool use_group_collect = use_priority_fallback && NUM_AGENTS >= 30;
    int group_size =
#ifdef D_FALLBACK_GROUP_SIZE
        D_FALLBACK_GROUP_SIZE;
#else
        6;
#endif
    auto group_leader = [&](int id) {
        return 1 + ((id - 1) / group_size) * group_size;
    };
    auto append_group_entry = [&](string &body, int sender, const string &payload) {
        body += to_string(sender);
        body.push_back(',');
        body += to_string(static_cast<int>(payload.size()));
        body.push_back(',');
        body += payload;
    };

    vector<unsigned char> local_bits;
    local_bits.reserve(my_count);

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

    if (AGENT_ID != 0) {
        if (use_group_collect) {
            string payload = encode_bits(local_bits, 0, MAX_MSG_LEN);
            int leader = group_leader(AGENT_ID);
            if (AGENT_ID != leader) {
                send_message_to(leader, "A" + payload);
                send_line("halt");
                return 0;
            }

            string body = "G";
            append_group_entry(body, AGENT_ID, payload);
            int group_end = min(NUM_AGENTS - 1, leader + group_size - 1);
            int need = group_end - leader;
            int got = 0;
            while (got < need) {
                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 member_body = reply.substr(space + 1);
                if (member_body.empty() || member_body[0] != 'A') continue;
                append_group_entry(body, sender, member_body.substr(1));
                ++got;
            }

            send_message_to_zero(body);
            send_line("halt");
            return 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);
    Dsu dsu(room_id((N + 1) / 2, (N + 1) / 2 - 1, (N + 1) / 2 - 1) + 1);
    for (int i = 0; i < my_count; ++i) {
        int order_pos = i * NUM_AGENTS;
        int edge_id = scan_order[order_pos];
        open_edge[edge_id] = local_bits[i];
        if (open_edge[edge_id]) dsu.unite(edges[edge_id].a, edges[edge_id].b);
    }
    if (dsu.same(0, ((N + 1) / 2) * ((N + 1) / 2) - 1)) {
        string path = build_path_from_edges(N, edges, open_edge);
        if (!path.empty()) {
            send_line("! " + path);
            return 0;
        }
    }

    auto apply_sender_payload = [&](int sender, const string &payload) {
        int sender_count = assigned_count(edge_count, NUM_AGENTS, sender);
        vector<unsigned char> bits = decode_bits(payload, sender_count);
        for (int local_pos = 0; local_pos < sender_count; ++local_pos) {
            if (!bits[local_pos]) continue;
            int order_pos = sender + local_pos * NUM_AGENTS;
            if (order_pos >= edge_count) break;
            int edge_id = scan_order[order_pos];
            open_edge[edge_id] = 1;
            dsu.unite(edges[edge_id].a, edges[edge_id].b);
        }
    };

    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 (use_group_collect && !body.empty() && body[0] == 'G') {
            size_t pos = 1;
            while (pos < body.size()) {
                size_t comma1 = body.find(',', pos);
                if (comma1 == string::npos) break;
                size_t comma2 = body.find(',', comma1 + 1);
                if (comma2 == string::npos) break;
                int original_sender = stoi(body.substr(pos, comma1 - pos));
                int len = stoi(body.substr(comma1 + 1, comma2 - comma1 - 1));
                size_t payload_start = comma2 + 1;
                if (payload_start + len > body.size()) break;
                apply_sender_payload(original_sender, body.substr(payload_start, len));
                if (!finished[original_sender]) {
                    finished[original_sender] = 1;
                    ++done;
                }
                pos = payload_start + len;
            }

            if (dsu.same(0, ((N + 1) / 2) * ((N + 1) / 2) - 1)) {
                string path = build_path_from_edges(N, edges, open_edge);
                if (!path.empty()) {
                    send_line("! " + path);
                    return 0;
                }
            }
            continue;
        }

        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 order_pos = sender + local_pos * NUM_AGENTS;
                if (order_pos < edge_count && ((val >> b) & 1)) {
                    int edge_id = scan_order[order_pos];
                    open_edge[edge_id] = 1;
                    dsu.unite(edges[edge_id].a, edges[edge_id].b);
                }
            }
        }

        if (dsu.same(0, ((N + 1) / 2) * ((N + 1) / 2) - 1)) {
            string path = build_path_from_edges(N, edges, open_edge);
            if (!path.empty()) {
                send_line("! " + path);
                return 0;
            }
        }
    }

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