#include <bits/stdc++.h>
using namespace std;

struct Edge {
    int a, b;
    int qr, qc;
    char dir;
};

static const string ALPH = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";
static const string B64 = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz+/";

string enc3(int x) {
    string s(3, '0');
    s[2] = ALPH[x % 62]; x /= 62;
    s[1] = ALPH[x % 62]; x /= 62;
    s[0] = ALPH[x % 62];
    return s;
}

int dec3(const string &s, int pos) {
    int x = 0;
    for (int k = 0; k < 3; k++) {
        char ch = s[pos + k];
        int v = ('0' <= ch && ch <= '9') ? ch - '0'
              : ('A' <= ch && ch <= 'Z') ? ch - 'A' + 10
                                          : ch - 'a' + 36;
        x = x * 62 + v;
    }
    return x;
}

string encode_bits(const vector<unsigned char> &bits) {
    string body;
    body.reserve((bits.size() + 5) / 6);
    for (int i = 0; i < (int)bits.size(); i += 6) {
        int v = 0;
        for (int k = 0; k < 6 && i + k < (int)bits.size(); k++) {
            if (bits[i + k]) v |= 1 << k;
        }
        body.push_back(B64[v]);
    }
    if (body.empty()) body = "0";
    return body;
}

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

struct MazeInfo {
    int N, m, rooms;
    vector<Edge> edges;
    vector<array<int, 4>> edge_at;
};

MazeInfo build_info(int N) {
    MazeInfo z;
    z.N = N;
    z.m = (N + 1) / 2;
    z.rooms = z.m * z.m;
    z.edge_at.assign(z.rooms, {-1, -1, -1, -1});
    for (int i = 0; i < z.m; i++) {
        for (int j = 0; j < z.m; j++) {
            int u = i * z.m + j;
            if (i + 1 < z.m) {
                int v = (i + 1) * z.m + j;
                int id = (int)z.edges.size();
                z.edges.push_back({u, v, 2 * i + 2, 2 * j + 1, 'D'});
                z.edge_at[u][2] = id;
                z.edge_at[v][0] = id;
            }
            if (j + 1 < z.m) {
                int v = i * z.m + (j + 1);
                int id = (int)z.edges.size();
                z.edges.push_back({u, v, 2 * i + 1, 2 * j + 2, 'R'});
                z.edge_at[u][3] = id;
                z.edge_at[v][1] = id;
            }
        }
    }
    return z;
}

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

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

void claim_room_path(const string &rooms_path) {
    string path;
    path.reserve(rooms_path.size() * 2);
    for (char ch : rooms_path) {
        path.push_back(ch);
        path.push_back(ch);
    }
    cout << "! " << path << endl;
}

