#include <algorithm>
#include <array>
#include <cstdlib>
#include <iostream>
#include <numeric>
#include <queue>
#include <string>
#include <tuple>
#include <vector>

using namespace std;

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

struct EdgeInfo {
    int r;
    int c;
    int a;
    int b;
};

struct DSU {
    vector<int> p;
    vector<unsigned char> rankv;

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

    void init(int n) {
        p.resize(n);
        rankv.assign(n, 0);
        iota(p.begin(), p.end(), 0);
    }

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

    bool unite(int a, int b) {
        a = find(a);
        b = find(b);
        if (a == b) return false;
        if (rankv[a] < rankv[b]) swap(a, b);
        p[b] = a;
        if (rankv[a] == rankv[b]) ++rankv[a];
        return true;
    }
};

string command_reply(const string& command) {
    cout << command << '\n' << flush;
    string reply;
    if (!getline(cin, reply)) exit(0);
    return reply;
}

[[noreturn]] void finish_with(const string& command) {
    cout << command << '\n' << flush;
    exit(0);
}

int decode_char(char ch) {
    if ('0' <= ch && ch <= '9') return ch - '0';
    if ('A' <= ch && ch <= 'Z') return 10 + (ch - 'A');
    if ('a' <= ch && ch <= 'z') return 36 + (ch - 'a');
    if (ch == '+') return 62;
    if (ch == '-') return 63;
    return 0;
}

char encode_char(int x) { return ALPHABET[x & 63]; }

string encode_bits(const vector<unsigned char>& bits, int count) {
    string out;
    out.reserve((count + 5) / 6);
    for (int i = 0; i < count; i += 6) {
        int v = 0;
        for (int b = 0; b < 6 && i + b < count; ++b) {
            if (bits[i + b]) v |= 1 << b;
        }
        out.push_back(encode_char(v));
    }
    return out;
}

bool encoded_bit(const string& encoded, int bit_index) {
    int pos = bit_index / 6;
    if (pos < 0 || pos >= (int)encoded.size()) return false;
    return ((decode_char(encoded[pos]) >> (bit_index % 6)) & 1) != 0;
}


// Denser printable bitset codec used for fixed-scan aggregation.
// It packs 13 bits into 2 chars from '!'..'~' (no spaces), so messages
// remain simple to parse while gaining about 8% capacity over base64-like bits.
int bit_capacity94(int max_msg_len) {
    if (max_msg_len <= 1) return 0;
    return ((max_msg_len - 1) / 2) * 13;
}

char enc94(int x) { return char('!' + x); }

int dec94(char ch) {
    if (ch < '!' || ch > '~') return 0;
    return ch - '!';
}

string encode_bits94(const vector<unsigned char>& bits, int count) {
    string out;
    out.reserve(2 * ((count + 12) / 13));
    for (int i = 0; i < count; i += 13) {
        int v = 0;
        for (int b = 0; b < 13 && i + b < count; ++b) {
            if (bits[i + b]) v |= 1 << b;
        }
        out.push_back(enc94(v % 94));
        out.push_back(enc94(v / 94));
    }
    return out;
}

bool encoded_bit94(const string& encoded, int bit_index) {
    int pos = 2 * (bit_index / 13);
    if (pos < 0 || pos + 1 >= (int)encoded.size()) return false;
    int v = dec94(encoded[pos]) + 94 * dec94(encoded[pos + 1]);
    return ((v >> (bit_index % 13)) & 1) != 0;
}

string encode_id3(int id) {
    string out(3, '0');
    out[0] = encode_char(id & 63);
    out[1] = encode_char((id >> 6) & 63);
    out[2] = encode_char((id >> 12) & 63);
    return out;
}

int decode_id3(const string& s, int pos) {
    return decode_char(s[pos]) | (decode_char(s[pos + 1]) << 6) |
           (decode_char(s[pos + 2]) << 12);
}

EdgeInfo edge_info(int idx, int m) {
    const int horizontal = m * (m - 1);
    if (idx < horizontal) {
        int row = idx / (m - 1);
        int col = idx % (m - 1);
        int a = row * m + col;
        return EdgeInfo{2 * row + 1, 2 * col + 2, a, a + 1};
    }
    int k = idx - horizontal;
    int row = k / m;
    int col = k % m;
    int a = row * m + col;
    return EdgeInfo{2 * row + 2, 2 * col + 1, a, a + m};
}

void incident_edges(int v, int m, vector<pair<int, int>>& out) {
    out.clear();
    int i = v / m;
    int j = v % m;
    int horizontal = m * (m - 1);
    if (j + 1 < m) out.push_back({i * (m - 1) + j, v + 1});
    if (j > 0) out.push_back({i * (m - 1) + j - 1, v - 1});
    if (i + 1 < m) out.push_back({horizontal + i * m + j, v + m});
    if (i > 0) out.push_back({horizontal + (i - 1) * m + j, v - m});
}

char move_between(int from, int to, int m) {
    if (to == from + 1) return 'R';
    if (to == from - 1) return 'L';
    if (to == from + m) return 'D';
    return 'U';
}

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

string doubled_room_path(const string& room_path) {
    string claim;
    claim.reserve(room_path.size() * 2);
    for (char ch : room_path) {
        claim.push_back(ch);
        claim.push_back(ch);
    }
    return claim;
}

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

long long order_key(int idx, int m) {
    const int horizontal = m * (m - 1);
    int x2, y2;
    if (idx < horizontal) {
        int row = idx / (m - 1);
        int col = idx % (m - 1);
        x2 = 2 * row;
        y2 = 2 * col + 1;
    } else {
        int k = idx - horizontal;
        int row = k / m;
        int col = k % m;
        x2 = 2 * row + 1;
        y2 = 2 * col;
    }
    int diagonal = abs(x2 - y2);
    int anti = abs(x2 + y2 - 2 * (m - 1));
    int end_bias = min(x2 + y2, 4 * (m - 1) - x2 - y2);
    return 1000000LL * diagonal + 90000LL * anti - 100LL * end_bias + idx;
}

vector<int> make_order(int m) {
    int total_edges = 2 * m * (m - 1);
    vector<int> order(total_edges);
    iota(order.begin(), order.end(), 0);
    stable_sort(order.begin(), order.end(), [m](int a, int b) {
        long long ka = order_key(a, m);
        long long kb = order_key(b, m);
        if (ka != kb) return ka < kb;
        return a < b;
    });
    return order;
}

