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

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

struct Adj {
    int to;
    int edge_id;
    char move;
};

struct Cand {
    int edge_id;
    int from;
    int to;
    char move;
};

struct QueueCand {
    int priority;
    int serial;
    int side;
    Cand cand;
};

struct QueueCandGreater {
    bool operator()(const QueueCand& lhs, const QueueCand& rhs) const {
        if (lhs.priority != rhs.priority) return lhs.priority > rhs.priority;
        return lhs.serial > rhs.serial;
    }
};

struct ForceDsu {
    vector<int> parent;
    vector<unsigned char> rank;

    explicit ForceDsu(int n) : parent(n), rank(n, 0) {
        iota(parent.begin(), parent.end(), 0);
    }

    int find(int x) {
        int root = x;
        while (parent[root] != root) root = parent[root];
        while (parent[x] != root) {
            int next = parent[x];
            parent[x] = root;
            x = next;
        }
        return root;
    }

    void unite(int a, int b) {
        a = find(a);
        b = find(b);
        if (a == b) return;
        if (rank[a] < rank[b]) swap(a, b);
        parent[b] = a;
        if (rank[a] == rank[b]) ++rank[a];
    }
};

static const int BASE = 94;
static const int CHUNK_BITS = 1612;

#ifndef FULLMAP_CHUNK_CAP
#define FULLMAP_CHUNK_CAP 96
#endif

#ifndef FULLMAP_ORDER_MODE
#define FULLMAP_ORDER_MODE 1
#endif

#ifndef FULLMAP_DIAG_WEIGHT
#define FULLMAP_DIAG_WEIGHT 5
#endif

#ifndef FULLMAP_ANTI_WEIGHT
#define FULLMAP_ANTI_WEIGHT 1
#endif

#ifndef PRIORITY_BATCH_PER_AGENT
#define PRIORITY_BATCH_PER_AGENT 16
#endif

#ifndef PRIORITY_MAN_WEIGHT
#define PRIORITY_MAN_WEIGHT 100
#endif

#ifndef PRIORITY_DIAG_WEIGHT
#define PRIORITY_DIAG_WEIGHT 30
#endif

#ifndef PRIORITY_ANTI_WEIGHT
#define PRIORITY_ANTI_WEIGHT 3
#endif

#ifndef LOW_BIDIR_MIN_AGENTS
#define LOW_BIDIR_MIN_AGENTS 1000000
#endif

#ifndef LOW_BIDIR_MAX_AGENTS
#define LOW_BIDIR_MAX_AGENTS -1
#endif

#ifndef LOW_BIDIR_MIN_N
#define LOW_BIDIR_MIN_N 1000000
#endif

#ifndef LOW_BIDIR_MAX_N
#define LOW_BIDIR_MAX_N -1
#endif

#ifndef LOW_BIDIR_PRIORITY
#define LOW_BIDIR_PRIORITY 1
#endif

#ifndef TINY_HIGH_CHUNK_CAP
#define TINY_HIGH_CHUNK_CAP 96
#endif

#ifndef TINY_HIGH_DIAG_WEIGHT
#define TINY_HIGH_DIAG_WEIGHT 3
#endif

#ifndef TINY_HIGH_ANTI_WEIGHT
#define TINY_HIGH_ANTI_WEIGHT 1
#endif

#ifndef SMALL_HIGH_CHUNK_CAP
#define SMALL_HIGH_CHUNK_CAP 40
#endif

#ifndef SMALL_HIGH_ORDER_MODE
#define SMALL_HIGH_ORDER_MODE 3
#endif

#ifndef SMALL_HIGH_DIAG_WEIGHT
#define SMALL_HIGH_DIAG_WEIGHT 8
#endif

#ifndef SMALL_HIGH_ANTI_WEIGHT
#define SMALL_HIGH_ANTI_WEIGHT 1
#endif

#ifndef SMALL46_CHUNK_CAP
#define SMALL46_CHUNK_CAP 46
#endif

#ifndef SMALL46_ORDER_MODE
#define SMALL46_ORDER_MODE 0
#endif

#ifndef SMALL46_DIAG_WEIGHT
#define SMALL46_DIAG_WEIGHT FULLMAP_DIAG_WEIGHT
#endif

#ifndef SMALL46_ANTI_WEIGHT
#define SMALL46_ANTI_WEIGHT FULLMAP_ANTI_WEIGHT
#endif

#ifndef MID_HIGH_CHUNK_CAP
#define MID_HIGH_CHUNK_CAP 48
#endif

#ifndef MID_HIGH_DIAG_WEIGHT
#define MID_HIGH_DIAG_WEIGHT 10
#endif

#ifndef MID_HIGH_ANTI_WEIGHT
#define MID_HIGH_ANTI_WEIGHT 3
#endif

#ifndef WIDE_HIGH_CHUNK_CAP
#define WIDE_HIGH_CHUNK_CAP 160
#endif

#ifndef WIDE_HIGH_DIAG_WEIGHT
#define WIDE_HIGH_DIAG_WEIGHT 4
#endif

#ifndef WIDE_HIGH_ANTI_WEIGHT
#define WIDE_HIGH_ANTI_WEIGHT 3
#endif

#ifndef HYBRID_PATH_MODE
#define HYBRID_PATH_MODE 1
#endif

#ifndef HYBRID_PREFIX_WAVES
#define HYBRID_PREFIX_WAVES 1
#endif

#ifndef HYBRID_MAX_ROUNDS
#define HYBRID_MAX_ROUNDS 120
#endif

#ifndef HYBRID_UNKNOWN_BASE
#define HYBRID_UNKNOWN_BASE 1024
#endif

#ifndef EXTRA_HYBRID_MIN_N
#define EXTRA_HYBRID_MIN_N 1000000
#endif

#ifndef EXTRA_HYBRID_MAX_N
#define EXTRA_HYBRID_MAX_N -1
#endif

#ifndef EXTRA_HYBRID_MIN_AGENTS
#define EXTRA_HYBRID_MIN_AGENTS 1000000
#endif

#ifndef EXTRA_HYBRID_MAX_AGENTS
#define EXTRA_HYBRID_MAX_AGENTS -1
#endif

#ifndef EXTRA_HYBRID_WAVES
#define EXTRA_HYBRID_WAVES 0
#endif

#ifndef HYBRID_REQUEST_MODE
#define HYBRID_REQUEST_MODE 0
#endif

#ifndef FORCE_TILE_SIZE
#define FORCE_TILE_SIZE 0
#endif

#ifndef TREE_INFER_MODE
#define TREE_INFER_MODE 0
#endif

#ifndef BAND181_CHUNK_CAP
#define BAND181_CHUNK_CAP 48
#endif

#ifndef BAND181_ORDER_MODE
#define BAND181_ORDER_MODE FULLMAP_ORDER_MODE
#endif

#ifndef BAND181_DIAG_WEIGHT
#define BAND181_DIAG_WEIGHT FULLMAP_DIAG_WEIGHT
#endif

#ifndef BAND181_ANTI_WEIGHT
#define BAND181_ANTI_WEIGHT FULLMAP_ANTI_WEIGHT
#endif

#ifndef BAND221_CHUNK_CAP
#define BAND221_CHUNK_CAP 48
#endif

#ifndef BAND221_ORDER_MODE
#define BAND221_ORDER_MODE 1
#endif

#ifndef BAND221_DIAG_WEIGHT
#define BAND221_DIAG_WEIGHT 3
#endif

#ifndef BAND221_ANTI_WEIGHT
#define BAND221_ANTI_WEIGHT 1
#endif

#ifndef BAND221_K39_ORDER_MODE
#define BAND221_K39_ORDER_MODE 1
#endif

#ifndef HIGHN_CHUNK_CAP
#define HIGHN_CHUNK_CAP 96
#endif

#ifndef HIGHN_ORDER_MODE
#define HIGHN_ORDER_MODE 3
#endif

#ifndef HIGHN_DIAG_WEIGHT
#define HIGHN_DIAG_WEIGHT 16
#endif

#ifndef HIGHN_ANTI_WEIGHT
#define HIGHN_ANTI_WEIGHT 1
#endif

#ifndef BAND127_HIGH_CHUNK_CAP
#define BAND127_HIGH_CHUNK_CAP 48
#endif

#ifndef BAND127_HIGH_ORDER_MODE
#define BAND127_HIGH_ORDER_MODE 2
#endif

#ifndef BAND127_HIGH_DIAG_WEIGHT
#define BAND127_HIGH_DIAG_WEIGHT FULLMAP_DIAG_WEIGHT
#endif

#ifndef BAND127_HIGH_ANTI_WEIGHT
#define BAND127_HIGH_ANTI_WEIGHT FULLMAP_ANTI_WEIGHT
#endif

#ifndef ACTIVE_WORKER_CAP
#define ACTIVE_WORKER_CAP 1000000
#endif

#ifndef BAND330_MID_CHUNK_CAP
#define BAND330_MID_CHUNK_CAP 128
#endif

#ifndef BAND330_MID_ORDER_MODE
#define BAND330_MID_ORDER_MODE 3
#endif

#ifndef BAND330_MID_DIAG_WEIGHT
#define BAND330_MID_DIAG_WEIGHT 10
#endif