void run_greedy_search(const MazeInfo &mz, int agent_id) {
    struct Param { int prog, dev, offset; bool rev; };
    static const Param params[] = {
        {100, 15,   0, false},
        { 60, 20, 100, true },
        { 50, 20, -30, true },
        { 50,  5,  50, false},
        {100, 40, -30, false},
        { 50, 20,   0, false},
        { 50,  0,   0, true },
        { 40, 20,   0, false},
        { 50, 20, -40, false},
        { 50, 20,  40, false},
    };
    int param_idx = agent_id % (int)(sizeof(params) / sizeof(params[0]));
    Param p = params[param_idx];
    if (mz.N < 400 && param_idx == 3) p = Param{30, 20, 30, false};

    int start = p.rev ? mz.rooms - 1 : 0;
    int target = p.rev ? 0 : mz.rooms - 1;

    vector<unsigned char> reached(mz.rooms, 0), asked(mz.edges.size(), 0);
    vector<int> dist(mz.rooms, INT_MAX), parent(mz.rooms, -1);

    struct Item {
        long long score;
        int tie, from, edge_id, to;
        bool operator<(const Item &o) const {
            if (score != o.score) return score > o.score;
            if (tie != o.tie) return tie > o.tie;
            return edge_id > o.edge_id;
        }
    };
    priority_queue<Item> pq;

    auto transformed = [&](int u) {
        int i = u / mz.m, j = u % mz.m;
        if (p.rev) {
            i = mz.m - 1 - i;
            j = mz.m - 1 - j;
        }
        return pair<int, int>(i, j);
    };
    auto score_of = [&](int v, int g) {
        auto [i, j] = transformed(v);
        int s = i + j;
        int d = abs(i - j - p.offset);
        return 1LL * g - 1LL * p.prog * s + 1LL * p.dev * d;
    };
    auto push_edges = [&](int u) {
        for (int d = 0; d < 4; d++) {
            int eid = mz.edge_at[u][d];
            if (eid < 0 || asked[eid]) continue;
            const Edge &e = mz.edges[eid];
            int v = e.a ^ e.b ^ u;
            if (reached[v]) continue;
            asked[eid] = 1;
            auto [ti, tj] = transformed(v);
            int h = (mz.m - 1 - ti) + (mz.m - 1 - tj);
            pq.push({score_of(v, dist[u] + 1), h, u, eid, v});
        }
    };

    reached[start] = 1;
    dist[start] = 0;
    push_edges(start);

    while (!pq.empty()) {
        Item it = pq.top();
        pq.pop();
        if (!reached[it.from] || reached[it.to]) continue;
        const Edge &e = mz.edges[it.edge_id];
        cout << "? " << e.qr << ' ' << e.qc << endl;
        string ans;
        if (!(cin >> ans)) return;
        if (ans != "1") continue;

        reached[it.to] = 1;
        dist[it.to] = dist[it.from] + 1;
        parent[it.to] = it.from;
        if (it.to == target) {
            string s;
            for (int v = target; v != start; v = parent[v]) {
                s.push_back(move_between(mz.m, parent[v], v));
            }
            reverse(s.begin(), s.end());
            if (p.rev) {
                string t;
                t.reserve(s.size());
                for (int i = (int)s.size() - 1; i >= 0; i--) t.push_back(inv_move(s[i]));
                s.swap(t);
            }
            claim_room_path(s);
            return;
        }
        push_edges(it.to);
    }

    cout << "halt" << endl;
}

