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

#ifndef EDGE_ORDER_STYLE
#define EDGE_ORDER_STYLE 1
#endif

#ifndef ASTAR_MAX_AGENTS
#define ASTAR_MAX_AGENTS 5
#endif

#ifndef ASTAR_PROFILE_SET
#define ASTAR_PROFILE_SET 0
#endif

static const string BASE64_ALPHABET =
    "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/";

static int dense_tail_bits(int chars) {
    static const int table[10] = {0, 6, 13, 19, 26, 32, 39, 45, 52, 59};
    return table[chars];
}

static int dense_bits_per_message(int max_msg_len) {
    int full = max_msg_len / 9;
    int rem = max_msg_len % 9;
    return full * 59 + dense_tail_bits(rem);
}

static int whole_base95_capacity(int chars) {
    static vector<int> cache(1, 0);
    static const long double log2_95 = log2l(95.0L);
    while ((int)cache.size() <= chars) {
        int c = (int)cache.size();
        cache.push_back((int)floor(c * log2_95 + 1e-12L));
    }
    return cache[chars];
}

struct SmallBigUInt {
    vector<uint32_t> limb;

    void trim() {
        while (!limb.empty() && limb.back() == 0) limb.pop_back();
    }

    void shift_left_add_bit(int bit) {
        uint64_t carry = bit & 1;
        for (uint32_t &x : limb) {
            uint64_t v = (uint64_t)x * 2 + carry;
            x = (uint32_t)v;
            carry = v >> 32;
        }
        if (carry) limb.push_back((uint32_t)carry);
    }

    void mul_small_add(uint32_t mul, uint32_t add) {
        uint64_t carry = add;
        for (uint32_t &x : limb) {
            uint64_t v = (uint64_t)x * mul + carry;
            x = (uint32_t)v;
            carry = v >> 32;
        }
        if (carry) limb.push_back((uint32_t)carry);
    }

    uint32_t div_small(uint32_t div) {
        uint64_t rem = 0;
        for (int i = (int)limb.size() - 1; i >= 0; --i) {
            uint64_t cur = (rem << 32) | limb[i];
            limb[i] = (uint32_t)(cur / div);
            rem = cur % div;
        }
        trim();
        return (uint32_t)rem;
    }

    int bit_at(int bit) const {
        int idx = bit >> 5;
        if (idx >= (int)limb.size()) return 0;
        return (limb[idx] >> (bit & 31)) & 1U;
    }
};

static bool use_dense_codec_for(int n, int num_agents) {
    if (num_agents <= ASTAR_MAX_AGENTS) return false;
    switch (n) {
        case 151:
            return num_agents == 6 || num_agents == 7;
        case 201:
            return 6 <= num_agents && num_agents <= 12;
        case 249:
            return 6 <= num_agents && num_agents <= 20 && num_agents != 10;
        case 301:
            return 6 <= num_agents && num_agents <= 24;
        case 351:
            return 6 <= num_agents && num_agents <= 30 &&
                   num_agents != 8 && num_agents != 10;
        case 401:
            return ((6 <= num_agents && num_agents <= 30) || num_agents == 50) &&
                   num_agents != 13;
        case 451:
            return ((7 <= num_agents && num_agents <= 21) ||
                    num_agents == 23 || num_agents == 24 ||
                    num_agents == 30 || num_agents == 50) &&
                   num_agents != 11 && num_agents != 13;
        case 501:
            return ((6 <= num_agents && num_agents <= 30) || num_agents == 37 ||
                    num_agents == 50) &&
                   num_agents != 8 && num_agents != 9 && num_agents != 10 &&
                   num_agents != 16 && num_agents != 20 && num_agents != 27;
        default:
            return false;
    }
}

static bool use_grouped_dense_codec_for(int n, int num_agents) {
    return (n == 249 && num_agents == 6) ||
           (n == 351 && num_agents == 6) ||
           (n == 451 && num_agents == 30) ||
           (n == 501 && num_agents == 37);
}

static bool use_whole_dense_codec_for(int n, int num_agents) {
    return n == 451 && num_agents == 30;
}