struct GlobalGraph {
    int m;
    int vertices;
    vector<unsigned char> added;
    vector<vector<pair<int, char>>> adj;
    DSU dsu;

    GlobalGraph(int m_, int edge_count)
        : m(m_),
          vertices(m_ * m_),
          added(edge_count, 0),
          adj(vertices),
          dsu(vertices) {}

    bool add_edge(int eid) {
        if (eid < 0 || eid >= (int)added.size() || added[eid]) return false;
        added[eid] = 1;
        EdgeInfo e = edge_info(eid, m);
        char ab = move_between(e.a, e.b, m);
        char ba = inverse_move(ab);
        dsu.unite(e.a, e.b);
        adj[e.a].push_back({e.b, ab});
        adj[e.b].push_back({e.a, ba});
        return true;
    }

    bool connected() { return dsu.find(0) == dsu.find(vertices - 1); }

    string build_claim() {
        vector<int> parent(vertices, -1);
        vector<char> parent_move(vertices, 0);
        queue<int> q;
        parent[0] = 0;
        q.push(0);
        while (!q.empty() && parent[vertices - 1] == -1) {
            int u = q.front();
            q.pop();
            for (auto [v, ch] : adj[u]) {
                if (parent[v] != -1) continue;
                parent[v] = u;
                parent_move[v] = ch;
                q.push(v);
                if (v == vertices - 1) break;
            }
        }
        if (parent[vertices - 1] == -1) return string();
        string room_path;
        for (int cur = vertices - 1; cur != 0; cur = parent[cur]) {
            room_path.push_back(parent_move[cur]);
        }
        reverse(room_path.begin(), room_path.end());
        return doubled_room_path(room_path);
    }
};

void maybe_claim(GlobalGraph& graph) {
    if (!graph.connected()) return;
    string claim = graph.build_claim();
    finish_with("! " + claim);
}

struct Explorer {
    struct Item {
        long long key;
        int serial;
        int from;
        int to;
        int eid;
        bool operator>(const Item& other) const {
            if (key != other.key) return key > other.key;
            return serial > other.serial;
        }
    };

    int m;
    int id;
    int side;
    int mode;
    int start;
    int target;
    int serial = 0;
    vector<unsigned char> owned;
    vector<int> depth;
    vector<int> parent;
    vector<char> parent_move;
    vector<signed char>* known;
    priority_queue<Item, vector<Item>, greater<Item>> pq;
    vector<pair<int, int>> scratch;

    static int alternate_side(int id_) { return (id_ + (id_ / 2)) & 1; }

    static int select_side(int m_, int id_, int agents_) {
        if (agents_ >= 6) return alternate_side(id_);
        if (agents_ == 5 && ((m_ >= 120 && m_ <= 160) || m_ >= 180)) {
            return alternate_side(id_);
        }
        if (agents_ == 3 && m_ >= 240) return alternate_side(id_);
        return id_ & 1;
    }

    static int select_mode(int m_, int id_, int agents_) {
        if (agents_ == 3) {
            if ((m_ >= 70 && m_ <= 85) || (m_ >= 146 && m_ <= 165) ||
                (m_ >= 186 && m_ <= 195)) {
                return id_ & 7;
            }
            static const int mode_map[3] = {1, 2, 3};
            return mode_map[id_];
        }
        if (agents_ == 5 && m_ >= 120) {
            static const int mode5[5] = {1, 7, 5, 7, 5};
            return mode5[id_ % 5];
        }
        if (agents_ <= 5) return id_ & 7;
        return (id_ / 2) & 7;
    }

    Explorer(int m_, int id_, int agents_, vector<signed char>& known_,
             int side_override = -1, int mode_override = -1)
        : m(m_),
          id(id_),
          side(side_override >= 0 ? side_override : select_side(m_, id_, agents_)),
          mode(mode_override >= 0 ? mode_override : select_mode(m_, id_, agents_)),
          start(side == 0 ? 0 : m_ * m_ - 1),
          target(side == 0 ? m_ * m_ - 1 : 0),
          owned(m_ * m_, 0),
          depth(m_ * m_, 0),
          parent(m_ * m_, -1),
          parent_move(m_ * m_, 0),
          known(&known_) {
        owned[start] = 1;
        parent[start] = start;
        push_vertex(start);
    }

    int heuristic(int v) const {
        int r = v / m;
        int c = v % m;
        int tr = target / m;
        int tc = target % m;
        return abs(r - tr) + abs(c - tc);
    }

    long long make_key(int from, int to, int eid) const {
        int d = depth[from] + 1;
        int h = heuristic(to);
        int r = to / m;
        int c = to % m;
        int diag = abs(r - c);
        int progress = side == 0 ? (r + c) : (2 * (m - 1) - r - c);
        int rnd = (int)(splitmix64((unsigned long long)(eid + 1) * 1000003ULL +
                                   (unsigned long long)(id + 17) * 9176ULL) &
                        1023ULL);
        switch (mode) {
            case 0:
                return 10000LL * (d + h) + rnd;
            case 1:
                return 10000LL * h + 300LL * d + 4LL * rnd;
            case 2:
                return 10000LL * h + 3200LL * diag + rnd;
            case 3:
                return 4500LL * h - 10000LL * d + rnd;
            case 4:
                return 10000LL * h + 2500LL * abs(progress - (m - 1)) + rnd;
            case 5:
                return 10000LL * h + 1200LL * diag + 40LL * rnd;
            case 6:
                return 6500LL * h + 10000LL * d + rnd;
            default:
                return 8000LL * h + 900LL * diag - 2500LL * d + rnd;
        }
    }

    void push_vertex(int v) {
        incident_edges(v, m, scratch);
        for (auto [eid, to] : scratch) {
            if ((*known)[eid] != -1 || owned[to]) continue;
            pq.push(Item{make_key(v, to, eid), serial++, v, to, eid});
        }
    }

    bool next_candidate(int& eid, int& from, int& to) {
        while (!pq.empty()) {
            Item it = pq.top();
            pq.pop();
            if ((*known)[it.eid] != -1) continue;
            if (!owned[it.from] || owned[it.to]) continue;
            eid = it.eid;
            from = it.from;
            to = it.to;
            return true;
        }
        return false;
    }