void run_bidir_search(const MazeInfo &mz, int agent_id) {
    struct Param { int prog, dev, offset; };
    static const Param params[] = {
        {50, 20,   0},
        {50,  0,   0},
        {40, 20,   0},
        {50, 20, -40},
        {50, 20,  40},
    };
    Param p = params[agent_id % (int)(sizeof(params) / sizeof(params[0]))];
    int start = 0, goal = mz.rooms - 1;

    vector<signed char> side(mz.rooms, -1);
    vector<unsigned char> asked(mz.edges.size(), 0);
    vector<array<int, 2>> parent(mz.rooms);
    vector<array<int, 2>> dist(mz.rooms);
    for (int i = 0; i < mz.rooms; i++) {
        parent[i] = {-1, -1};
        dist[i] = {INT_MAX, INT_MAX};
    }

    struct Item {
        long long score;
        int tie, from, edge_id, to, side;
        bool operator<(const Item &o) const {
            if (score != o.score) return score > o.score;
            if (tie != o.tie) return tie > o.tie;
            return edge_id > o.edge_id;
        }
    };
    priority_queue<Item> pq;

    auto transformed = [&](int u, int s) {
        int i = u / mz.m, j = u % mz.m;
        if (s == 1) {
            i = mz.m - 1 - i;
            j = mz.m - 1 - j;
        }
        return pair<int, int>(i, j);
    };
    auto score_of = [&](int v, int g, int s) {
        auto [i, j] = transformed(v, s);
        int progress = i + j;
        int d = abs(i - j - p.offset);
        return 1LL * g - 1LL * p.prog * progress + 1LL * p.dev * d;
    };
    auto push_edges = [&](int u, int s) {
        for (int d = 0; d < 4; d++) {
            int eid = mz.edge_at[u][d];
            if (eid < 0 || asked[eid]) continue;
            const Edge &e = mz.edges[eid];
            int v = e.a ^ e.b ^ u;
            if (side[v] == s) continue;
            asked[eid] = 1;
            auto [ti, tj] = transformed(v, s);
            int h = (mz.m - 1 - ti) + (mz.m - 1 - tj);
            pq.push({score_of(v, dist[u][s] + 1, s), h, u, eid, v, s});
        }
    };
    auto start_path = [&](int node) {
        string out;
        for (int v = node; v != start; v = parent[v][0]) {
            int u = parent[v][0];
            if (u < 0) return string();
            out.push_back(move_between(mz.m, u, v));
        }
        reverse(out.begin(), out.end());
        return out;
    };
    auto goal_path = [&](int node) {
        string out;
        for (int v = node; v != goal; v = parent[v][1]) {
            int u = parent[v][1];
            if (u < 0) return string();
            out.push_back(move_between(mz.m, v, u));
        }
        return out;
    };
    auto claim_join = [&](int u, int v, int s) {
        string path;
        if (s == 0) {
            path = start_path(u);
            path.push_back(move_between(mz.m, u, v));
            path += goal_path(v);
        } else {
            path = start_path(v);
            path.push_back(move_between(mz.m, v, u));
            path += goal_path(u);
        }
        claim_room_path(path);
    };

    side[start] = 0;
    side[goal] = 1;
    dist[start][0] = 0;
    dist[goal][1] = 0;
    push_edges(start, 0);
    push_edges(goal, 1);

    while (!pq.empty()) {
        Item it = pq.top();
        pq.pop();
        if (side[it.from] != it.side || side[it.to] == it.side) continue;
        const Edge &e = mz.edges[it.edge_id];
        cout << "? " << e.qr << ' ' << e.qc << endl;
        string ans;
        if (!(cin >> ans)) return;
        if (ans != "1") continue;

        if (side[it.to] == 1 - it.side) {
            claim_join(it.from, it.to, it.side);
            return;
        }

        side[it.to] = it.side;
        parent[it.to][it.side] = it.from;
        dist[it.to][it.side] = dist[it.from][it.side] + 1;
        push_edges(it.to, it.side);
    }

    cout << "halt" << endl;
}


void run_full_restore(const MazeInfo &mz, int num_agents, int agent_id, int max_msg_len) {
    vector<int> mine;
    for (int e = agent_id; e < (int)mz.edges.size(); e += num_agents) {
        const Edge &ed = mz.edges[e];
        cout << "? " << ed.qr << ' ' << ed.qc << endl;
        string ans;
        if (!(cin >> ans)) return;
        if (ans == "1") mine.push_back(e);
    }

    if (agent_id != 0) {
        int per_msg = max(1, max_msg_len / 3);
        for (int i = 0; i < (int)mine.size(); i += per_msg) {
            string body;
            int lim = min((int)mine.size(), i + per_msg);
            body.reserve(3 * (lim - i));
            for (int j = i; j < lim; j++) body += enc3(mine[j]);
            cout << "> 0 " << body << endl;
            string ok;
            if (!(cin >> ok)) return;
        }
        cout << "> 0 ~" << endl;
        string ok;
        if (cin >> ok) cout << "halt" << endl;
        return;
    }

    vector<vector<pair<int, char>>> adj(mz.rooms);
    auto add_edge = [&](int idx) {
        const Edge &ed = mz.edges[idx];
        if (ed.dir == 'D') {
            adj[ed.a].push_back({ed.b, 'D'});
            adj[ed.b].push_back({ed.a, 'U'});
        } else {
            adj[ed.a].push_back({ed.b, 'R'});
            adj[ed.b].push_back({ed.a, 'L'});
        }
    };

    for (int idx : mine) add_edge(idx);

    int finished = 0;
    while (finished < num_agents - 1) {
        cout << "< ?" << endl;
        string sender, body;
        if (!(cin >> sender >> body)) return;
        if (sender == "-" && body == "-") continue;
        if (body == "~") {
            finished++;
            continue;
        }
        for (int pos = 0; pos + 2 < (int)body.size(); pos += 3) {
            int idx = dec3(body, pos);
            if (0 <= idx && idx < (int)mz.edges.size()) add_edge(idx);
        }
    }

    vector<int> parent(mz.rooms, -1);
    vector<char> step(mz.rooms, 0);
    queue<int> q;
    parent[0] = 0;
    q.push(0);
    while (!q.empty() && parent[mz.rooms - 1] == -1) {
        int u = q.front();
        q.pop();
        for (auto [v, ch] : adj[u]) {
            if (parent[v] != -1) continue;
            parent[v] = u;
            step[v] = ch;
            q.push(v);
            if (v == mz.rooms - 1) break;
        }
    }

    string room_path;
    for (int v = mz.rooms - 1; v != 0; v = parent[v]) {
        if (v < 0) return;
        room_path.push_back(step[v]);
    }
    reverse(room_path.begin(), room_path.end());
    claim_room_path(room_path);
}