static int skip_inferred_payload_for(int n, int num_agents) {
    if (n == 151 && num_agents == 7) return 1560;
    if (n == 249 && num_agents == 6) return 1620;
    if (n == 249 && num_agents == 9) return 1630;
    if (n == 301 && num_agents == 13) return 1660;
    if (n == 351 && num_agents == 6) return 1610;
    if (n == 351 && num_agents == 7) return 1660;
    if (n == 351 && num_agents == 9) return 1620;
    if (n == 351 && num_agents == 12) return 1620;
    if (n == 401 && num_agents == 9) return 1681;
    if (n == 451 && num_agents == 12) return 1600;
    if (n == 501 && num_agents == 6) return 1640;
    if (n == 501 && num_agents == 7) return 1681;
    if (n == 501 && num_agents == 8) return 1640;
    if (n == 501 && num_agents == 9) return 1640;
    if (n == 501 && num_agents == 10) return 1681;
    if (n == 501 && num_agents == 12) return 1650;
    if (n == 501 && num_agents == 24) return 1668;
    return 0;
}

static bool use_local_prune_for(int n, int num_agents) {
    if (n <= 63) return num_agents <= 16;
    if (n <= 75) return num_agents <= 20;
    if (n <= 101) return num_agents <= 26;
    if (n <= 151) return num_agents <= 40;
    if (n <= 175) return num_agents <= 45;
    return true;
}

static int choose_edge_order_style(int n, int num_agents) {
#if EDGE_ORDER_STYLE != 1
    (void)n;
    (void)num_agents;
    return EDGE_ORDER_STYLE;
#else
    if (n == 201) return num_agents >= 16 ? 12 : 1;
    if (n == 249) return num_agents >= 20 ? 12 : 1;
    if (n == 301) return num_agents >= 24 ? 12 : 1;
    if (n == 351) return num_agents >= 24 ? 12 : 1;
    if (n == 401) return num_agents == 50 ? 12 : 1;
    if (n == 451) return num_agents == 37 ? 12 : 1;
    return 1;
#endif
}

static string encode_bits(const vector<unsigned char> &bits, int dense_codec_mode) {
    if (dense_codec_mode == 0) {
        string out;
        out.reserve((bits.size() + 5) / 6);
        int val = 0, cnt = 0;
        for (unsigned char bit : bits) {
            val = (val << 1) | (bit & 1);
            ++cnt;
            if (cnt == 6) {
                out.push_back(BASE64_ALPHABET[val]);
                val = 0;
                cnt = 0;
            }
        }
        if (cnt) {
            val <<= (6 - cnt);
            out.push_back(BASE64_ALPHABET[val]);
        }
        return out;
    }

    if (dense_codec_mode == 1) {
        string out;
        out.reserve(((bits.size() + 12) / 13) * 2);
        int val = 0, cnt = 0;
        for (unsigned char bit : bits) {
            val = (val << 1) | (bit & 1);
            ++cnt;
            if (cnt == 13) {
                out.push_back((char)(' ' + val / 95));
                out.push_back((char)(' ' + val % 95));
                val = 0;
                cnt = 0;
            }
        }
        if (cnt) {
            val <<= (13 - cnt);
            out.push_back((char)(' ' + val / 95));
            out.push_back((char)(' ' + val % 95));
        }
        return out;
    }

    if (dense_codec_mode == 2) {
        string out;
        out.reserve(((bits.size() + 58) / 59) * 9);
        int pos = 0;
        while (pos < (int)bits.size()) {
            int remaining = (int)bits.size() - pos;
            int chars = 9;
            if (remaining < 59) {
                chars = 1;
                while (dense_tail_bits(chars) < remaining) ++chars;
            }
            int group_bits = dense_tail_bits(chars);
            uint64_t val = 0;
            for (int i = 0; i < group_bits; ++i) {
                val <<= 1;
                if (pos < (int)bits.size()) {
                    val |= bits[pos++] & 1;
                }
            }
            string group(chars, ' ');
            for (int i = chars - 1; i >= 0; --i) {
                group[i] = (char)(' ' + (val % 95));
                val /= 95;
            }
            out += group;
        }
        return out;
    }

    if (dense_codec_mode == 4) {
        int len = (int)bits.size();
        string out;
        out.reserve(2 + (len + 6) / 6);
        out.push_back((char)(' ' + len / 95));
        out.push_back((char)(' ' + len % 95));
        out += encode_bits(bits, 3);
        return out;
    }

    if (dense_codec_mode == 5) {
        return encode_bits(bits, 3);
    }

    int chars = 1;
    while (whole_base95_capacity(chars) < (int)bits.size()) ++chars;
    int group_bits = whole_base95_capacity(chars);
    SmallBigUInt val;
    for (int i = 0; i < group_bits; ++i) {
        val.shift_left_add_bit(i < (int)bits.size() ? (bits[i] & 1) : 0);
    }
    string out(chars, ' ');
    for (int i = chars - 1; i >= 0; --i) {
        int digit = (int)val.div_small(95);
        out[i] = (char)(' ' + digit);
    }
    return out;
}