    bool absorb_open_edge(int eid) {
        if (eid < 0) return false;
        EdgeInfo e = edge_info(eid, m);
        vector<int> stack;

        auto take_vertex = [&](int v, int p) {
            owned[v] = 1;
            depth[v] = depth[p] + 1;
            parent[v] = p;
            parent_move[v] = move_between(p, v, m);
            stack.push_back(v);
        };

        if (owned[e.a] && !owned[e.b]) {
            take_vertex(e.b, e.a);
        } else if (owned[e.b] && !owned[e.a]) {
            take_vertex(e.a, e.b);
        } else {
            return false;
        }

        while (!stack.empty()) {
            int u = stack.back();
            stack.pop_back();
            incident_edges(u, m, scratch);
            for (auto [eid2, v] : scratch) {
                if ((*known)[eid2] == 1 && !owned[v]) {
                    take_vertex(v, u);
                }
            }
            push_vertex(u);
        }
        return true;
    }

    void apply_result(int eid, int from, int to, bool open) {
        (void)from;
        (void)to;
        (*known)[eid] = open ? 1 : 0;
        if (open) absorb_open_edge(eid);
    }

    bool reached() const { return owned[target]; }

    string build_own_claim() const {
        if (!reached()) return string();
        string room_path;
        if (side == 0) {
            for (int cur = target; cur != start; cur = parent[cur]) {
                room_path.push_back(parent_move[cur]);
            }
            reverse(room_path.begin(), room_path.end());
        } else {
            for (int cur = target; cur != start; cur = parent[cur]) {
                room_path.push_back(inverse_move(parent_move[cur]));
            }
        }
        return doubled_room_path(room_path);
    }
};

void explorer_turn(Explorer& explorer, GlobalGraph* graph,
                   vector<int>* opened_buffer) {
    int eid = -1, from = -1, to = -1;
    if (explorer.next_candidate(eid, from, to)) {
        EdgeInfo e = edge_info(eid, explorer.m);
        string reply = command_reply("? " + to_string(e.r) + " " + to_string(e.c));
        bool open = !reply.empty() && reply[0] == '1';
        explorer.apply_result(eid, from, to, open);
        if (open) {
            if (opened_buffer) opened_buffer->push_back(eid);
            if (graph) {
                graph->add_edge(eid);
                maybe_claim(*graph);
            }
            if (explorer.reached()) {
                finish_with("! " + explorer.build_own_claim());
            }
        }
    } else {
        command_reply(".");
    }
}


struct FrontierExplorer {
    struct Item {
        long long key;
        int serial;
        int from;
        int to;
        int eid;
        bool operator>(const Item& other) const {
            if (key != other.key) return key > other.key;
            return serial > other.serial;
        }
    };

    int m;
    int seed;
    int side;
    int mode;
    int start;
    int target;
    int serial = 0;
    vector<unsigned char> owned;
    vector<int> depth;
    vector<signed char>* known;
    priority_queue<Item, vector<Item>, greater<Item>> pq;
    queue<int> pending_vertices;
    vector<pair<int, int>> scratch;

    FrontierExplorer(int m_, int seed_, int side_, int mode_, vector<signed char>& known_)
        : m(m_),
          seed(seed_),
          side(side_),
          mode(mode_),
          start(side_ == 0 ? 0 : m_ * m_ - 1),
          target(side_ == 0 ? m_ * m_ - 1 : 0),
          owned(m_ * m_, 0),
          depth(m_ * m_, 0),
          known(&known_) {
        add_vertex(start, 0);
        process_vertices();
    }

    int heuristic(int v) const {
        int r = v / m;
        int c = v % m;
        int tr = target / m;
        int tc = target % m;
        return abs(r - tr) + abs(c - tc);
    }

    long long make_key(int from, int to, int eid) const {
        int d = depth[from] + 1;
        int h = heuristic(to);
        int r = to / m;
        int c = to % m;
        int diag = abs(r - c);
        int progress = side == 0 ? (r + c) : (2 * (m - 1) - r - c);
        int center_wave = abs(progress - (m - 1));
        int rnd = (int)(splitmix64((unsigned long long)(eid + 3) * 11995408973635179863ULL +
                                   (unsigned long long)(seed + 101) * 1013904223ULL) &
                        1023ULL);
        switch (mode) {
            case 0:
                return 10000LL * (d + h) + rnd;
            case 1:
                return 10000LL * h + 280LL * d + 4LL * rnd;
            case 2:
                return 10000LL * h + 3000LL * diag + rnd;
            case 3:
                return 4600LL * h - 9800LL * d + rnd;
            case 4:
                return 10000LL * h + 2200LL * center_wave + rnd;
            case 5:
                return 9200LL * h + 1200LL * diag - 900LL * d + 8LL * rnd;
            case 6:
                return 6500LL * h + 9000LL * d + rnd;
            default:
                return 7600LL * h + 800LL * diag - 2300LL * d + 16LL * rnd;
        }
    }

    void add_vertex(int v, int d) {
        if (owned[v]) return;
        owned[v] = 1;
        depth[v] = d;
        pending_vertices.push(v);
    }

    void process_vertices() {
        while (!pending_vertices.empty()) {
            int v = pending_vertices.front();
            pending_vertices.pop();
            incident_edges(v, m, scratch);
            for (auto [eid, to] : scratch) {
                if (owned[to]) continue;
                signed char st = (*known)[eid];
                if (st == 1) {
                    add_vertex(to, depth[v] + 1);
                } else if (st == -1) {
                    pq.push(Item{make_key(v, to, eid), serial++, v, to, eid});
                }
            }
        }
    }

    void notify_open(int eid) {
        EdgeInfo e = edge_info(eid, m);
        if (owned[e.a] && !owned[e.b]) add_vertex(e.b, depth[e.a] + 1);
        if (owned[e.b] && !owned[e.a]) add_vertex(e.a, depth[e.b] + 1);
        process_vertices();
    }

    bool next_candidate(int& eid, int& from, int& to) {
        process_vertices();
        while (!pq.empty()) {
            Item it = pq.top();
            pq.pop();
            if ((*known)[it.eid] != -1) continue;
            if (!owned[it.from] || owned[it.to]) continue;
            eid = it.eid;
            from = it.from;
            to = it.to;
            return true;
        }
        return false;
    }
};

void notify_frontiers(vector<FrontierExplorer>& frontiers, int eid) {
    for (auto& f : frontiers) f.notify_open(eid);
}