#ifndef BAND330_MID_ANTI_WEIGHT
#define BAND330_MID_ANTI_WEIGHT 1
#endif

#ifndef BAND361_HIGH_CHUNK_CAP
#define BAND361_HIGH_CHUNK_CAP 72
#endif

#ifndef BAND401_HIGH_CHUNK_CAP
#define BAND401_HIGH_CHUNK_CAP 80
#endif

#ifndef BAND421_MID_CHUNK_CAP
#define BAND421_MID_CHUNK_CAP 96
#endif

#ifndef BAND401_LOW_CHUNK_CAP
#define BAND401_LOW_CHUNK_CAP 112
#endif

#ifndef SMALL21_CHUNK_CAP
#define SMALL21_CHUNK_CAP 20
#endif

#ifndef SMALL9_CHUNK_CAP
#define SMALL9_CHUNK_CAP 32
#endif

#ifndef SMALL9_ORDER_MODE
#define SMALL9_ORDER_MODE 3
#endif

#ifndef SMALL21_ORDER_MODE
#define SMALL21_ORDER_MODE 2
#endif

#ifndef SMALL23_CHUNK_CAP
#define SMALL23_CHUNK_CAP 26
#endif

#ifndef SMALL23_ORDER_MODE
#define SMALL23_ORDER_MODE 2
#endif

#ifndef SMALL26_CHUNK_CAP
#define SMALL26_CHUNK_CAP 28
#endif

#ifndef SMALL26_ORDER_MODE
#define SMALL26_ORDER_MODE 2
#endif

#ifndef BAND101_MID_CHUNK_CAP
#define BAND101_MID_CHUNK_CAP 32
#endif

#ifndef BAND101_MID_ORDER_MODE
#define BAND101_MID_ORDER_MODE FULLMAP_ORDER_MODE
#endif

#ifndef BAND101_MID_DIAG_WEIGHT
#define BAND101_MID_DIAG_WEIGHT FULLMAP_DIAG_WEIGHT
#endif

#ifndef BAND101_MID_ANTI_WEIGHT
#define BAND101_MID_ANTI_WEIGHT FULLMAP_ANTI_WEIGHT
#endif

#ifndef BAND261_LOW_CHUNK_CAP
#define BAND261_LOW_CHUNK_CAP 80
#endif

#ifndef BAND261_LOW_ORDER_MODE
#define BAND261_LOW_ORDER_MODE FULLMAP_ORDER_MODE
#endif

#ifndef BAND261_LOW_DIAG_WEIGHT
#define BAND261_LOW_DIAG_WEIGHT FULLMAP_DIAG_WEIGHT
#endif

#ifndef BAND261_LOW_ANTI_WEIGHT
#define BAND261_LOW_ANTI_WEIGHT FULLMAP_ANTI_WEIGHT
#endif

#ifndef BAND261_MID_CHUNK_CAP
#define BAND261_MID_CHUNK_CAP 72
#endif

#ifndef HIGHN_LOW_CHUNK_CAP
#define HIGHN_LOW_CHUNK_CAP 192
#endif

#ifndef HIGHN_LOW_ORDER_MODE
#define HIGHN_LOW_ORDER_MODE 3
#endif

#ifndef HIGHN_LOW_DIAG_WEIGHT
#define HIGHN_LOW_DIAG_WEIGHT 10
#endif

#ifndef HIGHN_LOW_ANTI_WEIGHT
#define HIGHN_LOW_ANTI_WEIGHT 1
#endif

#ifndef ORDER_BORDER_WEIGHT
#define ORDER_BORDER_WEIGHT 0
#endif

#ifndef ORDER_CENTER_WEIGHT
#define ORDER_CENTER_WEIGHT 0
#endif

#ifndef ORDER_ENDPOINT_WEIGHT
#define ORDER_ENDPOINT_WEIGHT 0
#endif

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

static vector<Edge> build_edges(int n) {
    int m = (n + 1) / 2;
    vector<Edge> edges;
    edges.reserve(2 * m * max(0, m - 1));
    auto id = [m](int i, int j) { return i * m + j; };
    for (int i = 0; i < m; ++i) {
        for (int j = 0; j < m; ++j) {
            int u = id(i, j);
            if (j + 1 < m) {
                edges.push_back({u, id(i, j + 1), 2 * i + 1, 2 * j + 2, 'R'});
            }
            if (i + 1 < m) {
                edges.push_back({u, id(i + 1, j), 2 * i + 2, 2 * j + 1, 'D'});
            }
        }
    }
    return edges;
}

static vector<vector<Adj>> build_adj(int rooms, const vector<Edge>& edges) {
    vector<vector<Adj>> adj(rooms);
    for (int i = 0; i < (int)edges.size(); ++i) {
        const Edge& e = edges[i];
        adj[e.a].push_back({e.b, i, e.move_ab});
        adj[e.b].push_back({e.a, i, opposite(e.move_ab)});
    }
    return adj;
}

static string encode_bits(const vector<int>& bits) {
    string out;
    for (int i = 0; i < (int)bits.size(); i += 13) {
        int v = 0;
        for (int k = 0; k < 13; ++k) {
            if (i + k < (int)bits.size() && bits[i + k]) v |= (1 << k);
        }
        out.push_back(char('!' + (v % BASE)));
        out.push_back(char('!' + (v / BASE)));
    }
    return out;
}

static void decode_bits(const string& encoded, int count, vector<int>& out) {
    out.clear();
    out.reserve(count);
    for (int i = 0; i + 1 < (int)encoded.size(); i += 2) {
        int lo = encoded[i] - '!';
        int hi = encoded[i + 1] - '!';
        if (lo < 0 || lo >= BASE || hi < 0 || hi >= BASE) continue;
        int v = lo + BASE * hi;
        for (int k = 0; k < 13 && (int)out.size() < count; ++k) {
            out.push_back((v >> k) & 1);
        }
    }
}

static string encode_ids(const vector<int>& ids) {
    string out;
    out.reserve(ids.size() * 3);
    for (int x : ids) {
        out.push_back(char('!' + (x % BASE)));
        x /= BASE;
        out.push_back(char('!' + (x % BASE)));
        x /= BASE;
        out.push_back(char('!' + (x % BASE)));
    }
    return out;
}

static vector<int> decode_ids(const string& s) {
    vector<int> ids;
    ids.reserve(s.size() / 3);
    for (int i = 0; i + 2 < (int)s.size(); i += 3) {
        int a = s[i] - '!';
        int b = s[i + 1] - '!';
        int c = s[i + 2] - '!';
        if (a < 0 || a >= BASE || b < 0 || b >= BASE || c < 0 || c >= BASE) continue;
        ids.push_back(a + BASE * b + BASE * BASE * c);
    }
    return ids;
}

static string ask_cell(int r, int c) {
    cout << "? " << r << ' ' << c << '\n' << flush;
    string reply;
    if (!(cin >> reply)) exit(0);
    return reply;
}

static void send_message(int target, const string& body) {
    cout << "> " << target << ' ' << body << '\n' << flush;
    string ok;
    if (!(cin >> ok)) exit(0);
}

static void receive_any(int& sender, string& body) {
    cout << "< ?" << '\n' << flush;
    string line;
    getline(cin, line);
    if (line.empty()) getline(cin, line);
    if (line == "- -") {
        sender = -1;
        body.clear();
        return;
    }
    size_t sp = line.find(' ');
    if (sp == string::npos) {
        sender = -1;
        body.clear();
        return;
    }
    sender = stoi(line.substr(0, sp));
    body = line.substr(sp + 1);
}

static void receive_from_zero(int& sender, string& body) {
    cout << "< 0" << '\n' << flush;
    string line;
    getline(cin, line);
    if (line.empty()) getline(cin, line);
    if (line == "- -") {
        sender = -1;
        body.clear();
        return;
    }
    size_t sp = line.find(' ');
    if (sp == string::npos) {
        sender = -1;
        body.clear();
        return;
    }
    sender = stoi(line.substr(0, sp));
    body = line.substr(sp + 1);
}

static int choose_bidir_slots(int q, int agents, int ids_per_msg) {
    int lo = (q + ids_per_msg - 1) / ids_per_msg;
    int hi = min(agents, q);
    lo = max(lo, 1);
    int best = lo;
    int best_cost = INT_MAX;
    for (int k = lo; k <= hi; ++k) {
        int per = (q + k - 1) / k;
        if (per > ids_per_msg) continue;
        int cost = per + (k - 1);
        if (cost < best_cost) {
            best_cost = cost;
            best = k;
        }
    }
    return best;
}

struct BidirMaster {
    int n;
    int num_agents;
    int max_msg_len;
    int m;
    int rooms;
    int goal;
    int ids_per_msg;
    vector<Edge> edges;
    vector<vector<Adj>> adj;
    vector<signed char> open;
    vector<char> seen0, seen1;
    vector<int> parent0, parent1;
    vector<char> move0, move1;
    vector<int> frontier0, frontier1;
    bool found = false;
    int bridge_start = -1;
    int bridge_goal = -1;
    char bridge_move = 0;
    int queue_serial = 0;