static vector<unsigned char> decode_bits(const string &text, int need, int dense_codec_mode) {
    vector<unsigned char> bits;
    bits.reserve(need);
    if (dense_codec_mode == 0) {
        for (char ch : text) {
            if ((int)bits.size() >= need) break;
            size_t pos = BASE64_ALPHABET.find(ch);
            if (pos == string::npos) continue;
            int v = (int)pos;
            for (int b = 5; b >= 0 && (int)bits.size() < need; --b) {
                bits.push_back((v >> b) & 1);
            }
        }
        return bits;
    }

    if (dense_codec_mode == 1) {
        for (int i = 0; i + 1 < (int)text.size() && (int)bits.size() < need; i += 2) {
            int hi = (unsigned char)text[i] - ' ';
            int lo = (unsigned char)text[i + 1] - ' ';
            if (hi < 0 || hi >= 95 || lo < 0 || lo >= 95) continue;
            int v = hi * 95 + lo;
            for (int b = 12; b >= 0 && (int)bits.size() < need; --b) {
                bits.push_back((v >> b) & 1);
            }
        }
        return bits;
    }

    if (dense_codec_mode == 2) {
        for (int i = 0; i < (int)text.size() && (int)bits.size() < need;) {
            int chars = min(9, (int)text.size() - i);
            int group_bits = dense_tail_bits(chars);
            uint64_t v = 0;
            bool valid = true;
            for (int j = 0; j < chars; ++j) {
                int digit = (unsigned char)text[i + j] - ' ';
                if (digit < 0 || digit >= 95) {
                    valid = false;
                    break;
                }
                v = v * 95 + (uint64_t)digit;
            }
            i += chars;
            if (!valid) continue;
            for (int b = group_bits - 1; b >= 0 && (int)bits.size() < need; --b) {
                bits.push_back((v >> b) & 1);
            }
        }
        return bits;
    }

    if (dense_codec_mode == 4) {
        if ((int)text.size() < 2) return bits;
        int hi = (unsigned char)text[0] - ' ';
        int lo = (unsigned char)text[1] - ' ';
        if (hi < 0 || hi >= 95 || lo < 0 || lo >= 95) return bits;
        int len = hi * 95 + lo;
        if (need > 0) len = min(len, need);
        return decode_bits(text.substr(2), len, 3);
    }

    if (dense_codec_mode == 5) {
        return decode_bits(text, need, 3);
    }

    int group_bits = whole_base95_capacity((int)text.size());
    SmallBigUInt val;
    bool valid = true;
    for (char ch : text) {
        int digit = (unsigned char)ch - ' ';
        if (digit < 0 || digit >= 95) {
            valid = false;
            break;
        }
        val.mul_small_add(95, digit);
    }
    if (!valid) return bits;
    for (int b = group_bits - 1; b >= 0 && (int)bits.size() < need; --b) {
        bits.push_back(val.bit_at(b));
    }
    return bits;
}

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

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

static pair<int, string> recv_any() {
    cout << "< ?" << '\n' << flush;
    string sender;
    if (!(cin >> sender)) exit(0);
    string body;
    getline(cin, body);
    if (!body.empty() && body[0] == ' ') body.erase(body.begin());
    if (sender == "-") return {-1, ""};
    return {stoi(sender), body};
}

struct AStarEdge {
    long long score;
    uint64_t tie;
    int side;
    int from;
    int to;
    int dir_idx;
    char ch;
    bool operator<(const AStarEdge &o) const {
        if (score != o.score) return score > o.score;
        return tie > o.tie;
    }
};

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

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

static int choose_astar_profile_set(int n, int num_agents) {
    if (n == 51 && num_agents <= 4) return 1;
    if (n == 101 && num_agents >= 2) return 2;
    if (n == 201) {
        if (num_agents == 1 || num_agents == 4 || num_agents == 5) return 2;
        if (num_agents == 2 || num_agents == 3) return 1;
    }
    if (n == 249 && num_agents <= 2) return 1;
    if (n == 351) {
        if (num_agents == 2) return 2;
        if (3 <= num_agents && num_agents <= 5) return 1;
    }
    if (n == 501) {
        if (num_agents == 1) return 1;
        if (num_agents == 2) return 2;
    }
    return 0;
}