bool add_open_edge(GlobalGraph& graph, vector<FrontierExplorer>* frontiers, int eid) {
    bool fresh = graph.add_edge(eid);
    if (fresh && frontiers) notify_frontiers(*frontiers, eid);
    return fresh;
}


int infer_forced_edges(GlobalGraph& graph, vector<signed char>& known,
                       vector<FrontierExplorer>* frontiers) {
    if (graph.connected()) return 0;
    int V = graph.vertices;
    int E = (int)known.size();
    vector<int> root_id(V, -1), comp(V, -1);
    int comps = 0;
    for (int v = 0; v < V; ++v) {
        int r = graph.dsu.find(v);
        if (root_id[r] == -1) root_id[r] = comps++;
        comp[v] = root_id[r];
    }
    if (comps <= 1) return 0;

    vector<vector<pair<int,int>>> g(comps);
    int newly_closed = 0;
    for (int eid = 0; eid < E; ++eid) {
        if (known[eid] != -1) continue;
        EdgeInfo e = edge_info(eid, graph.m);
        int a = comp[e.a], b = comp[e.b];
        if (a == b) {
            known[eid] = 0;
            ++newly_closed;
        } else {
            g[a].push_back({b, eid});
            g[b].push_back({a, eid});
        }
    }

    vector<int> tin(comps, -1), low(comps, 0), parent(comps, -1),
                parent_edge(comps, -1), it(comps, 0), bridges;
    int timer = 0;
    for (int st = 0; st < comps; ++st) {
        if (tin[st] != -1) continue;
        tin[st] = low[st] = timer++;
        vector<int> stack;
        stack.push_back(st);
        while (!stack.empty()) {
            int u = stack.back();
            if (it[u] < (int)g[u].size()) {
                auto [v, eid] = g[u][it[u]++];
                if (eid == parent_edge[u]) continue;
                if (tin[v] == -1) {
                    parent[v] = u;
                    parent_edge[v] = eid;
                    tin[v] = low[v] = timer++;
                    stack.push_back(v);
                } else {
                    low[u] = min(low[u], tin[v]);
                }
            } else {
                stack.pop_back();
                if (parent[u] != -1) {
                    int p = parent[u];
                    low[p] = min(low[p], low[u]);
                    if (low[u] > tin[p]) bridges.push_back(parent_edge[u]);
                }
            }
        }
    }

    int forced = 0;
    for (int eid : bridges) {
        if (known[eid] == -1) {
            known[eid] = 1;
            add_open_edge(graph, frontiers, eid);
            ++forced;
        }
    }
    return forced + newly_closed;
}

void build_frontier_pool(int m, int id, int agents, vector<signed char>& known,
                         vector<FrontierExplorer>& frontiers) {
    frontiers.clear();
    frontiers.reserve(6);
    int base_seed = id * 97 + agents * 13 + m;
    frontiers.emplace_back(m, base_seed + 0, 0, 1, known);
    frontiers.emplace_back(m, base_seed + 1, 1, 1, known);
    frontiers.emplace_back(m, base_seed + 2, 0, 5, known);
    frontiers.emplace_back(m, base_seed + 3, 1, 5, known);
    if (agents <= 20 || m >= 130) {
        frontiers.emplace_back(m, base_seed + 4, 0, 3, known);
        frontiers.emplace_back(m, base_seed + 5, 1, 7, known);
    }
}

void frontier_pool_turn(vector<FrontierExplorer>& frontiers, int& rr, GlobalGraph& graph) {
    int cnt = (int)frontiers.size();
    for (int tries = 0; tries < cnt; ++tries) {
        int idx = rr % cnt;
        rr = (rr + 1) % max(1, cnt);
        int eid = -1, from = -1, to = -1;
        if (!frontiers[idx].next_candidate(eid, from, to)) continue;
        EdgeInfo e = edge_info(eid, frontiers[idx].m);
        string reply = command_reply("? " + to_string(e.r) + " " + to_string(e.c));
        bool open = !reply.empty() && reply[0] == '1';
        (*frontiers[idx].known)[eid] = open ? 1 : 0;
        if (open) {
            add_open_edge(graph, &frontiers, eid);
            maybe_claim(graph);
        }
        return;
    }
    command_reply(".");
}

int choose_adaptive_q_phase(int m, int agents, int max_msg_len) {
    int cap_ids = max(1, (max_msg_len - 1) / 3);
    int q = max(1, cap_ids - max(0, agents - 1));
    // For smaller adaptive cases, earlier reports/merges usually beat ultra-large batches.
    if (m <= 70) q = min(q, 48);
    else if (m <= 95 && agents >= 6) q = min(q, 64);
    return max(8, q);
}

void receive_adaptive_body(const string& body, GlobalGraph& graph,
                           vector<FrontierExplorer>* frontiers = nullptr,
                           vector<signed char>* known = nullptr,
                           Explorer* explorer = nullptr) {
    if (body.empty() || body[0] != 'A') return;
    for (int pos = 1; pos + 2 < (int)body.size(); pos += 3) {
        int eid = decode_id3(body, pos);
        if (known && eid >= 0 && eid < (int)known->size()) (*known)[eid] = 1;
        add_open_edge(graph, frontiers, eid);
        if (explorer) explorer->absorb_open_edge(eid);
    }
}

void run_adaptive(int n, int agents, int id, int max_msg_len, int m,
                  int total_edges, vector<signed char>& known) {
    int cap_ids = max(1, (max_msg_len - 1) / 3);
    int q_phase = choose_adaptive_q_phase(m, agents, max_msg_len);

    Explorer explorer(m, id, agents, known);

    if (id == 0) {
        GlobalGraph graph(m, total_edges);
        while (true) {
            for (int t = 0; t < q_phase; ++t) {
                explorer_turn(explorer, &graph, nullptr);
            }
            // Same turn in which workers send; their messages become readable next turn.
            explorer_turn(explorer, &graph, nullptr);
            for (int t = 0; t < agents - 1; ++t) {
                string reply = command_reply("< ?");
                if (reply != "- -") {
                    size_t sp = reply.find(' ');
                    if (sp != string::npos) {
                        receive_adaptive_body(reply.substr(sp + 1), graph, nullptr, &known, &explorer);
                        maybe_claim(graph);
                    }
                }
            }
        }
    } else {
        vector<int> pending;
        pending.reserve(cap_ids + 8);
        while (true) {
            for (int t = 0; t < q_phase; ++t) {
                explorer_turn(explorer, nullptr, &pending);
            }

            string body = "A";
            int take = min(cap_ids, (int)pending.size());
            for (int i = 0; i < take; ++i) body += encode_id3(pending[i]);
            if (take > 0) pending.erase(pending.begin(), pending.begin() + take);
            command_reply("> 0 " + body);

            for (int t = 0; t < agents - 1; ++t) {
                explorer_turn(explorer, nullptr, &pending);
            }
        }
    }
}