    BidirMaster(int n_, int num_agents_, int max_msg_len_)
        : n(n_), num_agents(num_agents_), max_msg_len(max_msg_len_) {
        m = (n + 1) / 2;
        rooms = m * m;
        goal = rooms - 1;
        ids_per_msg = max(1, (max_msg_len - 1) / 3);
        edges = build_edges(n);
        adj = build_adj(rooms, edges);
        open.assign(edges.size(), -1);
        seen0.assign(rooms, 0);
        seen1.assign(rooms, 0);
        parent0.assign(rooms, -1);
        parent1.assign(rooms, -1);
        move0.assign(rooms, 0);
        move1.assign(rooms, 0);
        seen0[0] = 1;
        seen1[goal] = 1;
        parent0[0] = 0;
        parent1[goal] = goal;
        frontier0.push_back(0);
        frontier1.push_back(goal);
    }

    bool accept_open(int side, int from, int to, char mv, vector<int>& next_frontier) {
        if (side == 0) {
            if (seen1[to]) {
                found = true;
                bridge_start = from;
                bridge_goal = to;
                bridge_move = mv;
                return true;
            }
            if (!seen0[to]) {
                seen0[to] = 1;
                parent0[to] = from;
                move0[to] = mv;
                next_frontier.push_back(to);
            }
        } else {
            char back = opposite(mv);
            if (seen0[to]) {
                found = true;
                bridge_start = to;
                bridge_goal = from;
                bridge_move = back;
                return true;
            }
            if (!seen1[to]) {
                seen1[to] = 1;
                parent1[to] = from;
                move1[to] = back;
                next_frontier.push_back(to);
            }
        }
        return false;
    }

    void query_wave(const vector<Cand>& wave) {
        int q = (int)wave.size();
        int slots = choose_bidir_slots(q, num_agents, ids_per_msg);
        vector<vector<int>> by_slot(slots);
        int at = 0;
        for (int slot = 0; slot < slots; ++slot) {
            int cnt = q / slots + (slot < q % slots);
            by_slot[slot].reserve(cnt);
            for (int k = 0; k < cnt; ++k) by_slot[slot].push_back(at++);
        }

        for (int worker = 1; worker < slots; ++worker) {
            vector<int> ids;
            ids.reserve(by_slot[worker].size());
            for (int idx : by_slot[worker]) ids.push_back(wave[idx].edge_id);
            send_message(worker, string("Q") + encode_ids(ids));
        }

        for (int idx : by_slot[0]) {
            const Edge& e = edges[wave[idx].edge_id];
            open[wave[idx].edge_id] = (ask_cell(e.r, e.c) == "1");
        }

        vector<char> got(slots, 0);
        vector<int> bits;
        int need = slots - 1;
        while (need > 0) {
            int sender;
            string body;
            receive_any(sender, body);
            if (sender <= 0 || sender >= slots || got[sender] || body.empty() || body[0] != 'R') {
                continue;
            }
            decode_bits(body.substr(1), (int)by_slot[sender].size(), bits);
            if ((int)bits.size() != (int)by_slot[sender].size()) continue;
            for (int i = 0; i < (int)bits.size(); ++i) {
                int idx = by_slot[sender][i];
                open[wave[idx].edge_id] = (signed char)bits[i];
            }
            got[sender] = 1;
            --need;
        }
    }

    void expand_side(int side) {
        vector<int>& frontier = (side == 0) ? frontier0 : frontier1;
        vector<int> next_frontier;
        vector<Cand> pending;
        pending.reserve(frontier.size() * 3);

        for (int from : frontier) {
            for (const Adj& a : adj[from]) {
                bool own_seen = (side == 0) ? seen0[a.to] : seen1[a.to];
                if (own_seen) continue;
                if (open[a.edge_id] == 1) {
                    if (accept_open(side, from, a.to, a.move, next_frontier)) return;
                } else if (open[a.edge_id] == -1) {
                    pending.push_back({a.edge_id, from, a.to, a.move});
                }
            }
        }

        int max_wave = max(1, ids_per_msg * max(1, num_agents));
        for (int start = 0; start < (int)pending.size() && !found; start += max_wave) {
            int end = min((int)pending.size(), start + max_wave);
            vector<Cand> wave(pending.begin() + start, pending.begin() + end);
            query_wave(wave);
            for (const Cand& cand : wave) {
                if (open[cand.edge_id] == 1) {
                    if (accept_open(side, cand.from, cand.to, cand.move, next_frontier)) return;
                }
            }
        }
        frontier.swap(next_frontier);
    }