struct Dsu {
    vector<int> p, sz;
    explicit Dsu(int n = 0) : p(n), sz(n, 1) {
        iota(p.begin(), p.end(), 0);
    }
    int find(int x) {
        while (p[x] != x) {
            p[x] = p[p[x]];
            x = p[x];
        }
        return x;
    }
    void unite(int a, int b) {
        a = find(a);
        b = find(b);
        if (a == b) return;
        if (sz[a] < sz[b]) swap(a, b);
        p[b] = a;
        sz[a] += sz[b];
    }
};

vector<int> build_priority_order(const MazeInfo &mz, int num_agents) {
    vector<int> order(mz.edges.size());
    iota(order.begin(), order.end(), 0);
    auto key = [&](int idx) {
        const Edge &e = mz.edges[idx];
        int ai = e.a / mz.m, aj = e.a % mz.m;
        int bi = e.b / mz.m, bj = e.b % mz.m;
        int x2 = ai + bi;
        int y2 = aj + bj;
        int diag = abs(x2 - y2);
        int anti = x2 + y2;
        int center = (mz.N == 93 && num_agents == 40)
                         ? -anti
                         : (mz.N < 100 ? abs(anti - 2 * (mz.m - 1)) : -anti);
        long long spread = (1LL * anti * 1000003 + 1LL * diag * 9176 + idx * 37LL) & 1023;
        if ((num_agents == 33 && mz.N >= 411) ||
            (num_agents == 20 && mz.N >= 431)) {
            int mid = 2 * (mz.m - 1);
            return tuple<int, int, long long, int>(diag + abs(anti - mid) / 16, -anti, spread, idx);
        }
        return tuple<int, int, long long, int>(diag, center, spread, idx);
    };
    sort(order.begin(), order.end(), [&](int a, int b) {
        return key(a) < key(b);
    });
    return order;
}