int choose_fixed_q(int m, int agents, int total_edges, int bit_cap) {
    int q_full = (total_edges + agents - 1) / agents;
    bool split_tiny_fast = (m <= 30 && agents >= 14 && q_full > 60);
    bool split_small_dense = (m <= 70 && agents >= 20 && q_full > 144);
    bool split_mid_high = (m <= 120 && agents >= 26 && q_full > 300);
    if (q_full <= bit_cap && q_full <= 512 && !split_tiny_fast && !split_small_dense &&
        !split_mid_high) {
        return max(1, q_full);
    }
    int base;
    if (m <= 35) {
        base = (m <= 30 && agents >= 14 ? 60 : 64);
    } else if (m <= 70) {
        base = agents <= 5 ? 96 : (agents >= 20 ? 144 : 128);
    } else if (m <= 120) {
        base = agents <= 5 ? 192
                           : (agents >= 48 ? 320
                                            : (agents >= 45 ? 352
                                                            : (agents >= 40 ? 384
                                                                            : (agents >= 30 ? 6 * agents : (agents >= 15 ? 10 * agents : 160)))));
    } else if (m <= 145) {
        base = (agents >= 50 && m <= 123) ? 384
                                           : ((agents >= 24 && m <= 137) ? 6 * agents
                                                                         : (agents >= 24 ? 320 : 256));
    } else if (m <= 180) {
        base = agents >= 15 ? min(384, 10 * agents) : 256;
    } else {
        base = 384;
        if (agents == 45) {
            if (m >= 190 && m <= 195) {
                base = 694;
            } else if (m >= 196 && m <= 205) {
                base = 320;
            } else if (m >= 226 && m <= 245) {
                base = 448;
            }
        } else if (agents == 48 && m >= 190 && m <= 195) {
            base = 440;
        } else if (agents == 49 && m >= 190 && m <= 195) {
            base = 432;
        } else if (agents >= 50 && m >= 190 && m <= 195) {
            base = 424;
        }
    }
    if (agents >= 40 && m >= 146 && m <= 190) base = max(base, 384);
    return max(1, min(bit_cap, base));
}

int choose_legacy_group_size(int q_turns, int agents, int bit_cap) {
    if (agents <= 2 || q_turns <= 0) return 1;
    int cap = min(agents, max(1, bit_cap / max(1, q_turns)));
    int best_g = 1;
    int best_cost = agents;  // direct-to-root exchange: send + A-1 receives.
    for (int g = 2; g <= cap; ++g) {
        int groups = (agents + g - 1) / g;
        int cost = (groups <= 1) ? g : (g + groups);
        if (cost < best_cost) {
            best_cost = cost;
            best_g = g;
        }
    }
    return best_g;
}



vector<int> choose_multilevel_fanins(int agents, int q_turns, int bit_cap) {
    int cap_records = max(1, bit_cap / max(1, q_turns));
    if (agents <= 2 || cap_records <= 1) return {};
    const int INF = 1000000000;
    vector<int> dp(cap_records + 1, INF), take(cap_records + 1, 0);
    dp[1] = 0;
    for (int x = 2; x <= cap_records; ++x) {
        dp[x] = x;
        take[x] = x;
        for (int d = 2; d * d <= x; ++d) {
            if (x % d) continue;
            if (dp[x / d] + d < dp[x]) {
                dp[x] = dp[x / d] + d;
                take[x] = d;
            }
            if (dp[d] + x / d < dp[x]) {
                dp[x] = dp[d] + x / d;
                take[x] = x / d;
            }
        }
    }
    int best_p = 1;
    int best_cost = agents;  // direct-to-root exchange length.
    for (int p2 = 2; p2 <= cap_records; ++p2) {
        int blocks = (agents + p2 - 1) / p2;
        int final_cost = (blocks <= 1 ? 0 : blocks);
        int cost = dp[p2] + final_cost;
        if (cost < best_cost) {
            best_cost = cost;
            best_p = p2;
        }
    }
    if (best_p == 1) return {};
    vector<int> fac;
    for (int x = best_p; x > 1; ) {
        int d = take[x] ? take[x] : x;
        fac.push_back(d);
        x /= d;
    }
    sort(fac.rbegin(), fac.rend());
    return fac;
}