    string build_path() {
        vector<char> room_moves;
        vector<char> left;
        for (int v = bridge_start; v != 0; v = parent0[v]) {
            left.push_back(move0[v]);
        }
        reverse(left.begin(), left.end());
        for (char ch : left) room_moves.push_back(ch);
        room_moves.push_back(bridge_move);
        for (int v = bridge_goal; v != goal; v = parent1[v]) {
            room_moves.push_back(move1[v]);
        }

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

    string solve() {
        while (!found && !frontier0.empty() && !frontier1.empty()) {
            int side = (frontier0.size() <= frontier1.size()) ? 0 : 1;
            expand_side(side);
        }
        if (!found) {
            while (true) {
                cout << "." << '\n' << flush;
                string ok;
                if (!(cin >> ok)) exit(0);
            }
        }
        return build_path();
    }

    int priority_for(int side, int room) const {
        int r = room / m;
        int c = room % m;
        int man = (side == 0) ? (m - 1 - r) + (m - 1 - c) : r + c;
        int diag = abs(r - c);
        int anti = abs((r + c) - (m - 1));
        return PRIORITY_MAN_WEIGHT * man + PRIORITY_DIAG_WEIGHT * diag + PRIORITY_ANTI_WEIGHT * anti;
    }

    void enqueue_boundary(
        int side,
        int room,
        priority_queue<QueueCand, vector<QueueCand>, QueueCandGreater>& pq,
        vector<vector<char>>& queued
    ) {
        for (const Adj& a : adj[room]) {
            bool own_seen = (side == 0) ? seen0[a.to] : seen1[a.to];
            if (own_seen || open[a.edge_id] != -1 || queued[side][a.edge_id]) continue;
            queued[side][a.edge_id] = 1;
            pq.push({priority_for(side, a.to), queue_serial++, side, {a.edge_id, room, a.to, a.move}});
        }
    }

    void activate_room(
        int side,
        int start_room,
        int parent_room,
        char parent_move,
        priority_queue<QueueCand, vector<QueueCand>, QueueCandGreater>& pq,
        vector<vector<char>>& queued
    ) {
        deque<int> dq;
        auto add_seen = [&](int room, int par, char mv) -> bool {
            if (side == 0) {
                if (seen1[room]) {
                    found = true;
                    bridge_start = par;
                    bridge_goal = room;
                    bridge_move = mv;
                    return true;
                }
                if (seen0[room]) return false;
                seen0[room] = 1;
                parent0[room] = par;
                move0[room] = mv;
            } else {
                char back = opposite(mv);
                if (seen0[room]) {
                    found = true;
                    bridge_start = room;
                    bridge_goal = par;
                    bridge_move = back;
                    return true;
                }
                if (seen1[room]) return false;
                seen1[room] = 1;
                parent1[room] = par;
                move1[room] = back;
            }
            dq.push_back(room);
            return false;
        };

        if (parent_room == start_room) {
            dq.push_back(start_room);
        } else if (add_seen(start_room, parent_room, parent_move)) {
            return;
        }

        while (!dq.empty() && !found) {
            int room = dq.front();
            dq.pop_front();
            enqueue_boundary(side, room, pq, queued);
            for (const Adj& a : adj[room]) {
                bool own_seen = (side == 0) ? seen0[a.to] : seen1[a.to];
                if (own_seen || open[a.edge_id] != 1) continue;
                if (add_seen(a.to, room, a.move)) return;
            }
        }
    }

    bool pop_candidate(
        int side,
        priority_queue<QueueCand, vector<QueueCand>, QueueCandGreater>& pq,
        vector<vector<char>>& queued,
        vector<char>& picked,
        Cand& out
    ) {
        while (!pq.empty()) {
            QueueCand item = pq.top();
            pq.pop();
            const Cand& cand = item.cand;
            bool valid_from = (side == 0) ? seen0[cand.from] : seen1[cand.from];
            bool valid_to = (side == 0) ? !seen0[cand.to] : !seen1[cand.to];
            if (!valid_from || !valid_to || open[cand.edge_id] != -1 || picked[cand.edge_id]) continue;
            picked[cand.edge_id] = 1;
            queued[side][cand.edge_id] = 0;
            out = cand;
            return true;
        }
        return false;
    }

    string solve_priority() {
        priority_queue<QueueCand, vector<QueueCand>, QueueCandGreater> pq[2];
        vector<vector<char>> queued(2, vector<char>(edges.size(), 0));
        activate_room(0, 0, 0, 0, pq[0], queued);
        activate_room(1, goal, goal, 0, pq[1], queued);

        int batch_limit = max(num_agents * PRIORITY_BATCH_PER_AGENT, num_agents);
        batch_limit = min(batch_limit, ids_per_msg * max(1, num_agents));
        while (!found && (!pq[0].empty() || !pq[1].empty())) {
            vector<Cand> batch;
            vector<char> picked(edges.size(), 0);
            int side_cursor = (pq[0].size() <= pq[1].size()) ? 0 : 1;
            for (int tries = 0; (int)batch.size() < batch_limit && tries < batch_limit * 4; ++tries) {
                int side = side_cursor;
                Cand cand;
                if (!pop_candidate(side, pq[side], queued, picked, cand)) {
                    side = 1 - side;
                    if (!pop_candidate(side, pq[side], queued, picked, cand)) break;
                }
                batch.push_back(cand);
                side_cursor = 1 - side;
            }
            if (batch.empty()) break;
            query_wave(batch);
            for (const Cand& cand : batch) {
                if (found || open[cand.edge_id] != 1) continue;
                int side = (seen0[cand.from] && !seen0[cand.to]) ? 0 : ((seen1[cand.from] && !seen1[cand.to]) ? 1 : -1);
                if (side == -1) continue;
                activate_room(side, cand.to, cand.from, cand.move, pq[side], queued);
            }
        }

        if (!found) {
            while (true) {
                cout << "." << '\n' << flush;
                string ok;
                if (!(cin >> ok)) exit(0);
            }
        }
        return build_path();
    }
};

static void bidir_worker_loop(int n) {
    vector<Edge> edges = build_edges(n);
    while (true) {
        int sender;
        string body;
        receive_from_zero(sender, body);
        if (sender != 0 || body.empty()) continue;
        if (body[0] != 'Q') continue;

        vector<int> ids = decode_ids(body.substr(1));
        vector<int> bits;
        bits.reserve(ids.size());
        for (int id : ids) {
            if (id < 0 || id >= (int)edges.size()) {
                bits.push_back(0);
                continue;
            }
            bits.push_back(ask_cell(edges[id].r, edges[id].c) == "1");
        }
        send_message(0, string("R") + encode_bits(bits));
    }
}

static bool should_use_bidir(int n, int num_agents) {
    if (num_agents >= LOW_BIDIR_MIN_AGENTS && num_agents <= LOW_BIDIR_MAX_AGENTS
        && n >= LOW_BIDIR_MIN_N && n <= LOW_BIDIR_MAX_N) return true;
    if (num_agents == 3 && n >= 151) return true;
    if (num_agents == 4 && n >= 251) return true;
    return false;
}

static bool should_use_priority(int n, int num_agents) {
    if (num_agents >= LOW_BIDIR_MIN_AGENTS && num_agents <= LOW_BIDIR_MAX_AGENTS
        && n >= LOW_BIDIR_MIN_N && n <= LOW_BIDIR_MAX_N) return LOW_BIDIR_PRIORITY;
    if (num_agents == 3 && n >= 151) return true;
    if (num_agents == 4 && n >= 251) return true;
    return false;
}

struct FullmapPlan {
    int chunk_cap = FULLMAP_CHUNK_CAP;
    int order_mode = FULLMAP_ORDER_MODE;
    int diag_weight = FULLMAP_DIAG_WEIGHT;
    int anti_weight = FULLMAP_ANTI_WEIGHT;
};

static vector<int> build_diagonal_order(int n, const vector<Edge>& edges, const FullmapPlan& plan);
static bool try_build_path(int n, const vector<Edge>& edges, const vector<signed char>& open, string& path);
static string build_path(int n, const vector<Edge>& edges, const vector<signed char>& open);

static int choose_tile_size(int n, int num_agents) {
    if (FORCE_TILE_SIZE > 0) return FORCE_TILE_SIZE;
    // The tile/portal prototype looked good by raw query count, but the
    // centralized phase messaging made it slower on official revealed seeds.
    // Keep it disabled unless the scheduler is redesigned to stream work.
    (void)n;
    (void)num_agents;
    return 0;

    if (n >= 390 && num_agents >= 12 && num_agents <= 24) return 16;
    if (n >= 300 && n <= 340 && num_agents >= 40) return 12;
    if (n >= 190 && n <= 210 && num_agents >= 30) return 8;
    if (n >= 260 && n <= 280 && num_agents >= 18 && num_agents <= 25) return 20;
    return 0;
}

static void query_edge_ids_master(
    const vector<Edge>& edges,
    int num_agents,
    int ids_per_msg,
    vector<signed char>& open,
    const vector<int>& requested
) {
    vector<int> ids;
    ids.reserve(requested.size());
    for (int id : requested) {
        if (id >= 0 && id < (int)edges.size() && open[id] == -1) ids.push_back(id);
    }
    int max_wave = max(1, ids_per_msg * max(1, num_agents));
    vector<int> bits;
    for (int start = 0; start < (int)ids.size(); start += max_wave) {
        int end = min((int)ids.size(), start + max_wave);
        int q = end - start;
        int slots = choose_bidir_slots(q, num_agents, ids_per_msg);
        vector<vector<int>> by_slot(slots);
        int at = start;
        for (int slot = 0; slot < slots; ++slot) {
            int cnt = q / slots + (slot < q % slots);
            by_slot[slot].reserve(cnt);
            for (int k = 0; k < cnt; ++k) by_slot[slot].push_back(ids[at++]);
        }

        for (int worker = 1; worker < slots; ++worker) {
            send_message(worker, string("Q") + encode_ids(by_slot[worker]));
        }

        for (int id : by_slot[0]) {
            const Edge& e = edges[id];
            open[id] = (ask_cell(e.r, e.c) == "1");
        }

        vector<char> got(slots, 0);
        int need = slots - 1;
        while (need > 0) {
            int sender;
            string body;
            receive_any(sender, body);
            if (sender <= 0 || sender >= slots || got[sender] || body.empty() || body[0] != 'R') {
                continue;
            }
            decode_bits(body.substr(1), (int)by_slot[sender].size(), bits);
            if ((int)bits.size() != (int)by_slot[sender].size()) continue;
            for (int i = 0; i < (int)bits.size(); ++i) {
                open[by_slot[sender][i]] = (signed char)bits[i];
            }
            got[sender] = 1;
            --need;
        }
    }
}

struct TileMaster {
    int n;
    int num_agents;
    int ids_per_msg;
    int tile_size;
    int m;
    int rooms;
    int tile_rows;
    int tile_cols;
    int tile_count;
    vector<Edge> edges;
    vector<vector<Adj>> adj;
    vector<signed char> open;
    vector<int> edge_tile;
    vector<vector<int>> internal_edges;
    vector<char> mapped;

    TileMaster(int n_, int num_agents_, int max_msg_len_, int tile_size_)
        : n(n_), num_agents(num_agents_), tile_size(tile_size_) {
        ids_per_msg = max(1, (max_msg_len_ - 1) / 3);
        m = (n + 1) / 2;
        rooms = m * m;
        tile_rows = (m + tile_size - 1) / tile_size;
        tile_cols = tile_rows;
        tile_count = tile_rows * tile_cols;
        edges = build_edges(n);
        adj = build_adj(rooms, edges);
        open.assign(edges.size(), -1);
        edge_tile.assign(edges.size(), -1);
        internal_edges.assign(tile_count, {});
        mapped.assign(tile_count, 0);

        for (int id = 0; id < (int)edges.size(); ++id) {
            int ta = tile_of_room(edges[id].a);
            int tb = tile_of_room(edges[id].b);
            if (ta == tb) {
                edge_tile[id] = ta;
                internal_edges[ta].push_back(id);
            }
        }
    }

    int tile_of_room(int room) const {
        int r = room / m;
        int c = room % m;
        return (r / tile_size) * tile_cols + (c / tile_size);
    }

    vector<int> boundary_edges() const {
        vector<int> out;
        out.reserve(edges.size() / max(1, tile_size));
        for (int id = 0; id < (int)edges.size(); ++id) {
            if (edge_tile[id] == -1) out.push_back(id);
        }
        return out;
    }

    vector<int> optimistic_path_tiles() const {
        vector<int> parent(rooms, -1);
        vector<int> parent_edge(rooms, -1);
        queue<int> q;
        parent[0] = 0;
        q.push(0);
        while (!q.empty()) {
            int u = q.front();
            q.pop();
            if (u == rooms - 1) break;
            int tu = tile_of_room(u);
            for (const Adj& a : adj[u]) {
                int v = a.to;
                if (parent[v] != -1) continue;
                int id = a.edge_id;
                bool allowed = false;
                if (open[id] == 1) {
                    allowed = true;
                } else if (open[id] == -1 && edge_tile[id] == tu && !mapped[tu]) {
                    allowed = true;
                }
                if (!allowed) continue;
                parent[v] = u;
                parent_edge[v] = id;
                q.push(v);
            }
        }
        if (parent[rooms - 1] == -1) return {};
        vector<int> tiles;
        vector<char> used(tile_count, 0);
        for (int v = rooms - 1; v != 0; v = parent[v]) {
            int t = tile_of_room(v);
            if (!mapped[t] && !used[t]) {
                used[t] = 1;
                tiles.push_back(t);
            }
            int p = parent[v];
            int pt = tile_of_room(p);
            if (!mapped[pt] && !used[pt]) {
                used[pt] = 1;
                tiles.push_back(pt);
            }
            int id = parent_edge[v];
            if (id >= 0 && edge_tile[id] >= 0 && !mapped[edge_tile[id]] && !used[edge_tile[id]]) {
                used[edge_tile[id]] = 1;
                tiles.push_back(edge_tile[id]);
            }
        }
        return tiles;
    }