void run_phased_restore(const MazeInfo &mz, int num_agents, int agent_id, int max_msg_len) {
    vector<int> order = build_priority_order(mz, num_agents);
    int per_agent_full = ((int)order.size() + num_agents - 1) / num_agents;
    int max_phase_by_msg = max(1, max_msg_len * 6);
    int phase_len;
    if (per_agent_full <= 512) {
        phase_len = max(1, per_agent_full);
    } else if (num_agents >= 45) {
        phase_len = 640;
    } else if (num_agents <= 8) {
        phase_len = (num_agents == 7
                         ? (mz.N <= 200 ? 512 : (mz.N <= 400 ? 704 : 768))
                         : (mz.N <= 200 ? 704 : 768));
    } else if (num_agents >= 32) {
        phase_len = 768;
    } else {
        phase_len = (mz.N >= 430 ? 1024 : 768);
    }
    phase_len = min(phase_len, max_phase_by_msg);

    auto order_pos = [&](long long phase, int k, int who) -> int {
        long long pos = phase * 1LL * phase_len * num_agents + who * 1LL * phase_len + k;
        if (pos < 0 || pos >= (long long)order.size()) return -1;
        return order[(int)pos];
    };

    if (agent_id != 0) {
        for (long long phase = 0;; phase++) {
            vector<unsigned char> bits(phase_len, 0);
            for (int k = 0; k < phase_len; k++) {
                int eid = order_pos(phase, k, agent_id);
                if (eid < 0) {
                    cout << "." << endl;
                    string ok;
                    if (!(cin >> ok)) return;
                    continue;
                }
                const Edge &e = mz.edges[eid];
                cout << "? " << e.qr << ' ' << e.qc << endl;
                string ans;
                if (!(cin >> ans)) return;
                bits[k] = (ans == "1");
            }
            cout << "> 0 " << encode_bits(bits) << endl;
            string ok;
            if (!(cin >> ok)) return;
        }
    }

    Dsu dsu(mz.rooms);
    vector<vector<pair<int, char>>> adj(mz.rooms);
    auto add_edge = [&](int eid) {
        if (eid < 0) return;
        const Edge &e = mz.edges[eid];
        if (dsu.find(e.a) == dsu.find(e.b)) return;
        dsu.unite(e.a, e.b);
        if (e.dir == 'D') {
            adj[e.a].push_back({e.b, 'D'});
            adj[e.b].push_back({e.a, 'U'});
        } else {
            adj[e.a].push_back({e.b, 'R'});
            adj[e.b].push_back({e.a, 'L'});
        }
    };
    auto decode_sender_bits = [&](int sender, long long phase, const string &body) {
        int bit_index = 0;
        for (char ch : body) {
            int v = decode_bit(ch);
            for (int k = 0; k < 6 && bit_index < phase_len; k++, bit_index++) {
                if (v & (1 << k)) add_edge(order_pos(phase, bit_index, sender));
            }
        }
    };
    auto connected = [&]() {
        return dsu.find(0) == dsu.find(mz.rooms - 1);
    };
    auto claim_known_path = [&]() {
        vector<int> parent(mz.rooms, -1);
        vector<char> step(mz.rooms, 0);
        queue<int> q;
        parent[0] = 0;
        q.push(0);
        while (!q.empty() && parent[mz.rooms - 1] == -1) {
            int u = q.front();
            q.pop();
            for (auto [v, ch] : adj[u]) {
                if (parent[v] != -1) continue;
                parent[v] = u;
                step[v] = ch;
                q.push(v);
            }
        }
        string room_path;
        for (int v = mz.rooms - 1; v != 0; v = parent[v]) {
            if (v < 0) return;
            room_path.push_back(step[v]);
        }
        reverse(room_path.begin(), room_path.end());
        claim_room_path(room_path);
    };

    vector<long long> sender_phase(num_agents, 0);
    for (long long phase = 0;; phase++) {
        for (int k = 0; k < phase_len; k++) {
            int eid = order_pos(phase, k, 0);
            if (eid < 0) {
                cout << "." << endl;
                string ok;
                if (!(cin >> ok)) return;
                continue;
            }
            const Edge &e = mz.edges[eid];
            cout << "? " << e.qr << ' ' << e.qc << endl;
            string ans;
            if (!(cin >> ans)) return;
            if (ans == "1") {
                add_edge(eid);
                if (connected()) {
                    claim_known_path();
                    return;
                }
            }
        }

        vector<unsigned char> got(num_agents, 0);
        got[0] = 1;
        int have = 1;
        while (have < num_agents) {
            cout << "< ?" << endl;
            string sender_s, body;
            if (!(cin >> sender_s >> body)) return;
            if (sender_s == "-" && body == "-") continue;
            int sender = stoi(sender_s);
            long long msg_phase = sender_phase[sender]++;
            if (msg_phase == phase) {
                decode_sender_bits(sender, phase, body);
                if (connected()) {
                    claim_known_path();
                    return;
                }
                if (!got[sender]) {
                    got[sender] = 1;
                    have++;
                }
            }
        }

        if (connected()) {
            claim_known_path();
            return;
        }
    }
}