void run_fixed_legacy(int n, int agents, int id, int max_msg_len, int m,
                      int total_edges, vector<signed char>& known) {
    int bit_cap = max(1, bit_capacity94(max_msg_len));
    int base_q = choose_fixed_q(m, agents, total_edges, bit_cap);
    vector<int> order = make_order(m);
    GlobalGraph graph(m, total_edges);
    vector<FrontierExplorer> frontiers;
    int frontier_rr = 0;
    if (id == 0) build_frontier_pool(m, id, agents, known, frontiers);
    Explorer idle_explorer(m, id, agents, known);

    auto idle_turn = [&]() {
        if (id == 0) {
            frontier_pool_turn(frontiers, frontier_rr, graph);
        } else {
            explorer_turn(idle_explorer, nullptr, nullptr);
        }
    };

    auto infer_epoch = [&]() {
        if (id == 0 && m <= 80 && !graph.connected()) {
            for (int rep = 0; rep < 3; ++rep) {
                int got = infer_forced_edges(graph, known, &frontiers);
                if (got == 0 || graph.connected()) break;
            }
            maybe_claim(graph);
        }
    };

    for (int epoch_start = 0; epoch_start < total_edges; epoch_start += agents * base_q) {
        int remaining_positions = total_edges - epoch_start;
        int q_turns = min(base_q, (remaining_positions + agents - 1) / agents);
        vector<unsigned char> bits(q_turns, 0);

        for (int t = 0; t < q_turns; ++t) {
            int pos = epoch_start + t * agents + id;
            if (pos < total_edges) {
                int eid = order[pos];
                if (known[eid] == -1) {
                    EdgeInfo e = edge_info(eid, m);
                    string reply =
                        command_reply("? " + to_string(e.r) + " " + to_string(e.c));
                    known[eid] = (!reply.empty() && reply[0] == '1') ? 1 : 0;
                } else {
                    idle_turn();
                }
                if (known[eid] == 1) {
                    idle_explorer.absorb_open_edge(eid);
                    if (idle_explorer.reached()) {
                        finish_with("! " + idle_explorer.build_own_claim());
                    }
                    bits[t] = 1;
                    if (id == 0) {
                        add_open_edge(graph, &frontiers, eid);
                        maybe_claim(graph);
                    }
                }
            } else {
                idle_turn();
            }
        }

        auto apply_bits_from_agent = [&](int sender, const string& encoded, int count) {
            for (int k = 0; k < count; ++k) {
                int pos = epoch_start + k * agents + sender;
                if (pos >= total_edges) continue;
                int eid = order[pos];
                bool bit = encoded_bit94(encoded, k);
                known[eid] = bit ? 1 : 0;
                if (bit) add_open_edge(graph, &frontiers, eid);
            }
            if (id == 0) maybe_claim(graph);
        };

        auto apply_group_bits = [&](int group_start2, int group_len2,
                                    const string& encoded) {
            for (int off = 0; off < group_len2; ++off) {
                int sender = group_start2 + off;
                for (int k = 0; k < q_turns; ++k) {
                    int pos = epoch_start + k * agents + sender;
                    if (pos >= total_edges) continue;
                    int eid = order[pos];
                    bool bit = encoded_bit94(encoded, off * q_turns + k);
                    known[eid] = bit ? 1 : 0;
                    if (bit) add_open_edge(graph, &frontiers, eid);
                }
            }
            if (id == 0) maybe_claim(graph);
        };

        auto copy_group_bits = [&](vector<unsigned char>& dst, int dst_record_off,
                                   const string& encoded, int records) {
            for (int off = 0; off < records; ++off) {
                for (int k = 0; k < q_turns; ++k) {
                    if (encoded_bit94(encoded, off * q_turns + k)) {
                        dst[(dst_record_off + off) * q_turns + k] = 1;
                    }
                }
            }
        };

        vector<int> fanins = choose_multilevel_fanins(agents, q_turns, bit_cap);
        // Multilevel aggregation wins when the fixed block is communication-heavy.
        // Keep the old two-level grouped exchange for very large blocks, where
        // early frontier probing during collection is usually more valuable.
        bool use_multi = !fanins.empty() && (q_turns <= 384 || agents >= 32);
        if (use_multi) {
            vector<unsigned char> agg(q_turns, 0);
            for (int k = 0; k < q_turns; ++k) agg[k] = bits[k];
            bool active = true;
            int block_size = 1;
            int block_start = id;
            int block_len = 1;

            for (int f : fanins) {
                int prev_block_size = block_size;
                int super_size = prev_block_size * f;
                int super_start = (id / super_size) * super_size;
                bool cur_leader = active && id == block_start;
                bool super_leader = cur_leader && id == super_start;
                int super_len = 0;
                vector<unsigned char> next_agg;

                if (super_leader) {
                    super_len = min(super_size, agents - super_start);
                    next_agg.assign(super_len * q_turns, 0);
                    for (int off = 0; off < block_len; ++off) {
                        for (int k = 0; k < q_turns; ++k) {
                            if (agg[off * q_turns + k]) next_agg[off * q_turns + k] = 1;
                        }
                    }
                }

                if (cur_leader && !super_leader) {
                    string body = "D" + encode_bits94(agg, block_len * q_turns);
                    command_reply("> " + to_string(super_start) + " " + body);
                    active = false;
                } else {
                    idle_turn();
                }

                int child_blocks = 0;
                if (super_leader) child_blocks = (super_len + prev_block_size - 1) / prev_block_size;
                for (int child = 1; child < f; ++child) {
                    if (super_leader && child < child_blocks) {
                        string reply = command_reply("< ?");
                        if (reply != "- -") {
                            size_t sp = reply.find(' ');
                            if (sp != string::npos) {
                                int sender = atoi(reply.c_str());
                                int expected_start = super_start + child * prev_block_size;
                                if (sender == expected_start) {
                                    string body = reply.substr(sp + 1);
                                    if (!body.empty() && body[0] == 'D') {
                                        int child_len = min(prev_block_size, agents - expected_start);
                                        string encoded = body.substr(1);
                                        copy_group_bits(next_agg, child * prev_block_size, encoded, child_len);
                                        if (id == 0) apply_group_bits(expected_start, child_len, encoded);
                                    }
                                }
                            }
                        }
                    } else {
                        idle_turn();
                    }
                }

                if (super_leader) {
                    agg.swap(next_agg);
                    block_start = super_start;
                    block_len = super_len;
                    active = true;
                }
                block_size = super_size;
            }

            int final_block_size = block_size;
            int final_blocks = (agents + final_block_size - 1) / final_block_size;
            bool final_leader = active && id == block_start;
            if (final_blocks > 1) {
                if (final_leader && id != 0) {
                    string body = "D" + encode_bits94(agg, block_len * q_turns);
                    command_reply("> 0 " + body);
                } else {
                    idle_turn();
                }
                if (id == 0) {
                    for (int b = 1; b < final_blocks; ++b) {
                        string reply = command_reply("< ?");
                        if (reply == "- -") continue;
                        size_t sp = reply.find(' ');
                        if (sp == string::npos) continue;
                        int sender = atoi(reply.c_str());
                        if (sender <= 0 || sender >= agents || sender % final_block_size != 0) continue;
                        string body = reply.substr(sp + 1);
                        if (body.empty() || body[0] != 'D') continue;
                        int len = min(final_block_size, agents - sender);
                        apply_group_bits(sender, len, body.substr(1));
                    }
                } else {
                    for (int b = 1; b < final_blocks; ++b) idle_turn();
                }
            } else {
                if (id == 0) maybe_claim(graph);
            }
            infer_epoch();
            continue;
        }

        int group_size = choose_legacy_group_size(q_turns, agents, bit_cap);
        int groups = (agents + group_size - 1) / group_size;
        int group_start = (id / group_size) * group_size;
        int group_end = min(agents, group_start + group_size);
        int group_count = group_end - group_start;
        bool collector = (id == group_start);

        auto process_member_bits = [&](int sender, const string& body,
                                       vector<unsigned char>* aggregate) {
            if (sender < group_start || sender >= group_end) return;
            if (body.empty() || body[0] != 'B') return;
            string encoded = body.substr(1);
            int off = sender - group_start;
            for (int k = 0; k < q_turns; ++k) {
                bool bit = encoded_bit94(encoded, k);
                if (aggregate && bit) (*aggregate)[off * q_turns + k] = 1;
                if (id == 0) {
                    int pos = epoch_start + k * agents + sender;
                    if (pos < total_edges) {
                        int eid = order[pos];
                        known[eid] = bit ? 1 : 0;
                        if (bit) add_open_edge(graph, &frontiers, eid);
                    }
                }
            }
            if (id == 0) maybe_claim(graph);
        };

        auto process_collector_body = [&](int sender, const string& body) {
            if (body.empty() || body[0] != 'C') return;
            if (sender <= 0 || sender >= agents) return;
            if (sender % group_size != 0) return;
            int g_start = sender;
            int g_count = min(group_size, agents - g_start);
            string encoded = body.substr(1);
            for (int off = 0; off < g_count; ++off) {
                int agent_id = g_start + off;
                for (int k = 0; k < q_turns; ++k) {
                    int pos = epoch_start + k * agents + agent_id;
                    if (pos >= total_edges) continue;
                    int eid = order[pos];
                    bool bit = encoded_bit94(encoded, off * q_turns + k);
                    known[eid] = bit ? 1 : 0;
                    if (bit) add_open_edge(graph, &frontiers, eid);
                }
            }
            maybe_claim(graph);
        };

        if (group_size <= 1) {
            if (id != 0) {
                string body = "B" + encode_bits94(bits, q_turns);
                command_reply("> 0 " + body);
                for (int t = 1; t < agents; ++t) idle_turn();
            } else if (agents > 1) {
                frontier_pool_turn(frontiers, frontier_rr, graph);
                for (int t = 1; t < agents; ++t) {
                    string reply = command_reply("< ?");
                    if (reply == "- -") continue;
                    size_t sp = reply.find(' ');
                    if (sp == string::npos) continue;
                    int sender = atoi(reply.c_str());
                    if (sender <= 0 || sender >= agents) continue;
                    string body = reply.substr(sp + 1);
                    if (body.empty() || body[0] != 'B') continue;
                    string encoded = body.substr(1);
                    for (int k = 0; k < q_turns; ++k) {
                        int pos = epoch_start + k * agents + sender;
                        if (pos >= total_edges) continue;
                        int eid = order[pos];
                        bool bit = encoded_bit94(encoded, k);
                        known[eid] = bit ? 1 : 0;
                        if (bit) add_open_edge(graph, &frontiers, eid);
                    }
                    maybe_claim(graph);
                }
            } else {
                maybe_claim(graph);
            }
            infer_epoch();
            continue;
        }

        if (!collector) {
            string body = "B" + encode_bits94(bits, q_turns);
            command_reply("> " + to_string(group_start) + " " + body);
            for (int t = 0; t < group_size - 1; ++t) idle_turn();
            if (groups > 1) {
                idle_turn();
                for (int t = 0; t < groups - 1; ++t) idle_turn();
            }
        } else {
            vector<unsigned char> aggregate(group_count * q_turns, 0);
            int self_off = id - group_start;
            for (int k = 0; k < q_turns; ++k) {
                if (bits[k]) aggregate[self_off * q_turns + k] = 1;
            }

            // Same turn in which non-collectors send their B messages.
            if (id == 0) {
                frontier_pool_turn(frontiers, frontier_rr, graph);
            } else {
                idle_turn();
            }

            for (int t = 0; t < group_size - 1; ++t) {
                if (t < group_count - 1) {
                    string reply = command_reply("< ?");
                    if (reply != "- -") {
                        size_t sp = reply.find(' ');
                        if (sp != string::npos) {
                            int sender = atoi(reply.c_str());
                            process_member_bits(sender, reply.substr(sp + 1), &aggregate);
                        }
                    }
                } else {
                    idle_turn();
                }
            }

            if (groups > 1) {
                if (id == 0) {
                    // Other collectors send their aggregate now; it is readable next turn.
                    frontier_pool_turn(frontiers, frontier_rr, graph);
                    for (int t = 0; t < groups - 1; ++t) {
                        string reply = command_reply("< ?");
                        if (reply == "- -") continue;
                        size_t sp = reply.find(' ');
                        if (sp == string::npos) continue;
                        int sender = atoi(reply.c_str());
                        process_collector_body(sender, reply.substr(sp + 1));
                    }
                } else {
                    string body = "C" + encode_bits94(aggregate, group_count * q_turns);
                    command_reply("> 0 " + body);
                    for (int t = 0; t < groups - 1; ++t) idle_turn();
                }
            }
        }
        infer_epoch();
    }

    if (id == 0) {
        string claim = graph.build_claim();
        if (!claim.empty() || n == 1) finish_with("! " + claim);
        finish_with("halt");
    } else {
        finish_with("halt");
    }
}