    string solve() {
        query_edge_ids_master(edges, num_agents, ids_per_msg, open, boundary_edges());
        string path;
        int queried_rounds = 0;
        while (!try_build_path(n, edges, open, path)) {
            vector<int> tiles = optimistic_path_tiles();
            if (tiles.empty()) break;
            vector<int> ids;
            for (int t : tiles) {
                if (mapped[t]) continue;
                mapped[t] = 1;
                ids.insert(ids.end(), internal_edges[t].begin(), internal_edges[t].end());
            }
            if (ids.empty()) break;
            query_edge_ids_master(edges, num_agents, ids_per_msg, open, ids);
            ++queried_rounds;
            if (queried_rounds > tile_count) break;
        }
        if (try_build_path(n, edges, open, path)) return path;

        vector<int> order = build_diagonal_order(n, edges, FullmapPlan{});
        query_edge_ids_master(edges, num_agents, ids_per_msg, open, order);
        return build_path(n, edges, open);
    }
};

static FullmapPlan select_fullmap_plan(int n, int num_agents) {
    FullmapPlan plan;
    if (num_agents >= 9 && num_agents <= 20 && n >= 51 && n <= 55) {
        plan.chunk_cap = 20;
        plan.order_mode = 0;
    } else if (num_agents >= 9 && num_agents <= 20 && n >= 56 && n <= 89) {
        plan.chunk_cap = SMALL9_CHUNK_CAP;
        plan.order_mode = SMALL9_ORDER_MODE;
    } else if (num_agents >= 21 && num_agents <= 22 && n >= 51 && n <= 89) {
        plan.chunk_cap = SMALL21_CHUNK_CAP;
        plan.order_mode = SMALL21_ORDER_MODE;
    } else if (num_agents >= 23 && num_agents <= 25 && n >= 51 && n <= 89) {
        plan.chunk_cap = SMALL23_CHUNK_CAP;
        plan.order_mode = SMALL23_ORDER_MODE;
    } else if (num_agents >= 26 && num_agents <= 34 && n >= 51 && n <= 89) {
        plan.chunk_cap = SMALL26_CHUNK_CAP;
        plan.order_mode = SMALL26_ORDER_MODE;
    } else if (num_agents >= 35 && n <= 99) {
        plan.chunk_cap = TINY_HIGH_CHUNK_CAP;
        plan.order_mode = 3;
        plan.diag_weight = TINY_HIGH_DIAG_WEIGHT;
        plan.anti_weight = TINY_HIGH_ANTI_WEIGHT;
    } else if (num_agents >= 35 && num_agents <= 45 && n >= 100 && n <= 125) {
        plan.chunk_cap = SMALL_HIGH_CHUNK_CAP;
        plan.order_mode = SMALL_HIGH_ORDER_MODE;
        plan.diag_weight = SMALL_HIGH_DIAG_WEIGHT;
        plan.anti_weight = SMALL_HIGH_ANTI_WEIGHT;
    } else if (num_agents >= 46 && n >= 100 && n <= 125) {
        plan.chunk_cap = SMALL46_CHUNK_CAP;
        plan.order_mode = SMALL46_ORDER_MODE;
        plan.diag_weight = SMALL46_DIAG_WEIGHT;
        plan.anti_weight = SMALL46_ANTI_WEIGHT;
    } else if (num_agents >= 15 && num_agents <= 25 && n >= 90 && n <= 110) {
        plan.chunk_cap = 40;
        plan.order_mode = 0;
    } else if (num_agents >= 5 && num_agents <= 8 && n >= 101 && n <= 125) {
        plan.chunk_cap = 64;
    } else if (num_agents >= 26 && num_agents <= 34 && n >= 101 && n <= 125) {
        plan.chunk_cap = BAND101_MID_CHUNK_CAP;
        plan.order_mode = BAND101_MID_ORDER_MODE;
        plan.diag_weight = BAND101_MID_DIAG_WEIGHT;
        plan.anti_weight = BAND101_MID_ANTI_WEIGHT;
    } else if (num_agents >= 5 && num_agents <= 8 && n >= 127 && n <= 159) {
        plan.order_mode = 0;
    } else if (num_agents <= 8 && n >= 160 && n <= 180) {
        plan.chunk_cap = 80;
        plan.order_mode = 3;
        plan.diag_weight = 3;
        plan.anti_weight = 1;
    } else if (num_agents == 10 && n == 169) {
        plan.chunk_cap = 80;
        plan.order_mode = 2;
    } else if (num_agents >= 9 && num_agents <= 19 && n >= 165 && n <= 180) {
        plan.chunk_cap = 72;
        plan.order_mode = 3;
        plan.diag_weight = 10;
        plan.anti_weight = 1;
    } else if (num_agents >= 9 && num_agents <= 19 && n >= 160 && n <= 164) {
        plan.chunk_cap = 48;
        plan.order_mode = 2;
    } else if (num_agents == 10 && n == 129) {
        plan.chunk_cap = 56;
        plan.order_mode = 1;
    } else if (num_agents >= 10 && n >= 127 && n <= 159) {
        if (num_agents <= 14) {
            plan.chunk_cap = 64;
            plan.order_mode = 2;
        } else if (num_agents == 15 && n <= 145) {
            plan.chunk_cap = 64;
            plan.order_mode = FULLMAP_ORDER_MODE;
        } else if (num_agents >= 35 && num_agents <= 38) {
            plan.chunk_cap = 64;
            plan.order_mode = FULLMAP_ORDER_MODE;
        } else if (num_agents >= 39 && num_agents <= 40) {
            plan.chunk_cap = 40;
            plan.order_mode = 1;
        } else {
            plan.chunk_cap = BAND127_HIGH_CHUNK_CAP;
            plan.order_mode = BAND127_HIGH_ORDER_MODE;
            plan.diag_weight = BAND127_HIGH_DIAG_WEIGHT;
            plan.anti_weight = BAND127_HIGH_ANTI_WEIGHT;
        }
    } else if (num_agents >= 30 && n >= 160 && n <= 180) {
        plan.chunk_cap = MID_HIGH_CHUNK_CAP;
        plan.order_mode = 3;
        plan.diag_weight = MID_HIGH_DIAG_WEIGHT;
        plan.anti_weight = MID_HIGH_ANTI_WEIGHT;
    } else if (num_agents >= 27 && num_agents < 30 && n >= 160 && n <= 180) {
        plan.chunk_cap = 48;
    } else if (num_agents >= 20 && num_agents <= 26 && n >= 160 && n <= 180) {
        plan.chunk_cap = 160;
    } else if (num_agents >= 15 && n >= 181 && n <= 189) {
        if (num_agents <= 35) {
            plan.chunk_cap = BAND181_CHUNK_CAP;
            plan.order_mode = BAND181_ORDER_MODE;
            plan.diag_weight = BAND181_DIAG_WEIGHT;
            plan.anti_weight = BAND181_ANTI_WEIGHT;
        } else {
            plan.chunk_cap = 48;
        }
    } else if (num_agents >= 9 && num_agents <= 14 && n >= 191 && n <= 230) {
        plan.chunk_cap = 80;
    } else if (num_agents >= 15 && num_agents <= 29 && n >= 191 && n <= 210) {
        plan.chunk_cap = 64;
    } else if (num_agents >= 30 && n >= 190 && n <= 210) {
        plan.chunk_cap = 64;
    } else if (num_agents >= 38 && n >= 210 && n <= 240) {
        plan.chunk_cap = BAND221_CHUNK_CAP;
        if (num_agents == 39) {
            plan.order_mode = BAND221_K39_ORDER_MODE;
        } else {
            plan.order_mode = BAND221_ORDER_MODE;
            plan.diag_weight = BAND221_DIAG_WEIGHT;
            plan.anti_weight = BAND221_ANTI_WEIGHT;
        }
    } else if (num_agents >= 20 && num_agents < 38 && n >= 211 && n <= 240) {
        plan.chunk_cap = 48;
        plan.order_mode = 0;
    } else if (num_agents >= 21 && n >= 241 && n <= 260) {
        plan.chunk_cap = 64;
    } else if (num_agents >= 12 && num_agents <= 20 && n >= 261 && n <= 290) {
        plan.chunk_cap = BAND261_LOW_CHUNK_CAP;
        plan.order_mode = BAND261_LOW_ORDER_MODE;
        plan.diag_weight = BAND261_LOW_DIAG_WEIGHT;
        plan.anti_weight = BAND261_LOW_ANTI_WEIGHT;
    } else if (num_agents >= 21 && num_agents <= 29 && n >= 261 && n <= 290) {
        plan.chunk_cap = BAND261_MID_CHUNK_CAP;
    } else if (num_agents >= 30 && num_agents <= 40 && n >= 260 && n <= 290) {
        plan.chunk_cap = 80;
        plan.order_mode = 2;
    } else if (num_agents >= 41 && n >= 261 && n <= 290) {
        plan.chunk_cap = 80;
    } else if (num_agents >= 41 && n >= 291 && n <= 321) {
        plan.chunk_cap = 48;
    } else if (num_agents >= 30 && num_agents <= 40 && n >= 291 && n <= 321) {
        plan.chunk_cap = 80;
    } else if (num_agents >= 20 && num_agents <= 29 && n >= 291 && n <= 321) {
        plan.chunk_cap = 64;
    } else if (num_agents >= 5 && num_agents <= 9 && n >= 301 && n <= 360) {
        plan.order_mode = 2;
    } else if (num_agents >= 12 && num_agents <= 20 && n >= 330 && n <= 360) {
        plan.chunk_cap = BAND330_MID_CHUNK_CAP;
        plan.order_mode = BAND330_MID_ORDER_MODE;
        plan.diag_weight = BAND330_MID_DIAG_WEIGHT;
        plan.anti_weight = BAND330_MID_ANTI_WEIGHT;
    } else if (num_agents >= 45 && n >= 361 && n <= 400) {
        plan.chunk_cap = BAND361_HIGH_CHUNK_CAP;
    } else if (num_agents >= 10 && num_agents <= 20 && n >= 401 && n <= 430) {
        plan.chunk_cap = BAND401_LOW_CHUNK_CAP;
    } else if (num_agents >= 30 && num_agents <= 40 && n >= 421 && n <= 430) {
        plan.chunk_cap = BAND421_MID_CHUNK_CAP;
    } else if (num_agents >= 30 && n >= 401 && n <= 430) {
        plan.chunk_cap = BAND401_HIGH_CHUNK_CAP;
    } else if (num_agents >= 5 && num_agents <= 9 && n >= 431) {
        plan.order_mode = 3;
        plan.diag_weight = 8;
        plan.anti_weight = 1;
    } else if (num_agents >= 10 && num_agents <= 15 && n >= 431) {
        plan.chunk_cap = HIGHN_LOW_CHUNK_CAP;
        plan.order_mode = HIGHN_LOW_ORDER_MODE;
        plan.diag_weight = HIGHN_LOW_DIAG_WEIGHT;
        plan.anti_weight = HIGHN_LOW_ANTI_WEIGHT;
    } else if (num_agents >= 16 && num_agents <= 29 && n == 501) {
        plan.chunk_cap = 192;
        plan.order_mode = 3;
        plan.diag_weight = 3;
        plan.anti_weight = 1;
    } else if (num_agents >= 30 && n >= 431) {
        if ((n >= 435 && n <= 439) || (n >= 443 && n <= 445)) {
            plan.chunk_cap = 80;
        } else {
            plan.chunk_cap = HIGHN_CHUNK_CAP;
            plan.order_mode = HIGHN_ORDER_MODE;
            plan.diag_weight = HIGHN_DIAG_WEIGHT;
            plan.anti_weight = HIGHN_ANTI_WEIGHT;
        }
    }
    return plan;
}

static vector<int> build_diagonal_order(int n, const vector<Edge>& edges, const FullmapPlan& plan) {
    int m = (n + 1) / 2;
    vector<int> order(edges.size());
    iota(order.begin(), order.end(), 0);
    sort(order.begin(), order.end(), [&](int lhs, int rhs) {
        auto key = [&](int idx) {
            const Edge& e = edges[idx];
            int ai = e.a / m, aj = e.a % m;
            int bi = e.b / m, bj = e.b % m;
            int mid_i2 = ai + bi;
            int mid_j2 = aj + bj;
            int diag = abs(mid_i2 - mid_j2);
            int anti = abs((mid_i2 + mid_j2) - 2 * (m - 1));
            if (plan.order_mode == 1) {
                return tuple<int, int, int>(diag, -(mid_i2 + mid_j2), idx);
            }
            if (plan.order_mode == 2) {
                return tuple<int, int, int>(diag, mid_i2 + mid_j2, idx);
            }
            if (plan.order_mode == 3) {
                int mixed = plan.diag_weight * diag + plan.anti_weight * anti;
                return tuple<int, int, int>(mixed, diag, idx);
            }
            if (plan.order_mode == 4) {
                int endpoint = min(mid_i2 + mid_j2, 4 * (m - 1) - (mid_i2 + mid_j2));
                return tuple<int, int, int>(diag, endpoint, idx);
            }
            if (plan.order_mode == 5) {
                int edge_i = min(mid_i2, 2 * (m - 1) - mid_i2);
                int edge_j = min(mid_j2, 2 * (m - 1) - mid_j2);
                int border = min(edge_i, edge_j);
                int rail = min(diag, 2 * border);
                return tuple<int, int, int>(rail, diag, idx);
            }
            if (plan.order_mode == 6) {
                int edge_i = min(mid_i2, 2 * (m - 1) - mid_i2);
                int edge_j = min(mid_j2, 2 * (m - 1) - mid_j2);
                int border = min(edge_i, edge_j);
                int center = abs(mid_i2 - (m - 1)) + abs(mid_j2 - (m - 1));
                int progress = mid_i2 + mid_j2;
                int endpoint = min(progress, 4 * (m - 1) - progress);
                int mixed = plan.diag_weight * diag
                    + plan.anti_weight * anti
                    + ORDER_BORDER_WEIGHT * border
                    + ORDER_CENTER_WEIGHT * center
                    + ORDER_ENDPOINT_WEIGHT * endpoint;
                return tuple<int, int, int>(mixed, diag, idx);
            }
            return tuple<int, int, int>(diag, anti, idx);
        };
        return key(lhs) < key(rhs);
    });
    return order;
}

static int fullmap_chunk_size(int total_edges, int num_agents, int chunk_cap) {
    int target = (total_edges + num_agents - 1) / num_agents;
    if (target < 64) return max(8, target);
    return min(chunk_cap, target);
}

static int fullmap_active_workers(int total_edges, int num_agents, int chunk_size) {
    if (num_agents <= 1 || total_edges <= 0) return 0;
    int useful_blocks = (total_edges + chunk_size - 1) / chunk_size;
    return min({num_agents - 1, chunk_size + 1, useful_blocks, ACTIVE_WORKER_CAP});
}

static int fullmap_master_count(int chunk_size, int active_workers) {
    return max(0, chunk_size + 1 - active_workers);
}

static long long fullmap_wave_span(int chunk_size, int active_workers) {
    return 1LL * active_workers * chunk_size + fullmap_master_count(chunk_size, active_workers);
}

static void query_wave_worker(
    const vector<Edge>& edges,
    const vector<int>& order,
    int agent_id,
    int active_workers,
    int chunk_size
) {
    if (agent_id > active_workers) {
        cout << "halt" << '\n' << flush;
        exit(0);
    }

    int master_count = fullmap_master_count(chunk_size, active_workers);
    long long wave_span = fullmap_wave_span(chunk_size, active_workers);
    vector<int> chunk;
    chunk.reserve(chunk_size);
    auto flush_chunk = [&](bool final_chunk) {
        char kind = final_chunk ? 'F' : 'B';
        string body = string(1, kind) + " " + to_string((int)chunk.size());
        if (!chunk.empty()) body += " " + encode_bits(chunk);
        send_message(0, body);
        chunk.clear();
    };

    for (long long wave = 0;; ++wave) {
        long long start = wave * wave_span + master_count + 1LL * (agent_id - 1) * chunk_size;
        if (start >= (int)order.size()) {
            flush_chunk(true);
            break;
        }
        long long end = min<long long>((int)order.size(), start + chunk_size);
        for (long long pos = start; pos < end; ++pos) {
            const Edge& e = edges[order[pos]];
            chunk.push_back(ask_cell(e.r, e.c) == "1");
        }
        bool final_chunk = end >= (int)order.size();
        flush_chunk(final_chunk);
        if (final_chunk) break;
    }
    cout << "halt" << '\n' << flush;
    exit(0);
}

static void query_master_wave(
    const vector<Edge>& edges,
    const vector<int>& order,
    long long wave,
    int active_workers,
    int chunk_size,
    vector<signed char>& open,
    int& known_open,
    int& known_closed
) {
    int master_count = fullmap_master_count(chunk_size, active_workers);
    long long start = wave * fullmap_wave_span(chunk_size, active_workers);
    long long end = min<long long>((int)order.size(), start + master_count);
    for (long long pos = start; pos < end; ++pos) {
        const Edge& e = edges[order[pos]];
        signed char bit = (ask_cell(e.r, e.c) == "1");
        if (open[order[pos]] == -1) {
            if (bit) ++known_open;
            else ++known_closed;
        }
        open[order[pos]] = bit;
    }
}

static void collect_prefix_positions(
    int total_edges,
    int worker,
    int prefix_waves,
    int active_workers,
    int chunk_size,
    vector<int>& positions
) {
    positions.clear();
    int master_count = fullmap_master_count(chunk_size, active_workers);
    long long wave_span = fullmap_wave_span(chunk_size, active_workers);
    for (int wave = 0; wave < prefix_waves; ++wave) {
        long long start;
        long long count;
        if (worker == 0) {
            start = 1LL * wave * wave_span;
            count = master_count;
        } else {
            start = 1LL * wave * wave_span + master_count + 1LL * (worker - 1) * chunk_size;
            count = chunk_size;
        }
        long long end = min<long long>(total_edges, start + count);
        for (long long pos = start; pos < end; ++pos) positions.push_back((int)pos);
    }
}

static void query_prefix_worker_then_loop(
    int n,
    const vector<Edge>& edges,
    const vector<int>& order,
    int agent_id,
    int active_workers,
    int chunk_size,
    int prefix_waves
) {
    if (agent_id > active_workers) {
        bidir_worker_loop(n);
        return;
    }

    vector<int> positions;
    collect_prefix_positions((int)order.size(), agent_id, prefix_waves, active_workers, chunk_size, positions);
    vector<int> bits;
    bits.reserve(positions.size());
    for (int pos : positions) {
        const Edge& e = edges[order[pos]];
        bits.push_back(ask_cell(e.r, e.c) == "1");
    }
    string body = "P " + to_string((int)bits.size());
    if (!bits.empty()) body += " " + encode_bits(bits);
    send_message(0, body);
    bidir_worker_loop(n);
}

static bool try_build_path(
    int n,
    const vector<Edge>& edges,
    const vector<signed char>& open,
    string& path
) {
    int m = (n + 1) / 2;
    int rooms = m * m;
    vector<vector<pair<int, char>>> g(rooms);
    for (int i = 0; i < (int)edges.size(); ++i) {
        if (open[i] != 1) continue;
        const Edge& e = edges[i];
        g[e.a].push_back({e.b, e.move_ab});
        char back = (e.move_ab == 'R') ? 'L' : 'U';
        g[e.b].push_back({e.a, back});
    }

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

    if (parent[rooms - 1] == -1) {
        return false;
    }

    vector<char> room_moves;
    for (int v = rooms - 1; v != 0; v = parent[v]) {
        room_moves.push_back(parent_move[v]);
    }
    reverse(room_moves.begin(), room_moves.end());

    path.clear();
    path.reserve(room_moves.size() * 2);
    for (char mv : room_moves) {
        path.push_back(mv);
        path.push_back(mv);
    }
    return true;
}

static bool try_build_path_adj(
    const vector<vector<Adj>>& adj,
    const vector<signed char>& open,
    string& path
) {
    int rooms = (int)adj.size();
    vector<int> parent(rooms, -1);
    vector<char> parent_move(rooms, 0);
    queue<int> q;
    parent[0] = 0;
    q.push(0);
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        if (u == rooms - 1) break;
        for (const Adj& a : adj[u]) {
            if (open[a.edge_id] != 1 || parent[a.to] != -1) continue;
            parent[a.to] = u;
            parent_move[a.to] = a.move;
            q.push(a.to);
        }
    }