static int choose_hybrid_racers(int n, int num_agents) {
    (void)n;
    (void)num_agents;
    return 0;
}

static void run_bidirectional_astar(int n, int num_agents, int agent_id) {
    int rooms = (n + 1) / 2;
    int total = rooms * rooms;
    auto node_id = [rooms](int r, int c) { return r * rooms + c; };
    auto row = [rooms](int v) { return v / rooms; };
    auto col = [rooms](int v) { return v % rooms; };

    const int dr[4] = {-1, 1, 0, 0};
    const int dc[4] = {0, 0, -1, 1};
    const char dch[4] = {'U', 'D', 'L', 'R'};
    const int rev[4] = {1, 0, 3, 2};

    int profile_set = ASTAR_PROFILE_SET ? ASTAR_PROFILE_SET : choose_astar_profile_set(n, num_agents);
    vector<pair<int, int>> profiles;
    if (profile_set == 1) {
        profiles = {
            {65536, 65536}, {2000000, 16384}, {8192, 0},
            {16384, 16384}, {2000000, 65536},
        };
    } else if (profile_set == 2) {
        profiles = {
            {8192, 4096}, {2000000, 262144}, {2000000, 4096},
            {2000000, 65536}, {65536, 65536},
        };
    } else {
        profiles = {
            {1000000, 1}, {262144, 4096}, {65536, 4096},
            {16384, 4096}, {4096, 4096},
        };
    }
    auto [weight, noise] = profiles[agent_id % (int)profiles.size()];
    uint64_t salt =
        splitmix64(0xA57A5A7A0DDF00DULL + (uint64_t)agent_id * 0x9e3779b97f4a7c15ULL);

    vector<array<signed char, 4>> edge_state(total);
    for (auto &a : edge_state) a.fill(-1);
    vector<array<unsigned char, 2>> seen(total);
    vector<array<int, 2>> parent(total);
    vector<array<char, 2>> parent_dir(total);
    vector<array<int, 2>> dist(total);
    for (int i = 0; i < total; ++i) {
        seen[i] = {0, 0};
        parent[i] = {-1, -1};
        parent_dir[i] = {0, 0};
        dist[i] = {0, 0};
    }

    int start = node_id(0, 0);
    int goal = node_id(rooms - 1, rooms - 1);
    seen[start][0] = 1;
    seen[goal][1] = 1;
    parent[start][0] = start;
    parent[goal][1] = goal;

    auto heuristic = [&](int side, int v) {
        int tr = side == 0 ? rooms - 1 : 0;
        int tc = side == 0 ? rooms - 1 : 0;
        return abs(row(v) - tr) + abs(col(v) - tc);
    };

    priority_queue<AStarEdge> pq;

    auto push_from = [&](int side, int v) {
        int r = row(v), c = col(v);
        for (int k = 0; k < 4; ++k) {
            int nr = r + dr[k], nc = c + dc[k];
            if (nr < 0 || nr >= rooms || nc < 0 || nc >= rooms) continue;
            int to = node_id(nr, nc);
            if (seen[to][side]) continue;
            if (edge_state[v][k] == 0) continue;
            uint64_t tie =
                splitmix64(salt ^ (uint64_t)(side * 2000003 + v * 37 + k * 10007 + to));
            long long score = (long long)(dist[v][side] + 1) * 1024LL +
                              (long long)heuristic(side, to) * weight;
            if (noise) score += (long long)(tie % (uint64_t)noise);
            pq.push({score, tie, side, v, to, k, dch[k]});
        }
    };

    auto side_path = [&](int side, int v) {
        string path;
        while (parent[v][side] != v) {
            path.push_back(parent_dir[v][side]);
            v = parent[v][side];
        }
        reverse(path.begin(), path.end());
        return path;
    };

    auto claim = [&](int meet) {
        string a = side_path(0, meet);
        string b = side_path(1, meet);
        string room_moves = a;
        for (int i = (int)b.size() - 1; i >= 0; --i) {
            room_moves.push_back(opposite_dir(b[i]));
        }
        string moves;
        moves.reserve(room_moves.size() * 2);
        for (char ch : room_moves) {
            moves.push_back(ch);
            moves.push_back(ch);
        }
        cout << "! " << moves << '\n' << flush;
        exit(0);
    };

    push_from(0, start);
    push_from(1, goal);

    while (!pq.empty()) {
        AStarEdge e = pq.top();
        pq.pop();
        if (!seen[e.from][e.side] || seen[e.to][e.side]) continue;
        signed char open = edge_state[e.from][e.dir_idx];
        if (open < 0) {
            int r = row(e.from), c = col(e.from);
            open = query_cell(2 * r + 1 + dr[e.dir_idx], 2 * c + 1 + dc[e.dir_idx]) ? 1 : 0;
            edge_state[e.from][e.dir_idx] = open;
            edge_state[e.to][rev[e.dir_idx]] = open;
        }
        if (!open) continue;
        seen[e.to][e.side] = 1;
        parent[e.to][e.side] = e.from;
        parent_dir[e.to][e.side] = e.ch;
        dist[e.to][e.side] = dist[e.from][e.side] + 1;
        if (seen[e.to][e.side ^ 1]) claim(e.to);
        push_from(e.side, e.to);
    }

    cout << "halt" << '\n' << flush;
    exit(0);
}

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

    bool small_scan = (num_agents == 5 && n <= 75);

    int scan_offset = 0;
    int scan_num_agents = num_agents;
    int scan_agent_id = agent_id;
    int hybrid_racers = choose_hybrid_racers(n, num_agents);
    if (hybrid_racers > 0 && num_agents > ASTAR_MAX_AGENTS &&
        num_agents - hybrid_racers >= 2) {
        if (agent_id < hybrid_racers) {
            run_bidirectional_astar(n, num_agents, agent_id);
        }
        scan_offset = hybrid_racers;
        scan_num_agents = num_agents - hybrid_racers;
        scan_agent_id = agent_id - hybrid_racers;
    } else if (num_agents <= ASTAR_MAX_AGENTS && !small_scan) {
        run_bidirectional_astar(n, num_agents, agent_id);
    }

    int rooms = (n + 1) / 2;
    long long total_edges = 2LL * rooms * (rooms - 1);
    int dense_codec_mode = 0;
    if (max_msg_len >= 256 && skip_inferred_payload_for(n, scan_num_agents) > 0) {
        int sparse_payload = skip_inferred_payload_for(n, scan_num_agents);
        dense_codec_mode = sparse_payload > whole_base95_capacity(max_msg_len - 2) ? 5 : 4;
    } else if (max_msg_len >= 2 && use_dense_codec_for(n, scan_num_agents)) {
        if (use_whole_dense_codec_for(n, scan_num_agents)) {
            dense_codec_mode = 3;
        } else if (use_grouped_dense_codec_for(n, scan_num_agents)) {
            dense_codec_mode = 2;
        } else {
            dense_codec_mode = 1;
        }
    }
    bool local_prune = use_local_prune_for(n, scan_num_agents);
    int bits_per_msg = max_msg_len * 6;
    if (dense_codec_mode == 1) bits_per_msg = (max_msg_len / 2) * 13;
    if (dense_codec_mode == 2) bits_per_msg = dense_bits_per_message(max_msg_len);
    if (dense_codec_mode == 3) bits_per_msg = whole_base95_capacity(max_msg_len);
    if (dense_codec_mode == 4) bits_per_msg = whole_base95_capacity(max_msg_len);
    if (dense_codec_mode == 5) bits_per_msg = whole_base95_capacity(max_msg_len);
    bits_per_msg = max(1, bits_per_msg);
    bool sparse_codec = dense_codec_mode == 4 || dense_codec_mode == 5;
    int chunk_payload_bits = sparse_codec ?
        skip_inferred_payload_for(n, scan_num_agents) : bits_per_msg;
    int edge_order_style = choose_edge_order_style(n, scan_num_agents);

    auto message_count = [&](int bits) -> int {
        return bits == 0 ? 0 : (bits + bits_per_msg - 1) / bits_per_msg;
    };

    auto estimate_finish = [&](int active_agents, int q0) {
        if (active_agents == 1) return (long long)total_edges + 1;
        long long rem = total_edges - q0;
        int workers = active_agents - 1;
        int base = (int)(rem / workers);
        int extra = (int)(rem % workers);
        vector<int> availability;
        availability.reserve(128);
        for (int id = 1; id < active_agents; ++id) {
            int q = base + (id - 1 < extra ? 1 : 0);
            int chunks = message_count(q);
            for (int k = 1; k <= chunks; ++k) {
                int queried = min(q, k * bits_per_msg);
                availability.push_back(queried + k + 1);
            }
        }
        sort(availability.begin(), availability.end());
        long long turn = (long long)q0 + 1;
        for (int ready : availability) {
            if (turn < ready) turn = ready;
            ++turn;
        }
        return turn;
    };

    auto best_q0_for = [&](int active_agents) {
        int lo = 0, hi = (int)total_edges;
        while (hi - lo > 512) {
            int m1 = lo + (hi - lo) / 3;
            int m2 = hi - (hi - lo) / 3;
            if (estimate_finish(active_agents, m1) <= estimate_finish(active_agents, m2)) {
                hi = m2;
            } else {
                lo = m1;
            }
        }
        long long best_finish = LLONG_MAX;
        int best_q0 = 0;
        for (int q0 = lo; q0 <= hi; ++q0) {
            long long finish = estimate_finish(active_agents, q0);
            if (finish < best_finish) {
                best_finish = finish;
                best_q0 = q0;
            }
        }
        return pair<long long, int>{best_finish, best_q0};
    };

    int active_agents = scan_num_agents;
    long long active_finish = LLONG_MAX;
    for (int k = 6; k <= scan_num_agents; ++k) {
        auto [finish, q0] = best_q0_for(k);
        (void)q0;
        if (finish < active_finish || (finish == active_finish && k > active_agents)) {
            active_finish = finish;
            active_agents = k;
        }
    }
    if (scan_agent_id >= active_agents) {
        cout << "halt" << '\n' << flush;
        return 0;
    }

    auto make_counts = [&]() {
        vector<int> best(active_agents, 0);
        if (active_agents == 1) {
            best[0] = (int)total_edges;
            return best;
        }
        auto [best_finish, q0] = best_q0_for(active_agents);
        (void)best_finish;
        long long rem = total_edges - q0;
        int workers = active_agents - 1;
        int base = (int)(rem / workers);
        int extra = (int)(rem % workers);
        best[0] = q0;
        for (int id = 1; id < active_agents; ++id) {
            best[id] = base + (id - 1 < extra ? 1 : 0);
        }
        return best;
    };

    vector<int> counts = make_counts();
    vector<long long> starts(active_agents + 1, 0);
    for (int id = 0; id < active_agents; ++id) {
        starts[id + 1] = starts[id] + counts[id];
    }

    vector<int> edge_from;
    vector<int> edge_to;
    vector<char> edge_dir;
    edge_from.reserve((int)total_edges);
    edge_to.reserve((int)total_edges);
    edge_dir.reserve((int)total_edges);
    for (int i = 0; i < rooms; ++i) {
        for (int j = 0; j < rooms; ++j) {
            int id = i * rooms + j;
            if (i + 1 < rooms) {
                edge_from.push_back(id);
                edge_to.push_back(id + rooms);
                edge_dir.push_back('D');
            }
            if (j + 1 < rooms) {
                edge_from.push_back(id);
                edge_to.push_back(id + 1);
                edge_dir.push_back('R');
            }
        }
    }
    vector<int> edge_order((int)total_edges);
    iota(edge_order.begin(), edge_order.end(), 0);
    auto edge_key = [&](int idx) {
        int ar = edge_from[idx] / rooms, ac = edge_from[idx] % rooms;
        int br = edge_to[idx] / rooms, bc = edge_to[idx] % rooms;
        int diag_min = min(abs(ar - ac), abs(br - bc));
        int diag_max = max(abs(ar - ac), abs(br - bc));
        int anti_mid = min(abs(ar + ac - (rooms - 1)), abs(br + bc - (rooms - 1)));
        int anti_end = min(ar + ac, 2 * (rooms - 1) - (br + bc));
        int sum_min = min(ar + ac, br + bc);
        if (edge_order_style == 2) {
            return array<int, 5>{diag_max, anti_end, idx, 0, 0};
        }
        if (edge_order_style == 3) {
            return array<int, 5>{diag_min, sum_min, idx, 0, 0};
        }
        if (edge_order_style == 12) {
            int tile = 8;
            int tile_count = (rooms + tile - 1) / tile;
            int atr = ar / tile, atc = ac / tile;
            int btr = br / tile, btc = bc / tile;
            int tile_diag = min(abs(atr - atc), abs(btr - btc));
            int tile_anti = min(abs(atr + atc - (tile_count - 1)),
                                abs(btr + btc - (tile_count - 1)));
            return array<int, 5>{tile_diag, tile_anti, diag_min, anti_mid, idx};
        }
        return array<int, 5>{diag_min, anti_mid, idx, 0, 0};
    };
    sort(edge_order.begin(), edge_order.end(), [&](int a, int b) {
        return edge_key(a) < edge_key(b);
    });
    vector<int> old_from = edge_from, old_to = edge_to;
    vector<char> old_dir = edge_dir;
    for (int i = 0; i < (int)total_edges; ++i) {
        edge_from[i] = old_from[edge_order[i]];
        edge_to[i] = old_to[edge_order[i]];
        edge_dir[i] = old_dir[edge_order[i]];
    }

    vector<unsigned char> my_bits;
    my_bits.reserve(counts[scan_agent_id]);
    vector<unsigned char> chunk_bits;
    chunk_bits.reserve(chunk_payload_bits);

    vector<int> local_parent(rooms * rooms), local_rank(rooms * rooms, 0);
    iota(local_parent.begin(), local_parent.end(), 0);
    auto local_find = [&](int x) {
        int root = x;
        while (local_parent[root] != root) root = local_parent[root];
        while (local_parent[x] != x) {
            int next = local_parent[x];
            local_parent[x] = root;
            x = next;
        }
        return root;
    };
    auto local_unite = [&](int a, int b) {
        int ra = local_find(a), rb = local_find(b);
        if (ra == rb) return;
        if (local_rank[ra] < local_rank[rb]) swap(ra, rb);
        local_parent[rb] = ra;
        if (local_rank[ra] == local_rank[rb]) ++local_rank[ra];
    };

    for (long long edge_idx = starts[scan_agent_id]; edge_idx < starts[scan_agent_id + 1]; ++edge_idx) {
        int from = edge_from[(int)edge_idx];
        int to = edge_to[(int)edge_idx];
        int r = from / rooms;
        int c = from % rooms;
        int qr = 2 * r + 1 + (edge_dir[(int)edge_idx] == 'D' ? 1 : 0);
        int qc = 2 * c + 1 + (edge_dir[(int)edge_idx] == 'R' ? 1 : 0);
        bool inferred_closed = local_prune && local_find(from) == local_find(to);
        unsigned char bit = 0;
        if (!inferred_closed) {
            bit = query_cell(qr, qc) ? 1 : 0;
            if (local_prune && bit) local_unite(from, to);
        }
        my_bits.push_back(bit);
        if (scan_agent_id != 0) {
            if (!sparse_codec || !inferred_closed) {
                chunk_bits.push_back(bit);
            }
            if ((int)chunk_bits.size() == chunk_payload_bits) {
                send_msg(scan_offset, encode_bits(chunk_bits, dense_codec_mode));
                chunk_bits.clear();
            }
        }
    }

    if (scan_agent_id != 0) {
        if (!chunk_bits.empty()) {
            send_msg(scan_offset, encode_bits(chunk_bits, dense_codec_mode));
        }
        cout << "halt" << '\n' << flush;
        return 0;
    }

    int start = 0, goal = rooms * rooms - 1;
    vector<vector<pair<int, char>>> graph(rooms * rooms);
    vector<int> dsu_parent(rooms * rooms), dsu_rank(rooms * rooms, 0);
    iota(dsu_parent.begin(), dsu_parent.end(), 0);

    auto dsu_find = [&](int x) {
        int root = x;
        while (dsu_parent[root] != root) root = dsu_parent[root];
        while (dsu_parent[x] != x) {
            int next = dsu_parent[x];
            dsu_parent[x] = root;
            x = next;
        }
        return root;
    };

    auto dsu_unite = [&](int a, int b) {
        int ra = dsu_find(a), rb = dsu_find(b);
        if (ra == rb) return;
        if (dsu_rank[ra] < dsu_rank[rb]) swap(ra, rb);
        dsu_parent[rb] = ra;
        if (dsu_rank[ra] == dsu_rank[rb]) ++dsu_rank[ra];
    };

    auto claim_if_connected = [&]() {
        if (dsu_find(start) != dsu_find(goal)) return;
        vector<int> parent(rooms * rooms, -1);
        vector<char> parent_dir(rooms * rooms, 0);
        queue<int> q;
        parent[start] = start;
        q.push(start);
        while (!q.empty() && parent[goal] == -1) {
            int v = q.front();
            q.pop();
            for (auto [to, dir] : graph[v]) {
                if (parent[to] == -1) {
                    parent[to] = v;
                    parent_dir[to] = dir;
                    q.push(to);
                }
            }
        }
        if (parent[goal] == -1) return;

        string room_path;
        for (int v = goal; v != start; v = parent[v]) {
            room_path.push_back(parent_dir[v]);
        }
        reverse(room_path.begin(), room_path.end());

        string moves;
        moves.reserve(room_path.size() * 2);
        for (char dir : room_path) {
            moves.push_back(dir);
            moves.push_back(dir);
        }
        cout << "! " << moves << '\n' << flush;
        exit(0);
    };

    vector<int> processed(active_agents, 0);
    auto process_bit = [&](int owner_id, unsigned char bit) {
        int offset = processed[owner_id]++;
        if (!bit) return;
        int edge = (int)starts[owner_id] + offset;
        int a = edge_from[edge], b = edge_to[edge];
        char dir = edge_dir[edge];
        graph[a].push_back({b, dir});
        graph[b].push_back({a, opposite_dir(dir)});
        dsu_unite(a, b);
    };

    vector<vector<int>> recv_parent;
    vector<vector<unsigned char>> recv_rank;
    if (sparse_codec) {
        recv_parent.assign(active_agents, {});
        recv_rank.assign(active_agents, {});
        for (int id = 1; id < active_agents; ++id) {
            recv_parent[id].resize(rooms * rooms);
            recv_rank[id].assign(rooms * rooms, 0);
            iota(recv_parent[id].begin(), recv_parent[id].end(), 0);
        }
    }

    auto recv_find = [&](int owner_id, int x) {
        vector<int> &parent = recv_parent[owner_id];
        int root = x;
        while (parent[root] != root) root = parent[root];
        while (parent[x] != x) {
            int next = parent[x];
            parent[x] = root;
            x = next;
        }
        return root;
    };

    auto recv_unite = [&](int owner_id, int a, int b) {
        int ra = recv_find(owner_id, a), rb = recv_find(owner_id, b);
        if (ra == rb) return;
        vector<int> &parent = recv_parent[owner_id];
        vector<unsigned char> &rank = recv_rank[owner_id];
        if (rank[ra] < rank[rb]) swap(ra, rb);
        parent[rb] = ra;
        if (rank[ra] == rank[rb]) ++rank[ra];
    };

    auto process_sparse_chunk = [&](int owner_id, const vector<unsigned char> &bits) {
        int bit_pos = 0;
        while (processed[owner_id] < counts[owner_id]) {
            int edge = (int)starts[owner_id] + processed[owner_id];
            int a = edge_from[edge], b = edge_to[edge];
            if (recv_find(owner_id, a) == recv_find(owner_id, b)) {
                process_bit(owner_id, 0);
                continue;
            }
            if (bit_pos >= (int)bits.size()) break;
            unsigned char bit = bits[bit_pos++];
            process_bit(owner_id, bit);
            if (bit) recv_unite(owner_id, a, b);
        }
    };

    for (unsigned char bit : my_bits) {
        process_bit(0, bit);
    }
    claim_if_connected();

    if (sparse_codec) {
        vector<unsigned char> done(active_agents, 0);
        int remaining_workers = active_agents - 1;
        while (remaining_workers > 0) {
            auto [sender, body] = recv_any();
            if (sender < 0) continue;
            int local_sender = sender - scan_offset;
            if (local_sender >= 1 && local_sender < active_agents && !done[local_sender]) {
                vector<unsigned char> bits = decode_bits(body, chunk_payload_bits, dense_codec_mode);
                process_sparse_chunk(local_sender, bits);
                claim_if_connected();
                if (processed[local_sender] >= counts[local_sender]) {
                    done[local_sender] = 1;
                    --remaining_workers;
                }
            }
        }
    } else {
        int remaining_messages = 0;
        for (int id = 1; id < active_agents; ++id) {
            remaining_messages += message_count(counts[id]);
        }

        while (remaining_messages > 0) {
            auto [sender, body] = recv_any();
            if (sender < 0) continue;
            int local_sender = sender - scan_offset;
            if (local_sender >= 1 && local_sender < active_agents) {
                int need = min(bits_per_msg, counts[local_sender] - processed[local_sender]);
                vector<unsigned char> bits = decode_bits(body, need, dense_codec_mode);
                for (unsigned char bit : bits) {
                    process_bit(local_sender, bit);
                }
                claim_if_connected();
                --remaining_messages;
            }
        }
    }
    claim_if_connected();
    cout << "halt" << '\n' << flush;
    return 0;
}