int choose_stream_q(int m, int agents, int total_edges, int bit_cap) {
    int workers = max(1, agents - 1);
    int q_full = (total_edges + workers - 1) / workers;

    // On tiny mazes, one full bitset round is faster than many small pipeline rounds.
    int full_limit = (m <= 70 ? 180 : 170);
    if (q_full <= bit_cap && q_full <= full_limit) {
        return max(workers, max(1, q_full));
    }

    // Small blocks almost hide communication: workers query during leader receive turns.
    // Tune the pipeline block by agent count and grid size.  Few-agent medium
    // rounds benefit from a larger block once reports are streaming; very small
    // A≈10 grids prefer earlier reports.  High-agent rounds keep 64 to avoid
    // delaying the first wave.
    int q = 64;
    if (agents <= 7) {
        if (m <= 65) q = 96;
        else if (m <= 170) q = 128;
        else q = 128;
    } else if (agents <= 13) {
        if (m <= 65) q = 40;
        else if (m <= 170) q = 80;
        else q = 128;
    } else if (agents <= 25) {
        if (m <= 90) q = 80;
        else if (m > 150) q = 192;
        else q = 128;
    } else {
        // High-agent medium boards were slightly under-batched: q=64 gives very
        // early reports but too many cycles.  Around m=120..160, A>=40 works
        // better with a modestly larger streaming wave while keeping latency low.
        if (m <= 160 && agents >= 40) q = 80;
        else q = (m <= 160 && agents <= 39) ? 96 : 64;
    }
    if (workers > q) q = workers;
    if (q > bit_cap) q = bit_cap;
    if (q < 1) q = 1;
    return q;
}