    if (parent[rooms - 1] == -1) return false;

    vector<char> room_moves;
    for (int v = rooms - 1; v != 0; v = parent[v]) {
        room_moves.push_back(parent_move[v]);
    }
    reverse(room_moves.begin(), room_moves.end());

    path.clear();
    path.reserve(room_moves.size() * 2);
    for (char mv : room_moves) {
        path.push_back(mv);
        path.push_back(mv);
    }
    return true;
}

static bool apply_tree_forcing(
    int rooms,
    const vector<Edge>& edges,
    vector<signed char>& open,
    int& known_open,
    int& known_closed
) {
    if (!TREE_INFER_MODE) return false;

    if (TREE_INFER_MODE == 2) {
        ForceDsu dsu(rooms);
        for (int i = 0; i < (int)edges.size(); ++i) {
            if (open[i] == 1) dsu.unite(edges[i].a, edges[i].b);
        }
        bool changed = false;
        for (int i = 0; i < (int)edges.size(); ++i) {
            if (open[i] != -1) continue;
            if (dsu.find(edges[i].a) == dsu.find(edges[i].b)) {
                open[i] = 0;
                ++known_closed;
                changed = true;
            }
        }
        return changed;
    }

    bool any_changed = false;
    bool changed = true;
    while (changed) {
        changed = false;

        ForceDsu dsu(rooms);
        for (int i = 0; i < (int)edges.size(); ++i) {
            if (open[i] == 1) dsu.unite(edges[i].a, edges[i].b);
        }

        vector<int> root_id(rooms, -1);
        vector<int> comp(rooms, -1);
        int comps = 0;
        for (int v = 0; v < rooms; ++v) {
            int root = dsu.find(v);
            int& id = root_id[root];
            if (id == -1) id = comps++;
            comp[v] = id;
        }

        vector<vector<pair<int, int>>> graph(comps);
        for (int i = 0; i < (int)edges.size(); ++i) {
            if (open[i] != -1) continue;
            int a = comp[edges[i].a];
            int b = comp[edges[i].b];
            if (a == b) {
                open[i] = 0;
                ++known_closed;
                changed = true;
                any_changed = true;
            } else {
                graph[a].push_back({b, i});
                graph[b].push_back({a, i});
            }
        }
        if (changed) continue;

        vector<int> tin(comps, -1), low(comps, 0), bridges;
        int timer = 0;
        auto dfs = [&](auto&& self, int u, int parent_edge) -> void {
            tin[u] = low[u] = timer++;
            for (auto [v, edge_id] : graph[u]) {
                if (edge_id == parent_edge) continue;
                if (tin[v] != -1) {
                    low[u] = min(low[u], tin[v]);
                    continue;
                }
                self(self, v, edge_id);
                low[u] = min(low[u], low[v]);
                if (low[v] > tin[u]) bridges.push_back(edge_id);
            }
        };
        for (int v = 0; v < comps; ++v) {
            if (tin[v] == -1) dfs(dfs, v, -1);
        }

        for (int edge_id : bridges) {
            if (open[edge_id] != -1) continue;
            open[edge_id] = 1;
            ++known_open;
            changed = true;
            any_changed = true;
        }
    }
    return any_changed;
}

