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

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 id_, int agents_) {
        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(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;
    }

    void apply_result(int eid, int from, int to, bool open) {
        (*known)[eid] = open ? 1 : 0;
        if (open && !owned[to]) {
            owned[to] = 1;
            depth[to] = depth[from] + 1;
            parent[to] = from;
            parent_move[to] = move_between(from, to, m);
            push_vertex(to);
        }
    }

    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 (frontiers) notify_frontiers(*frontiers, eid);
    return fresh;
}

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) {
    if (body.empty() || body[0] != 'A') return;
    for (int pos = 1; pos + 2 < (int)body.size(); pos += 3) {
        add_open_edge(graph, frontiers, decode_id3(body, pos));
    }
}

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 = max(1, cap_ids - max(0, agents - 1));

    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);
                        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_small_dense = (m <= 70 && agents >= 30 && q_full > 256);
    bool split_mid_high = (m <= 120 && agents >= 26 && q_full > 300);
    if (q_full <= bit_cap && q_full <= 512 && !split_small_dense &&
        !split_mid_high) {
        return max(1, q_full);
    }
    int base;
    if (m <= 35) {
        base = 64;
    } else if (m <= 70) {
        base = agents <= 5 ? 96 : (agents >= 30 ? 256 : 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));
}

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, (max_msg_len - 1) * 6);
    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);

    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 {
                    command_reply(".");
                }
                if (known[eid] == 1) {
                    bits[t] = 1;
                    if (id == 0) {
                        add_open_edge(graph, &frontiers, eid);
                        maybe_claim(graph);
                    }
                }
            } else {
                command_reply(".");
            }
        }

        int group_cap = max(1, bit_cap / max(1, q_turns));
        int group_size = max(1, min(agents, group_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_bit(encoded, k);
                if (aggregate && bit) (*aggregate)[off * q_turns + k] = 1;
                if (id == 0 && bit) {
                    int pos = epoch_start + k * agents + sender;
                    if (pos < total_edges) add_open_edge(graph, &frontiers, order[pos]);
                }
            }
            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) {
                    if (!encoded_bit(encoded, off * q_turns + k)) continue;
                    int pos = epoch_start + k * agents + agent_id;
                    if (pos < total_edges) add_open_edge(graph, &frontiers, order[pos]);
                }
            }
            maybe_claim(graph);
        };

        if (!collector) {
            string body = "B" + encode_bits(bits, q_turns);
            command_reply("> " + to_string(group_start) + " " + body);
            for (int t = 0; t < group_size - 1; ++t) command_reply(".");
            if (groups > 1) {
                command_reply(".");
                for (int t = 0; t < groups - 1; ++t) command_reply(".");
            }
        } 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 {
                command_reply(".");
            }

            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 {
                    command_reply(".");
                }
            }

            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_bits(aggregate, group_count * q_turns);
                    command_reply("> 0 " + body);
                    for (int t = 0; t < groups - 1; ++t) command_reply(".");
                }
            }
        }
    }

    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.
    int q = 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);

    auto leader_aux_turn = [&]() {
        frontier_pool_turn(frontiers, frontier_rr, graph);
    };

    // 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 sender = 1; sender <= workers; ++sender) {
            string reply = command_reply("< " + to_string(sender));
            if (reply != "- -") {
                size_t sp = reply.find(' ');
                if (sp != string::npos) {
                    string body = reply.substr(sp + 1);
                    if (!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);
                    }
                }
            }
        }

        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 < 45) return false;
    if (agents <= 5) return true;
    if (agents <= 8 && m >= 170 && !(agents >= 7 && m >= 190 && m <= 240)) 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;
    if (q_full_agent <= 180) return true;
    if (agents < 14) 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;
}