unsigned char query_fixed_position(long long order_pos, int total_edges,
                                   const vector<int>& order, int m) {
    if (order_pos >= 0 && order_pos < total_edges) {
        int eid = order[(int)order_pos];
        EdgeInfo e = edge_info(eid, m);
        string reply = command_reply("? " + to_string(e.r) + " " + to_string(e.c));
        return (!reply.empty() && reply[0] == '1') ? 1 : 0;
    }
    command_reply(".");
    return 0;
}

void run_stream_fixed(int n, int agents, int id, int max_msg_len, int m,
                      int total_edges, vector<signed char>& aux_known) {
    int bit_cap = max(1, (max_msg_len - 1) * 6);
    int workers = max(1, agents - 1);
    int q = choose_stream_q(m, agents, total_edges, bit_cap);
    if (q < workers) q = workers;
    if (q > bit_cap) q = bit_cap;

    vector<int> order = make_order(m);

    if (id != 0) {
        int worker = id - 1;  // 0..workers-1
        vector<unsigned char> bits(q, 0);
        int block = 0;
        int pref = 0;

        while (true) {
            for (int i = pref; i < q; ++i) {
                long long order_pos = (1LL * block * q + i) * workers + worker;
                bits[i] = query_fixed_position(order_pos, total_edges, order, m);
            }

            string body = "B" + encode_bits(bits, q);
            command_reply("> 0 " + body);

            ++block;
            fill(bits.begin(), bits.end(), 0);

            pref = min(workers, q);
            for (int i = 0; i < pref; ++i) {
                long long order_pos = (1LL * block * q + i) * workers + worker;
                bits[i] = query_fixed_position(order_pos, total_edges, order, m);
            }
        }
    }

    GlobalGraph graph(m, total_edges);
    vector<FrontierExplorer> frontiers;
    build_frontier_pool(m, id, agents, aux_known, frontiers);
    int frontier_rr = 0;
    vector<int> block_of_sender(agents, 0);
    int stream_aux_infer_counter = 0;

    auto infer_stream_once = [&]() {
        if (!graph.connected() && m >= 75) {
            int got = infer_forced_edges(graph, aux_known, &frontiers);
            (void)got;
            maybe_claim(graph);
        }
    };

    auto infer_stream_cycle = [&]() {
        if (!graph.connected() && m >= 75) {
            for (int rep = 0; rep < 2; ++rep) {
                int got = infer_forced_edges(graph, aux_known, &frontiers);
                if (got == 0 || graph.connected()) break;
            }
            maybe_claim(graph);
        }
    };

    auto leader_aux_turn = [&]() {
        frontier_pool_turn(frontiers, frontier_rr, graph);
        if (m <= 170 && agents >= 30) {
            // A closed result from a targeted frontier query can make a bridge
            // forced.  Throttle to every fourth auxiliary turn to keep CPU safe.
            if (((++stream_aux_infer_counter) & 3) == 0) infer_stream_once();
        }
    };

    // Initial warm-up: workers are filling their first block and sending it.
    for (int t = 0; t < q + 1; ++t) leader_aux_turn();

    while (true) {
        for (int read_i = 1; read_i <= workers; ++read_i) {
            string reply = command_reply("< ?");
            if (reply != "- -") {
                size_t sp = reply.find(' ');
                if (sp != string::npos) {
                    int sender = atoi(reply.c_str());
                    string body = reply.substr(sp + 1);
                    if (sender > 0 && sender <= workers && !body.empty() && body[0] == 'B') {
                        string encoded = body.substr(1);
                        int block = block_of_sender[sender]++;
                        int worker = sender - 1;
                        for (int k = 0; k < q; ++k) {
                            long long order_pos = (1LL * block * q + k) * workers + worker;
                            if (order_pos >= total_edges) continue;
                            int eid = order[(int)order_pos];
                            bool open = encoded_bit(encoded, k);
                            aux_known[eid] = open ? 1 : 0;
                            if (open) add_open_edge(graph, &frontiers, eid);
                        }
                        maybe_claim(graph);
                        // Medium/high-agent stream rounds can become solvable in the middle
                        // of the receive sweep once enough closed edges are known.  Run a
                        // cheap forced-bridge pass immediately instead of waiting for the
                        // end of the whole worker sweep.
                        if (m <= 170 && agents >= 30) infer_stream_once();
                    }
                }
            }
        }

        infer_stream_cycle();

        int aux_turns = q - workers + 1;
        if (aux_turns < 1) aux_turns = 1;
        for (int t = 0; t < aux_turns; ++t) leader_aux_turn();
    }
}


bool use_adaptive_mode(int m, int agents) {
    if (m < 25) return false;
    if (agents <= 5) return true;
    // 6..8 agents are enough to make adaptive competitive once the board is medium-sized.
    if (agents <= 8 && m >= 90) return true;
    return false;
}

bool use_legacy_fixed_mode(int m, int agents, int total_edges) {
    int q_full_agent = (total_edges + agents - 1) / agents;
    // Legacy fixed is excellent for one-shot / tiny scans, but on medium grids
    // with few agents it delays the first useful report until a whole huge chunk
    // is scanned.  Stream fixed reports partial chunks much earlier and is
    // markedly stronger on the later high-weight rounds.
    if (q_full_agent <= 180) return true;
    return false;
}

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

    int n, agents, id, max_msg_len;
    if (!(cin >> n >> agents >> id >> max_msg_len)) return 0;
    string rest;
    getline(cin, rest);

    if (n == 1) {
        if (id == 0)
            finish_with("!");
        else
            finish_with("halt");
    }

    int m = (n + 1) / 2;
    int total_edges = 2 * m * (m - 1);
    vector<signed char> known(total_edges, -1);

    if (use_adaptive_mode(m, agents)) {
        run_adaptive(n, agents, id, max_msg_len, m, total_edges, known);
    } else if (use_legacy_fixed_mode(m, agents, total_edges)) {
        run_fixed_legacy(n, agents, id, max_msg_len, m, total_edges, known);
    } else {
        run_stream_fixed(n, agents, id, max_msg_len, m, total_edges, known);
    }
    return 0;
}