static string build_path(int n, const vector<Edge>& edges, const vector<signed char>& open) {
    string path;
    if (!try_build_path(n, edges, open, path)) {
        // Should never happen after all edge cells are known. Prefer a no-claim
        // timeout over an invalid claim if something goes badly wrong.
        while (true) {
            cout << "." << '\n' << flush;
            string ok;
            if (!(cin >> ok)) exit(0);
        }
    }
    return path;
}

static int hybrid_prefix_waves(int n, int num_agents) {
    if (!HYBRID_PATH_MODE) return 0;
    if (num_agents >= EXTRA_HYBRID_MIN_AGENTS && num_agents <= EXTRA_HYBRID_MAX_AGENTS
        && n >= EXTRA_HYBRID_MIN_N && n <= EXTRA_HYBRID_MAX_N) {
        return EXTRA_HYBRID_WAVES;
    }
    if (num_agents == 3 && n >= 51 && n <= 150) return 1;
    if (num_agents == 4 && n >= 51 && n <= 150) return 1;
    if (num_agents == 4 && n >= 151 && n <= 250) return 3;
    if ((num_agents == 5 || num_agents == 6) && n >= 51 && n <= 189) return 2;
    if (num_agents == 7 && n >= 51 && n <= 169) return 2;
    if (num_agents == 7 && n >= 170 && n <= 179) return 1;
    if (num_agents == 7 && n >= 180 && n <= 189) return 2;
    return 0;
}

static int edge_geometric_bias(int n, const Edge& e, const FullmapPlan& plan) {
    int m = (n + 1) / 2;
    int ai = e.a / m, aj = e.a % m;
    int bi = e.b / m, bj = e.b % m;
    int mid_i2 = ai + bi;
    int mid_j2 = aj + bj;
    int diag = abs(mid_i2 - mid_j2);
    int anti = abs((mid_i2 + mid_j2) - 2 * (m - 1));
    return plan.diag_weight * diag + plan.anti_weight * anti;
}

static vector<int> optimistic_corridor_request(
    int n,
    const vector<Edge>& edges,
    const vector<vector<Adj>>& adj,
    const vector<signed char>& open,
    const FullmapPlan& plan
) {
    int m = (n + 1) / 2;
    int rooms = m * m;
    const long long INF = (1LL << 60);
    vector<long long> dist(rooms, INF);
    vector<int> parent(rooms, -1);
    vector<int> parent_edge(rooms, -1);
    priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> pq;
    dist[0] = 0;
    pq.push({0, 0});
    while (!pq.empty()) {
        auto [du, u] = pq.top();
        pq.pop();
        if (du != dist[u]) continue;
        if (u == rooms - 1) break;
        for (const Adj& a : adj[u]) {
            int state = open[a.edge_id];
            if (state == 0) continue;
            long long w = (state == 1) ? 0 : HYBRID_UNKNOWN_BASE + edge_geometric_bias(n, edges[a.edge_id], plan);
            if (du + w < dist[a.to]) {
                dist[a.to] = du + w;
                parent[a.to] = u;
                parent_edge[a.to] = a.edge_id;
                pq.push({dist[a.to], a.to});
            }
        }
    }
    if (parent[rooms - 1] == -1) return {};

    vector<int> room_path;
    vector<int> path_edges;
    for (int v = rooms - 1; v != 0; v = parent[v]) {
        room_path.push_back(v);
        path_edges.push_back(parent_edge[v]);
    }
    room_path.push_back(0);
    reverse(room_path.begin(), room_path.end());
    reverse(path_edges.begin(), path_edges.end());

    vector<int> request;
    vector<char> picked(edges.size(), 0);
    auto add_edge = [&](int id) {
        if (id < 0 || open[id] != -1 || picked[id]) return;
        picked[id] = 1;
        request.push_back(id);
    };
    for (int id : path_edges) add_edge(id);
    if (HYBRID_REQUEST_MODE == 0) {
        for (int room : room_path) {
            for (const Adj& a : adj[room]) add_edge(a.edge_id);
        }
    } else if (HYBRID_REQUEST_MODE == 2) {
        for (int i = 0; i < (int)room_path.size(); ++i) {
            int room = room_path[i];
            int prev = (i > 0) ? room_path[i - 1] : -1;
            int next = (i + 1 < (int)room_path.size()) ? room_path[i + 1] : -1;
            for (const Adj& a : adj[room]) {
                if (a.to == prev || a.to == next) continue;
                add_edge(a.edge_id);
            }
        }
    }
    return request;
}