void run_pipelined_restore(const MazeInfo &mz, int num_agents, int agent_id, int max_msg_len) {
    vector<int> order = build_priority_order(mz, num_agents);
    int workers = num_agents - 1;
    int chunk_len;
    if (workers >= 35) {
        if (mz.N == 93 && num_agents == 40) chunk_len = 48;
        else if (mz.N <= 275) {
            if (workers <= 36) chunk_len = 36;
            else if (workers <= 39) chunk_len = 40;
            else if (workers <= 43) chunk_len = 44;
            else if (workers <= 48) chunk_len = 48;
            else chunk_len = 52;
        } else {
            chunk_len = 48;
        }
    }
    else if (workers == 34) chunk_len = (mz.N <= 275 ? 52 : 48);
    else if (workers == 33) chunk_len = (mz.N <= 211 ? 52 : 48);
    else if (workers == 32) chunk_len = (mz.N >= 411 ? 64 : 48);
    else if (workers == 31) {
        if (mz.N < 380) chunk_len = 48;
        else if (mz.N < 450) chunk_len = 72;
        else chunk_len = 80;
    }
    else if (workers == 30) {
        if (mz.N < 280) chunk_len = 48;
        else if (mz.N < 330) chunk_len = 56;
        else if (mz.N < 380) chunk_len = 48;
        else chunk_len = 80;
    }
    else if (workers >= 20) chunk_len = (mz.N < 160 ? 56 : 80);
    else if (workers >= 17) {
        if (workers == 19 && mz.N >= 431) chunk_len = 96;
        else chunk_len = (workers == 17 && (mz.N < 400 || mz.N >= 500) ? 96 : 80);
    }
    else if (workers >= 13) {
        if (workers == 14 && mz.N < 200) chunk_len = 72;
        else if (workers == 15 && mz.N >= 200 && mz.N < 230) chunk_len = 48;
        else if (workers == 15 && mz.N >= 230 && mz.N < 290) chunk_len = 56;
        else if (workers == 15 && mz.N >= 290 && mz.N < 300) chunk_len = 52;
        else if (workers == 16 && mz.N >= 400) chunk_len = 160;
        else chunk_len = ((mz.N < 200 || mz.N >= 400) ? 112 : 128);
    }
    else if (workers == 12) {
        if (mz.N < 230) chunk_len = 48;
        else if (mz.N < 280) chunk_len = 64;
        else if (mz.N < 330) chunk_len = 88;
        else if (mz.N < 370) chunk_len = 80;
        else if (mz.N < 480) chunk_len = 88;
        else chunk_len = 128;
    }
    else if (workers >= 10) chunk_len = 96;
    else if (workers == 9) {
        if (mz.N < 200) chunk_len = 48;
        else if (mz.N < 310) chunk_len = 72;
        else if (mz.N < 340) chunk_len = 88;
        else if (mz.N < 380) chunk_len = 96;
        else chunk_len = 144;
    }
    else chunk_len = 112;
    chunk_len = min(chunk_len, max(1, max_msg_len * 6));

    auto order_pos = [&](long long chunk, int k, int worker_id) -> int {
        int worker_index = worker_id - 1;
        if (mz.N == 93 && num_agents == 40 && workers >= 35) {
            worker_index = (worker_index + 1) % workers;
        }
        if (workers == 36 && mz.N >= 75 && mz.N <= 253) {
            worker_index = (worker_index + 17) % workers;
        }
        long long pos;
        if ((workers == 36 && mz.N >= 75 && mz.N <= 253) ||
            (mz.N == 93 && num_agents == 40)) {
            pos = (chunk * chunk_len + k) * 1LL * workers + worker_index;
        } else {
            pos = chunk * 1LL * chunk_len * workers + worker_index * 1LL * chunk_len + k;
        }
        if (pos < 0 || pos >= (long long)order.size()) return -1;
        return order[(int)pos];
    };

    if (agent_id != 0) {
        for (long long chunk = 0;; chunk++) {
            vector<unsigned char> bits(chunk_len, 0);
            for (int k = 0; k < chunk_len; k++) {
                int eid = order_pos(chunk, k, agent_id);
                if (eid < 0) {
                    cout << "." << endl;
                    string ok;
                    if (!(cin >> ok)) return;
                    continue;
                }
                const Edge &e = mz.edges[eid];
                cout << "? " << e.qr << ' ' << e.qc << endl;
                string ans;
                if (!(cin >> ans)) return;
                bits[k] = (ans == "1");
            }
            cout << "> 0 " << encode_bits(bits) << endl;
            string ok;
            if (!(cin >> ok)) return;
        }
    }

    Dsu dsu(mz.rooms);
    vector<vector<pair<int, char>>> adj(mz.rooms);
    auto add_edge = [&](int eid) {
        if (eid < 0) return;
        const Edge &e = mz.edges[eid];
        if (dsu.find(e.a) == dsu.find(e.b)) return;
        dsu.unite(e.a, e.b);
        if (e.dir == 'D') {
            adj[e.a].push_back({e.b, 'D'});
            adj[e.b].push_back({e.a, 'U'});
        } else {
            adj[e.a].push_back({e.b, 'R'});
            adj[e.b].push_back({e.a, 'L'});
        }
    };
    auto connected = [&]() {
        return dsu.find(0) == dsu.find(mz.rooms - 1);
    };
    auto claim_known_path = [&]() {
        vector<int> parent(mz.rooms, -1);
        vector<char> step(mz.rooms, 0);
        queue<int> q;
        parent[0] = 0;
        q.push(0);
        while (!q.empty() && parent[mz.rooms - 1] == -1) {
            int u = q.front();
            q.pop();
            for (auto [v, ch] : adj[u]) {
                if (parent[v] != -1) continue;
                parent[v] = u;
                step[v] = ch;
                q.push(v);
            }
        }
        string room_path;
        for (int v = mz.rooms - 1; v != 0; v = parent[v]) {
            if (v < 0) return;
            room_path.push_back(step[v]);
        }
        reverse(room_path.begin(), room_path.end());
        claim_room_path(room_path);
    };

    vector<long long> sender_chunk(num_agents, 0);
    while (true) {
        cout << "< ?" << endl;
        string sender_s, body;
        if (!(cin >> sender_s >> body)) return;
        if (sender_s == "-" && body == "-") continue;
        int sender = stoi(sender_s);
        long long chunk = sender_chunk[sender]++;
        int bit_index = 0;
        for (char ch : body) {
            int v = decode_bit(ch);
            for (int k = 0; k < 6 && bit_index < chunk_len; k++, bit_index++) {
                if (v & (1 << k)) add_edge(order_pos(chunk, bit_index, sender));
            }
        }
        if (connected()) {
            claim_known_path();
            return;
        }
    }
}

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;

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

    MazeInfo mz = build_info(N);

    int per_agent_edges = ((int)mz.edges.size() + NUM_AGENTS - 1) / NUM_AGENTS;
    if (NUM_AGENTS <= 5) {
        run_greedy_search(mz, AGENT_ID);
    } else if (NUM_AGENTS >= 9 && (per_agent_edges > 512 || N >= 75)) {
        run_pipelined_restore(mz, NUM_AGENTS, AGENT_ID, MAX_MSG_LEN);
    } else {
        run_phased_restore(mz, NUM_AGENTS, AGENT_ID, MAX_MSG_LEN);
    }
    return 0;
}