static string solve_hybrid_path(
    int n,
    int num_agents,
    int max_msg_len,
    const vector<Edge>& edges,
    const vector<int>& order,
    const FullmapPlan& plan,
    int active_workers,
    int chunk_size,
    int prefix_waves
) {
    int ids_per_msg = max(1, (max_msg_len - 1) / 3);
    vector<vector<Adj>> adj = build_adj(((n + 1) / 2) * ((n + 1) / 2), edges);
    vector<signed char> open(edges.size(), -1);

    vector<int> positions;
    collect_prefix_positions((int)order.size(), 0, prefix_waves, active_workers, chunk_size, positions);
    for (int pos : positions) {
        const Edge& e = edges[order[pos]];
        open[order[pos]] = (ask_cell(e.r, e.c) == "1");
    }

    vector<char> worker_done(num_agents, 0);
    vector<int> bits;
    int received = 0;
    while (received < active_workers) {
        int sender;
        string body;
        receive_any(sender, body);
        if (sender <= 0 || sender > active_workers || worker_done[sender]) continue;
        if (body.rfind("P ", 0) != 0) continue;
        size_t p = body.find(' ', 2);
        int count = 0;
        string encoded;
        if (p == string::npos) {
            count = stoi(body.substr(2));
        } else {
            count = stoi(body.substr(2, p - 2));
            encoded = body.substr(p + 1);
        }
        decode_bits(encoded, count, bits);
        collect_prefix_positions((int)order.size(), sender, prefix_waves, active_workers, chunk_size, positions);
        int usable = min({(int)bits.size(), count, (int)positions.size()});
        for (int i = 0; i < usable; ++i) {
            open[order[positions[i]]] = (signed char)bits[i];
        }
        worker_done[sender] = 1;
        ++received;
    }

    string path;
    if (try_build_path_adj(adj, open, path)) return path;

    for (int round = 0; round < HYBRID_MAX_ROUNDS; ++round) {
        vector<int> request = optimistic_corridor_request(n, edges, adj, open, plan);
        if (request.empty()) break;
        query_edge_ids_master(edges, num_agents, ids_per_msg, open, request);
        if (try_build_path_adj(adj, open, path)) return path;
    }

    query_edge_ids_master(edges, num_agents, ids_per_msg, open, order);
    return build_path(n, edges, open);
}

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 << "!" << '\n' << flush;
        } else {
            cout << "halt" << '\n' << flush;
        }
        return 0;
    }

    if (should_use_bidir(n, num_agents)) {
        if (agent_id != 0) {
            bidir_worker_loop(n);
            return 0;
        }
        BidirMaster master(n, num_agents, max_msg_len);
        string path = should_use_priority(n, num_agents) ? master.solve_priority() : master.solve();
        cout << "! " << path << '\n' << flush;
        return 0;
    }

    int tile_size = choose_tile_size(n, num_agents);
    if (tile_size > 0) {
        if (agent_id != 0) {
            bidir_worker_loop(n);
            return 0;
        }
        TileMaster master(n, num_agents, max_msg_len, tile_size);
        string path = master.solve();
        cout << "! " << path << '\n' << flush;
        return 0;
    }

    vector<Edge> edges = build_edges(n);
    FullmapPlan plan = select_fullmap_plan(n, num_agents);
    vector<int> order = build_diagonal_order(n, edges, plan);
    int chunk_size = fullmap_chunk_size((int)edges.size(), num_agents, plan.chunk_cap);
    if (num_agents >= 35 && n <= 99) {
        if (n <= 55) {
            chunk_size = 40;
        } else if (n >= 70 && n <= 75) {
            if (num_agents <= 40) chunk_size = 36;
        } else if (n >= 90) {
            if (num_agents <= 35) chunk_size = 40;
            else if (num_agents <= 45) chunk_size = 52;
        }
    }
    int active_workers = fullmap_active_workers((int)edges.size(), num_agents, chunk_size);
    int prefix_waves = hybrid_prefix_waves(n, num_agents);
    if (prefix_waves > 0) {
        if (agent_id != 0) {
            query_prefix_worker_then_loop(n, edges, order, agent_id, active_workers, chunk_size, prefix_waves);
            return 0;
        }
        string hybrid_path = solve_hybrid_path(
            n,
            num_agents,
            max_msg_len,
            edges,
            order,
            plan,
            active_workers,
            chunk_size,
            prefix_waves
        );
        cout << "! " << hybrid_path << '\n' << flush;
        return 0;
    }

    if (agent_id != 0) {
        query_wave_worker(edges, order, agent_id, active_workers, chunk_size);
        return 0;
    }

    vector<signed char> open(edges.size(), -1);
    int known_open = 0;
    int known_closed = 0;
    int rooms = ((n + 1) / 2) * ((n + 1) / 2);
    vector<vector<Adj>> adj = build_adj(rooms, edges);
    int total_open = rooms - 1;
    int total_closed = (int)edges.size() - total_open;
    auto apply_forced_counts = [&]() {
        signed char forced = -1;
        if (known_closed == total_closed) {
            forced = 1;
        } else if (known_open == total_open) {
            forced = 0;
        } else {
            return false;
        }
        bool changed = false;
        for (signed char& state : open) {
            if (state != -1) continue;
            state = forced;
            if (forced) ++known_open;
            else ++known_closed;
            changed = true;
        }
        return changed;
    };
    auto apply_all_forcing = [&]() {
        bool changed = false;
        bool again = true;
        while (again) {
            again = false;
            if (apply_forced_counts()) {
                changed = true;
                again = true;
            }
            if (apply_tree_forcing(rooms, edges, open, known_open, known_closed)) {
                changed = true;
                again = true;
            }
        }
        return changed;
    };
    vector<char> worker_done(num_agents, 0);
    int done = 0;
    vector<int> bits;
    for (long long wave = 0; done < active_workers; ++wave) {
        query_master_wave(edges, order, wave, active_workers, chunk_size, open, known_open, known_closed);
        string early_path;
        apply_all_forcing();
        if (try_build_path_adj(adj, open, early_path)) {
            cout << "! " << early_path << '\n' << flush;
            return 0;
        }

        int expected_messages = active_workers - done;
        int received_messages = 0;
        while (done < active_workers && received_messages < expected_messages) {
            int sender;
            string body;
            receive_any(sender, body);
            if (sender <= 0 || sender > active_workers || worker_done[sender]) continue;
            if (body.rfind("B ", 0) == 0 || body.rfind("F ", 0) == 0) {
                bool final_chunk = body[0] == 'F';
                size_t p = body.find(' ', 2);
                int count = 0;
                string encoded;
                if (p == string::npos) {
                    count = stoi(body.substr(2));
                } else {
                    count = stoi(body.substr(2, p - 2));
                    encoded = body.substr(p + 1);
                }
                decode_bits(encoded, count, bits);
                long long start = wave * fullmap_wave_span(chunk_size, active_workers)
                    + fullmap_master_count(chunk_size, active_workers)
                    + 1LL * (sender - 1) * chunk_size;
                for (int i = 0; i < (int)bits.size(); ++i) {
                    long long pos = start + i;
                    if (pos >= (int)order.size()) break;
                    int edge_id = order[pos];
                    signed char bit = (signed char)bits[i];
                    if (open[edge_id] == -1) {
                        if (bit) ++known_open;
                        else ++known_closed;
                    }
                    open[edge_id] = bit;
                }
                bool check_now = true;
                if (n >= 330 && num_agents <= 15) {
                    int after_message = received_messages + 1;
                    check_now = final_chunk || after_message == expected_messages;
                } else if (n >= 390 && num_agents >= 20) {
                    int after_message = received_messages + 1;
                    check_now = final_chunk || after_message == expected_messages || after_message % 8 == 0;
                }
                bool forced_now = false;
                if (TREE_INFER_MODE == 2) {
                    forced_now = apply_forced_counts();
                    if (check_now) forced_now = apply_all_forcing() || forced_now;
                } else {
                    forced_now = apply_all_forcing();
                }
                if ((forced_now || check_now) && try_build_path_adj(adj, open, early_path)) {
                    cout << "! " << early_path << '\n' << flush;
                    return 0;
                }
                if (final_chunk) {
                    worker_done[sender] = 1;
                    ++done;
                }
                ++received_messages;
            }
        }
    }

    string path;
    apply_all_forcing();
    if (!try_build_path_adj(adj, open, path)) path = build_path(n, edges, open);
    cout << "! " << path << '\n' << flush;
    return 0;
}