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

static const string ALPH = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz-_";

struct Edge {
    int u, v;
    int qr, qc; // 1-indexed maze cell to query
    char dir;   // direction from u to v in room graph, D or R
};

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

string ask(const string &s) {
    cout << s << '\n' << flush;
    string r;
    if (!getline(cin, r)) exit(0);
    return r;
}

bool query_cell(int r, int c) {
    string rep = ask("? " + to_string(r) + " " + to_string(c));
    return !rep.empty() && rep[0] == '1';
}

[[noreturn]] void halt_now() {
    cout << "halt\n" << flush;
    exit(0);
}

[[noreturn]] void claim_path(const string &path) {
    if (path.empty()) cout << "!\n" << flush;
    else cout << "! " << path << '\n' << flush;
    exit(0);
}

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

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

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

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

string encode_id3(int x) {
    string s;
    s.push_back(ALPH[x & 63]);
    s.push_back(ALPH[(x >> 6) & 63]);
    s.push_back(ALPH[(x >> 12) & 63]);
    return s;
}

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

// Query order for the global scanner: expand from the main diagonal.  The old
// row-major order almost forces the bottom-right part of the answer to be found last.
vector<int> build_priority_order(int m, const vector<Edge> &edges) {
    vector<int> order(edges.size());
    iota(order.begin(), order.end(), 0);
    const int center_sum = 2 * (m - 1); // in doubled room-midpoint coordinates
    auto key = [&](int eid) {
        const Edge &e = edges[eid];
        int i = e.u / m, j = e.u % m;
        int x2, y2;
        if (e.dir == 'D') { x2 = 2 * i + 1; y2 = 2 * j; }
        else { x2 = 2 * i; y2 = 2 * j + 1; }
        int diag = abs(x2 - y2);
        int sum = x2 + y2;
        int center = abs(sum - center_sum);
        return tuple<int,int,int,int,int>(diag, center, sum, x2, y2);
    };
    sort(order.begin(), order.end(), [&](int a, int b) { return key(a) < key(b); });
    return order;
}

string answer_from_known_adj(int m, const vector<vector<pair<int,char>>> &adj) {
    const int V = m * m;
    vector<int> par(V, -2);
    vector<char> pdir(V, 0);
    queue<int> q;
    par[0] = -1;
    q.push(0);
    while (!q.empty() && par[V - 1] == -2) {
        int u = q.front(); q.pop();
        for (auto [v, d] : adj[u]) {
            if (par[v] != -2) continue;
            par[v] = u;
            pdir[v] = d;
            q.push(v);
            if (v == V - 1) break;
        }
    }
    if (par[V - 1] == -2) return string();
    string room_path;
    for (int cur = V - 1; cur != 0; cur = par[cur]) room_path.push_back(pdir[cur]);
    reverse(room_path.begin(), room_path.end());
    string ans;
    ans.reserve(room_path.size() * 2);
    for (char d : room_path) { ans.push_back(d); ans.push_back(d); }
    return ans;
}

void add_known_open_edge(int eid, const vector<Edge> &edges, DSU &dsu,
                         vector<vector<pair<int,char>>> &adj) {
    const Edge &e = edges[eid];
    if (dsu.unite(e.u, e.v)) {
        adj[e.u].push_back({e.v, e.dir});
        adj[e.v].push_back({e.u, opposite_dir(e.dir)});
    }
}


// ---------- Mode 0: classic full scan fallback (good when E / agents is already tiny) ----------

long long classic_owned_count(int E, int owner, int agents) {
    if (owner < 0 || owner >= agents || owner >= E) return 0;
    return (E - 1LL - owner) / agents + 1;
}

void classic_full_scan(int m, int NUM_AGENTS, int AGENT_ID, int MAX_MSG_LEN,
                       const vector<Edge> &edges) {
    const int E = (int)edges.size();
    const int V = m * m;
    vector<unsigned char> my_bits;
    my_bits.reserve((E + NUM_AGENTS - 1) / NUM_AGENTS + 1);
    vector<signed char> open;
    if (AGENT_ID == 0) open.assign(E, -1);

    for (int eid = AGENT_ID; eid < E; eid += NUM_AGENTS) {
        bool ok = query_cell(edges[eid].qr, edges[eid].qc);
        if (AGENT_ID == 0) open[eid] = ok ? 1 : 0;
        else my_bits.push_back(ok ? 1 : 0);
    }

    if (AGENT_ID != 0) {
        string enc = encode_bits(my_bits);
        int chunk = max(1, MAX_MSG_LEN);
        for (int pos = 0; pos < (int)enc.size(); pos += chunk) {
            ask("> 0 " + enc.substr(pos, chunk));
        }
        halt_now();
    }

    vector<int> expected(NUM_AGENTS, 0), got(NUM_AGENTS, 0);
    vector<string> received(NUM_AGENTS);
    int need = 0, total = 0;
    int chunk = max(1, MAX_MSG_LEN);
    for (int s = 1; s < NUM_AGENTS; ++s) {
        long long bits = classic_owned_count(E, s, NUM_AGENTS);
        long long chars = (bits + 5) / 6;
        expected[s] = (int)((chars + chunk - 1) / chunk);
        need += expected[s];
        received[s].reserve((size_t)chars);
    }
    while (total < need) {
        string rep = ask("< ?");
        if (rep == "- -") continue;
        size_t sp = rep.find(' ');
        if (sp == string::npos) continue;
        int sender = -1;
        try { sender = stoi(rep.substr(0, sp)); } catch (...) { continue; }
        if (sender <= 0 || sender >= NUM_AGENTS || got[sender] >= expected[sender]) continue;
        received[sender] += rep.substr(sp + 1);
        ++got[sender];
        ++total;
    }

    for (int s = 1; s < NUM_AGENTS; ++s) {
        long long bit_count = classic_owned_count(E, s, NUM_AGENTS);
        long long bit_idx = 0;
        for (char ch : received[s]) {
            int val = enc_val(ch);
            for (int b = 0; b < 6 && bit_idx < bit_count; ++b, ++bit_idx) {
                int eid = s + (int)bit_idx * NUM_AGENTS;
                if (eid < E) open[eid] = ((val >> b) & 1) ? 1 : 0;
            }
        }
    }

    vector<vector<pair<int,char>>> adj(V);
    for (int eid = 0; eid < E; ++eid) {
        if (open[eid] != 1) continue;
        const Edge &e = edges[eid];
        adj[e.u].push_back({e.v, e.dir});
        adj[e.v].push_back({e.u, opposite_dir(e.dir)});
    }
    string ans = answer_from_known_adj(m, adj);
    if (ans.empty() && V != 1) halt_now();
    claim_path(ans);
}

// ---------- Mode 1: diagonal-priority distributed scan with streaming ----------

long long owned_count_in_scan(int E, int scanner_index, int scanners) {
    // scanner_index is 0..scanners-1, position in priority order is scanner_index + k*scanners.
    if (scanner_index < 0 || scanner_index >= scanners || scanner_index >= E) return 0;
    return (E - 1LL - scanner_index) / scanners + 1;
}

void scan_worker(int N, int AGENT_ID, int NUM_AGENTS, int MAX_MSG_LEN,
                 const vector<Edge> &edges, const vector<int> &order) {
    int scanners = NUM_AGENTS - 1;
    int sid = AGENT_ID - 1;
    int max_bits = max(1, min(384, 6 * max(1, MAX_MSG_LEN)));
    vector<unsigned char> bits;
    bits.reserve(max_bits);

    for (int pos = sid; pos < (int)order.size(); pos += scanners) {
        int eid = order[pos];
        bool ok = query_cell(edges[eid].qr, edges[eid].qc);
        bits.push_back(ok ? 1 : 0);
        if ((int)bits.size() >= max_bits) {
            string body = encode_bits(bits);
            ask("> 0 " + body);
            bits.clear();
        }
    }
    if (!bits.empty()) {
        string body = encode_bits(bits);
        ask("> 0 " + body);
    }
    halt_now();
}

void scan_coordinator(int m, int NUM_AGENTS, int MAX_MSG_LEN,
                      const vector<Edge> &edges, const vector<int> &order) {
    const int E = (int)edges.size();
    const int V = m * m;
    int scanners = NUM_AGENTS - 1;
    int max_bits = max(1, min(384, 6 * max(1, MAX_MSG_LEN)));

    DSU dsu(V);
    vector<vector<pair<int,char>>> adj(V);
    vector<long long> processed(NUM_AGENTS, 0), owned(NUM_AGENTS, 0);
    long long total_owned = 0, total_processed = 0;
    for (int s = 1; s < NUM_AGENTS; ++s) {
        owned[s] = owned_count_in_scan(E, s - 1, scanners);
        total_owned += owned[s];
    }

    while (true) {
        if (dsu.find(0) == dsu.find(V - 1)) {
            string ans = answer_from_known_adj(m, adj);
            claim_path(ans);
        }
        if (total_processed >= total_owned) {
            // Should already be connected after all scan data.  Avoid an invalid claim on impossible bugs.
            halt_now();
        }

        string rep = ask("< ?");
        if (rep == "- -") continue;
        size_t sp = rep.find(' ');
        if (sp == string::npos) continue;
        int sender = -1;
        try { sender = stoi(rep.substr(0, sp)); } catch (...) { continue; }
        if (sender <= 0 || sender >= NUM_AGENTS) continue;
        string body = rep.substr(sp + 1);

        for (char ch : body) {
            int val = enc_val(ch);
            for (int b = 0; b < 6 && processed[sender] < owned[sender]; ++b) {
                int pos = (sender - 1) + (int)processed[sender] * scanners;
                ++processed[sender];
                ++total_processed;
                if (pos >= E) continue;
                if ((val >> b) & 1) add_known_open_edge(order[pos], edges, dsu, adj);
            }
        }
    }
}

// ---------- Mode 2: low-agent bidirectional DFS portfolio + open-edge streaming ----------

struct DFSExplorer {
    int m, V, E, root, target, strategy;
    const vector<Edge> *edges;
    vector<array<pair<int,int>,4>> nbr; // (to, edge id), at most 4 per room
    vector<unsigned char> deg, it;
    vector<int> parent;
    vector<char> pdir;
    vector<signed char> known; // -1 unknown, 0 wall, 1 open, local to this explorer
    vector<int> st;

    DFSExplorer(int m_, int root_, int target_, int strategy_, const vector<Edge> &edges_)
        : m(m_), V(m_ * m_), E((int)edges_.size()), root(root_), target(target_),
          strategy(strategy_), edges(&edges_) {
        nbr.resize(V);
        deg.assign(V, 0);
        it.assign(V, 0);
        parent.assign(V, -2);
        pdir.assign(V, 0);
        known.assign(E, -1);
        parent[root] = -1;
        st.push_back(root);
        build_ordered_neighbours();
    }

    int manhattan_to_target(int v) const {
        int i = v / m, j = v % m;
        int ti = target / m, tj = target % m;
        return abs(ti - i) + abs(tj - j);
    }

    char dir_from_to(int u, int v, int eid) const {
        const Edge &e = (*edges)[eid];
        if (e.u == u && e.v == v) return e.dir;
        return opposite_dir(e.dir);
    }

    void build_ordered_neighbours() {
        vector<vector<pair<int,int>>> tmp(V);
        for (int eid = 0; eid < E; ++eid) {
            const Edge &e = (*edges)[eid];
            tmp[e.u].push_back({e.v, eid});
            tmp[e.v].push_back({e.u, eid});
        }
        for (int u = 0; u < V; ++u) {
            auto &a = tmp[u];
            int strat = strategy % 6;
            auto coord = [&](int v) { return pair<int,int>(v / m, v % m); };
            if (strat == 0) {
                sort(a.begin(), a.end(), [&](auto x, auto y) {
                    int hx = manhattan_to_target(x.first), hy = manhattan_to_target(y.first);
                    if (hx != hy) return hx < hy;
                    return x.first < y.first;
                });
            } else if (strat == 1) {
                sort(a.begin(), a.end(), [&](auto x, auto y) {
                    auto [xi, xj] = coord(x.first);
                    auto [yi, yj] = coord(y.first);
                    int ti = target / m, tj = target % m;
                    int bx = abs(xi - ti) - abs(xj - tj);
                    int by = abs(yi - ti) - abs(yj - tj);
                    if (bx != by) return bx < by;
                    return manhattan_to_target(x.first) < manhattan_to_target(y.first);
                });
            } else if (strat == 2) {
                sort(a.begin(), a.end(), [&](auto x, auto y) {
                    auto [xi, xj] = coord(x.first);
                    auto [yi, yj] = coord(y.first);
                    int dx = abs(xi - xj), dy = abs(yi - yj);
                    if (dx != dy) return dx < dy;
                    return manhattan_to_target(x.first) < manhattan_to_target(y.first);
                });
            } else if (strat == 3) {
                sort(a.begin(), a.end(), [&](auto x, auto y) {
                    int hx = manhattan_to_target(x.first), hy = manhattan_to_target(y.first);
                    if (hx != hy) return hx > hy;
                    return x.first < y.first;
                });
            } else {
                // Deterministic pseudo-random diversity.  No runtime randomness needed.
                sort(a.begin(), a.end(), [&](auto x, auto y) {
                    uint32_t ax = (uint32_t)(x.second * 1103515245u + (u + 1) * 12345u + strategy * 2654435761u);
                    uint32_t ay = (uint32_t)(y.second * 1103515245u + (u + 1) * 12345u + strategy * 2654435761u);
                    return ax < ay;
                });
            }
            deg[u] = (unsigned char)a.size();
            for (int k = 0; k < (int)a.size(); ++k) nbr[u][k] = a[k];
        }
    }

    string current_path_answer() const {
        // We are at target. parent[] describes root -> target.
        string dirs;
        for (int cur = target; cur != root; cur = parent[cur]) dirs.push_back(pdir[cur]);
        reverse(dirs.begin(), dirs.end());
        if (root != 0) {
            // The stored path is goal -> start; invert it to start -> goal.
            string inv;
            inv.reserve(dirs.size());
            for (int i = (int)dirs.size() - 1; i >= 0; --i) inv.push_back(opposite_dir(dirs[i]));
            dirs.swap(inv);
        }
        string ans;
        ans.reserve(dirs.size() * 2);
        for (char d : dirs) { ans.push_back(d); ans.push_back(d); }
        return ans;
    }

    // Returns queried edge id, -2 if target reached, or -1 if the search is exhausted.
    int next_query_or_claim() {
        while (!st.empty()) {
            int u = st.back();
            if (u == target) return -2;
            while (it[u] < deg[u]) {
                auto [v, eid] = nbr[u][it[u]++];
                if (parent[u] == v || parent[v] != -2) continue;
                if (known[eid] != -1) {
                    if (known[eid] == 1) {
                        parent[v] = u;
                        pdir[v] = dir_from_to(u, v, eid);
                        st.push_back(v);
                    }
                    continue;
                }
                return eid;
            }
            st.pop_back();
        }
        return -1;
    }

    void record_result(int eid, bool open) {
        known[eid] = open ? 1 : 0;
        if (!open || st.empty()) return;
        int u = st.back();
        const Edge &e = (*edges)[eid];
        int v = (e.u == u ? e.v : e.u);
        if (parent[v] == -2) {
            parent[v] = u;
            pdir[v] = dir_from_to(u, v, eid);
            st.push_back(v);
        }
    }
};

void dfs_flush(string &buf) {
    if (buf.empty()) return;
    ask("> 0 E" + buf);
    buf.clear();
}

void dfs_worker(int m, int AGENT_ID, int NUM_AGENTS, int MAX_MSG_LEN, const vector<Edge> &edges) {
    const int V = m * m;
    int wid = AGENT_ID - 1;
    int root = (wid % 2 == 0) ? 0 : (V - 1);
    int target = (root == 0) ? (V - 1) : 0;
    int strategy = wid / 2;
    DFSExplorer ex(m, root, target, strategy, edges);

    int max_ids_by_len = max(1, (MAX_MSG_LEN - 1) / 3);
    int flush_ids = max(1, min(48, max_ids_by_len));
    string buf;
    buf.reserve(3 * flush_ids);

    while (true) {
        if ((int)buf.size() / 3 >= flush_ids) dfs_flush(buf);
        int eid = ex.next_query_or_claim();
        if (eid == -2) {
            // The local DFS has already verified every corridor on this chain.
            // Claiming directly saves the final open-edge upload to agent 0.
            claim_path(ex.current_path_answer());
        }
        if (eid < 0) {
            dfs_flush(buf);
            halt_now();
        }
        bool ok = query_cell(edges[eid].qr, edges[eid].qc);
        ex.record_result(eid, ok);
        if (ok) {
            if ((int)buf.size() + 3 <= 3 * flush_ids) buf += encode_id3(eid);
            else { dfs_flush(buf); buf += encode_id3(eid); }
        }
    }
}

void dfs_coordinator(int m, int NUM_AGENTS, const vector<Edge> &edges) {
    const int V = m * m;
    DSU dsu(V);
    vector<vector<pair<int,char>>> adj(V);
    while (true) {
        if (dsu.find(0) == dsu.find(V - 1)) {
            string ans = answer_from_known_adj(m, adj);
            claim_path(ans);
        }
        string rep = ask("< ?");
        if (rep == "- -") continue;
        size_t sp = rep.find(' ');
        if (sp == string::npos) continue;
        string body = rep.substr(sp + 1);
        if (body.empty() || body[0] != 'E') continue;
        for (int pos = 1; pos + 2 < (int)body.size(); pos += 3) {
            int eid = decode_id3(body, pos);
            if (0 <= eid && eid < (int)edges.size()) add_known_open_edge(eid, edges, dsu, adj);
        }
    }
}



// ---------- Mode 3: batched diagonal scan with hierarchical message reduction ----------

int h_encoded_len(int bits) {
    return (bits + 5) / 6;
}

vector<string> h_split_chunks(const string &s, int max_len) {
    vector<string> out;
    if (max_len <= 0) return out;
    for (int p = 0; p < (int)s.size(); p += max_len) out.push_back(s.substr(p, max_len));
    return out;
}

void h_decode_bits_and_add(const string &body, int bit_count, const function<void(int)> &on_one) {
    int bit_idx = 0;
    for (char ch : body) {
        int val = enc_val(ch);
        for (int b = 0; b < 6 && bit_idx < bit_count; ++b, ++bit_idx) {
            if ((val >> b) & 1) on_one(bit_idx);
        }
        if (bit_idx >= bit_count) break;
    }
}

long long h_count_positions(int prev, int cur, int who, int agents) {
    int first = prev + who;
    if (first >= cur) return 0;
    return (cur - 1LL - first) / agents + 1;
}

int h_finish_receiving_time(int start_turn, vector<int> send_times) {
    if (send_times.empty()) return start_turn - 1;
    sort(send_times.begin(), send_times.end());
    int got = 0, n = (int)send_times.size();
    int t = start_turn;
    while (got < n) {
        int available = (int)(upper_bound(send_times.begin(), send_times.end(), t - 1) - send_times.begin()) - got;
        if (available > 0) {
            ++got;
            ++t;
        } else {
            t = max(t, send_times[got] + 1);
        }
    }
    return t - 1;
}

struct HPlan {
    int prev = 0, cur = 0, A = 0, max_len = 256, G = 1, phase_turns = 0;
    vector<int> qcnt, enclen, chunks;
    vector<int> leader, gstart, gend;
    vector<int> expected_direct; // chunks sent directly to agent 0 by sender
    vector<int> expected_agg;    // aggregate chunks sent to agent 0 by group leader
    vector<int> expected_worker; // chunks group leader receives from its workers
};

HPlan h_make_plan_for_group(int prev, int cur, int A, int max_len, int G) {
    HPlan bp;
    bp.prev = prev; bp.cur = cur; bp.A = A; bp.max_len = max_len; bp.G = G;
    bp.qcnt.assign(A, 0); bp.enclen.assign(A, 0); bp.chunks.assign(A, 0);
    bp.leader.assign(A, 0); bp.gstart.assign(A, 0); bp.gend.assign(A, 0);
    bp.expected_direct.assign(A, 0); bp.expected_agg.assign(A, 0); bp.expected_worker.assign(A, 0);

    for (int s = 0; s < A; ++s) {
        bp.qcnt[s] = (int)h_count_positions(prev, cur, s, A);
        bp.enclen[s] = h_encoded_len(bp.qcnt[s]);
        bp.chunks[s] = bp.enclen[s] == 0 ? 0 : (bp.enclen[s] + max_len - 1) / max_len;
    }
    for (int st = 0; st < A; st += G) {
        int en = min(A, st + G);
        for (int s = st; s < en; ++s) {
            bp.leader[s] = st;
            bp.gstart[s] = st;
            bp.gend[s] = en;
        }
    }

    vector<int> root_send_times;
    int phase = 0;
    for (int s = 0; s < A; ++s) phase = max(phase, bp.qcnt[s]);

    if (G == 1) {
        for (int s = 1; s < A; ++s) {
            bp.expected_direct[s] = bp.chunks[s];
            for (int k = 1; k <= bp.chunks[s]; ++k) root_send_times.push_back(bp.qcnt[s] + k);
            phase = max(phase, bp.qcnt[s] + bp.chunks[s]);
        }
    } else {
        int root_end = min(A, G);
        for (int s = 1; s < root_end; ++s) {
            bp.expected_direct[s] = bp.chunks[s];
            for (int k = 1; k <= bp.chunks[s]; ++k) root_send_times.push_back(bp.qcnt[s] + k);
            phase = max(phase, bp.qcnt[s] + bp.chunks[s]);
        }
        for (int st = G; st < A; st += G) {
            int en = min(A, st + G);
            int L = st;
            vector<int> to_leader;
            for (int s = st + 1; s < en; ++s) {
                bp.expected_worker[L] += bp.chunks[s];
                for (int k = 1; k <= bp.chunks[s]; ++k) to_leader.push_back(bp.qcnt[s] + k);
                phase = max(phase, bp.qcnt[s] + bp.chunks[s]);
            }
            int recv_done = h_finish_receiving_time(bp.qcnt[L] + 1, to_leader);
            int agg_len = 0;
            for (int s = st; s < en; ++s) agg_len += bp.enclen[s];
            int agg_chunks = (agg_len + max_len - 1) / max_len;
            bp.expected_agg[L] = agg_chunks;
            for (int k = 1; k <= agg_chunks; ++k) root_send_times.push_back(recv_done + k);
            phase = max(phase, recv_done + agg_chunks);
        }
    }

    int root_done = h_finish_receiving_time(bp.qcnt[0] + 1, root_send_times);
    phase = max(phase, root_done);
    bp.phase_turns = phase;
    return bp;
}

HPlan h_choose_plan(int prev, int cur, int A, int max_len) {
    HPlan best = h_make_plan_for_group(prev, cur, A, max_len, 1);
    for (int G = 2; G <= A; ++G) {
        HPlan cand = h_make_plan_for_group(prev, cur, A, max_len, G);
        if (cand.phase_turns < best.phase_turns || (cand.phase_turns == best.phase_turns && cand.G < best.G)) best = std::move(cand);
    }
    return best;
}

vector<int> h_build_batches(int E, int A) {
    double per = (double)E / max(1, A);
    vector<double> f;
    if (per < 220.0) {
        f = {0.55, 0.65, 0.75, 0.85, 0.93, 1.0};
    } else if (per < 700.0) {
        f = {0.50, 0.60, 0.70, 0.80, 0.90, 1.0};
    } else if (per < 2200.0) {
        f = {0.45, 0.55, 0.65, 0.75, 0.85, 0.93, 1.0};
    } else if (per < 8500.0) {
        f = {0.36, 0.44, 0.52, 0.60, 0.68, 0.72, 0.76, 0.80, 0.84, 0.88, 0.92, 0.95, 0.98, 1.0};
    } else {
        f = {0.34, 0.42, 0.50, 0.58, 0.66, 0.70, 0.74, 0.78, 0.82, 0.86, 0.90, 0.94, 0.97, 1.0};
    }
    vector<int> out;
    int last = 0;
    for (double x : f) {
        int cur = (int)ceil(E * x - 1e-12);
        cur = max(0, min(E, cur));
        if (cur > last) { out.push_back(cur); last = cur; }
    }
    if (out.empty() || out.back() != E) out.push_back(E);
    return out;
}

vector<string> h_split_aggregate(const string &agg, int expected) {
    vector<string> parts;
    parts.reserve(expected);
    string cur;
    for (char ch : agg) {
        if (ch == '~') {
            parts.push_back(cur);
            cur.clear();
            if ((int)parts.size() == expected) break;
        } else {
            cur.push_back(ch);
        }
    }
    while ((int)parts.size() < expected) parts.push_back("");
    return parts;
}

void hierarchical_scan_solver(int m, int NUM_AGENTS, int AGENT_ID, int MAX_MSG_LEN,
                              const vector<Edge> &edges, const vector<int> &order) {
    const int E = (int)edges.size();
    const int V = m * m;
    const int A = NUM_AGENTS;
    vector<int> batches = h_build_batches(E, A);

    DSU dsu(V);
    vector<vector<pair<int,char>>> adj;
    if (AGENT_ID == 0) adj.assign(V, {});

    auto add_edge0 = [&](int eid) {
        if (AGENT_ID == 0) add_known_open_edge(eid, edges, dsu, adj);
    };

    auto maybe_claim = [&]() {
        if (AGENT_ID == 0 && dsu.find(0) == dsu.find(V - 1)) {
            string ans = answer_from_known_adj(m, adj);
            claim_path(ans);
        }
    };

    int prev = 0;
    for (int cur : batches) {
        HPlan bp = h_choose_plan(prev, cur, A, MAX_MSG_LEN);
        int used = 0;
        vector<unsigned char> my_bits;
        my_bits.reserve((size_t)bp.qcnt[AGENT_ID]);

        for (int k = 0; k < bp.qcnt[AGENT_ID]; ++k) {
            int pos = prev + AGENT_ID + k * A;
            int eid = order[pos];
            bool ok = query_cell(edges[eid].qr, edges[eid].qc);
            if (AGENT_ID == 0) {
                if (ok) add_known_open_edge(eid, edges, dsu, adj);
            } else {
                my_bits.push_back(ok ? 1 : 0);
            }
            ++used;
        }
        string my_enc;
        if (AGENT_ID != 0) my_enc = encode_bits(my_bits);

        int L = bp.leader[AGENT_ID];
        int st = bp.gstart[AGENT_ID];
        int en = bp.gend[AGENT_ID];
        bool is_leader = (AGENT_ID == L);

        if (AGENT_ID == 0) {
            vector<string> direct(A), aggregate(A);
            vector<int> got_direct(A, 0), got_agg(A, 0);
            while (used < bp.phase_turns) {
                string rep = ask("< ?");
                ++used;
                if (rep == "- -") continue;
                size_t sp = rep.find(' ');
                if (sp == string::npos) continue;
                int sender = -1;
                try { sender = stoi(rep.substr(0, sp)); } catch (...) { sender = -1; }
                if (sender <= 0 || sender >= A) continue;
                string body = rep.substr(sp + 1);
                if (bp.expected_direct[sender] && got_direct[sender] < bp.expected_direct[sender]) {
                    direct[sender] += body;
                    ++got_direct[sender];
                } else if (bp.expected_agg[sender] && got_agg[sender] < bp.expected_agg[sender]) {
                    aggregate[sender] += body;
                    ++got_agg[sender];
                }
            }
            for (int s = 1; s < A; ++s) {
                if (!bp.expected_direct[s]) continue;
                h_decode_bits_and_add(direct[s], bp.qcnt[s], [&](int bit_idx) {
                    int pos = prev + s + bit_idx * A;
                    if (pos < cur) add_known_open_edge(order[pos], edges, dsu, adj);
                });
            }
            for (int leader = 1; leader < A; ++leader) {
                if (!bp.expected_agg[leader]) continue;
                int gst = bp.gstart[leader], gen = bp.gend[leader];
                int off = 0;
                for (int s = gst; s < gen; ++s) {
                    int len = bp.enclen[s];
                    string part;
                    if (off < (int)aggregate[leader].size()) part = aggregate[leader].substr(off, len);
                    off += len;
                    h_decode_bits_and_add(part, bp.qcnt[s], [&](int bit_idx) {
                        int pos = prev + s + bit_idx * A;
                        if (pos < cur) add_known_open_edge(order[pos], edges, dsu, adj);
                    });
                }
            }
            maybe_claim();
        } else if (!is_leader || bp.G == 1 || L == 0) {
            int target = (bp.G == 1 || L == 0) ? 0 : L;
            vector<string> chunks = h_split_chunks(my_enc, MAX_MSG_LEN);
            for (const string &ch : chunks) { ask("> " + to_string(target) + " " + ch); ++used; }
            while (used < bp.phase_turns) { ask("."); ++used; }
        } else {
            vector<string> received(A);
            vector<int> got_chunks(A, 0);
            int need = bp.expected_worker[AGENT_ID], got = 0;
            while (got < need) {
                string rep = ask("< ?");
                ++used;
                if (rep == "- -") continue;
                size_t sp = rep.find(' ');
                if (sp == string::npos) continue;
                int sender = -1;
                try { sender = stoi(rep.substr(0, sp)); } catch (...) { sender = -1; }
                if (sender <= AGENT_ID || sender >= en || bp.leader[sender] != AGENT_ID) continue;
                if (got_chunks[sender] >= bp.chunks[sender]) continue;
                received[sender] += rep.substr(sp + 1);
                ++got_chunks[sender];
                ++got;
            }
            string agg;
            int agg_len = 0;
            for (int s = st; s < en; ++s) agg_len += bp.enclen[s];
            agg.reserve(agg_len);
            for (int s = st; s < en; ++s) {
                if (s == AGENT_ID) agg += my_enc;
                else agg += received[s];
            }
            vector<string> chunks = h_split_chunks(agg, MAX_MSG_LEN);
            for (const string &ch : chunks) { ask("> 0 " + ch); ++used; }
            while (used < bp.phase_turns) { ask("."); ++used; }
        }
        prev = cur;
    }

    if (AGENT_ID == 0) {
        string ans = answer_from_known_adj(m, adj);
        if (!ans.empty() || V == 1) claim_path(ans);
    }
    halt_now();
}



// ---------- Mode 4: low-agent active cooperative best-first / DFS search ----------
// The previous low-agent mode left agent 0 as a passive receiver.  With only 3..6
// agents that wastes 17%..33% of the available queries.  This mode lets agent 0
// search as well, while it periodically drains compressed open-edge reports from
// the other agents.  The coordinator can claim either from its own verified path
// or from the union of all reported open edges.

struct CoopBFExplorer {
    struct Node {
        double pr;
        int serial, u, v, eid;
        bool operator<(const Node &o) const {
            if (pr != o.pr) return pr > o.pr;
            return serial > o.serial;
        }
    };

    int m, V, E, root, target, strategy;
    const vector<Edge> *edges;
    vector<array<pair<int,int>,4>> nbr;
    vector<unsigned char> deg, state;
    vector<signed char> known;
    vector<int> parent, depth;
    vector<char> pdir;
    priority_queue<Node> pq;
    int serial = 0;
    int last_u = -1, last_v = -1, last_eid = -1;
    bool reached = false;

    CoopBFExplorer(int m_, int root_, int target_, int strategy_, const vector<Edge> &edges_)
        : m(m_), V(m_ * m_), E((int)edges_.size()), root(root_), target(target_),
          strategy(strategy_), edges(&edges_) {
        nbr.resize(V);
        deg.assign(V, 0);
        state.assign(V, 0);
        known.assign(E, -1);
        parent.assign(V, -2);
        depth.assign(V, 0);
        pdir.assign(V, 0);

        vector<vector<pair<int,int>>> tmp(V);
        for (int eid = 0; eid < E; ++eid) {
            const Edge &e = (*edges)[eid];
            tmp[e.u].push_back({e.v, eid});
            tmp[e.v].push_back({e.u, eid});
        }
        for (int u = 0; u < V; ++u) {
            deg[u] = (unsigned char)tmp[u].size();
            for (int k = 0; k < (int)tmp[u].size(); ++k) nbr[u][k] = tmp[u][k];
        }
        state[root] = 1;
        parent[root] = -1;
        add_frontier(root);
    }

    char dir_from_to(int u, int v, int eid) const {
        const Edge &e = (*edges)[eid];
        if (e.u == u && e.v == v) return e.dir;
        return opposite_dir(e.dir);
    }

    void params(double &lam, double &alpha, double &beta, double &gamma, double &delta, int &mode, int &noise) const {
        // Tuned on locally generated Kruskal mazes.  The first entries are stable
        // across board sizes; later entries are mainly portfolio diversity.
        static const double P[][6] = {
            {3.0, 16.0, 1.0, 5.0, 0.0, 3.0},
            {3.0,  8.0, 0.2, 1.0, 0.0, 0.0},
            {0.3,  4.0, 1.0, 0.0, 1.0, 3.0},
            {1.0, 16.0, 0.2, 5.0, 3.0, 3.0},
            {3.0,  8.0, 1.0, 1.0, 3.0, 0.0},
            {0.3, 16.0, 0.2, 1.0, 1.0, 3.0},
            {3.0, 16.0, 0.2, 5.0, 3.0, 3.0},
            {1.0,  4.0, 1.5, 0.0, 1.0, 3.0},
            {1.0, 16.0, 0.5, 1.0, 0.0, 0.0},
            {0.1, 16.0, 0.5, 1.0, 0.0, 0.0},
            {0.0,  8.0, 1.0,10.0, 2.0, 0.0},
            {2.0, 12.0, 0.7, 3.0, 1.0, 2.0},
        };
        const int C = (int)(sizeof(P) / sizeof(P[0]));
        int idx = strategy % C;
        lam = P[idx][0]; alpha = P[idx][1]; beta = P[idx][2];
        gamma = P[idx][3]; delta = P[idx][4]; mode = (int)P[idx][5];
        noise = strategy / C;
    }

    double heuristic(int v) const {
        double lam, alpha, beta, gamma, delta;
        int mode, noise;
        params(lam, alpha, beta, gamma, delta, mode, noise);
        int i = v / m, j = v % m;
        int ti = target / m, tj = target % m;
        int ri = root / m, rj = root % m;
        int man = abs(i - ti) + abs(j - tj);
        double M = max(1, m - 1);
        double prog = ((i - ri) + (j - rj)) / (2.0 * M);
        if (prog < 0.0) prog = 0.0;
        if (prog > 1.0) prog = 1.0;
        double diag = abs(i - j);
        double sig = alpha + beta * sqrt(max(0.0, prog * (1.0 - prog))) * M;
        return lam * man + gamma * (diag * diag) / (sig * sig) + delta * diag / sig;
    }

    double priority_value(int u, int v, int eid) const {
        double lam, alpha, beta, gamma, delta;
        int mode, noise;
        params(lam, alpha, beta, gamma, delta, mode, noise);
        double base = heuristic(v);
        int g = depth[u] + 1;
        if (mode == 1) base += g;
        else if (mode == 2) base += 0.3 * g;
        else if (mode == 3) base -= 0.1 * g;
        uint32_t h = (uint32_t)eid * 1103515245u + (uint32_t)(v + 1) * 12345u + (uint32_t)noise * 2654435761u;
        base += (double)(h & 65535u) * (1.0 / 65536.0) * 1e-3;
        return base;
    }

    void add_frontier(int u) {
        for (int k = 0; k < deg[u]; ++k) {
            auto [v, eid] = nbr[u][k];
            if (state[v] || known[eid] != -1) continue;
            pq.push(Node{priority_value(u, v, eid), serial++, u, v, eid});
        }
    }

    int next_query() {
        while (!pq.empty()) {
            Node x = pq.top(); pq.pop();
            if (!state[x.u] || state[x.v] || known[x.eid] != -1) continue;
            last_u = x.u; last_v = x.v; last_eid = x.eid;
            return x.eid;
        }
        return -1;
    }

    void record_result(int eid, bool open) {
        known[eid] = open ? 1 : 0;
        if (!open) return;
        int u = last_u, v = last_v;
        if (eid != last_eid || u < 0 || v < 0 || !state[u] || state[v]) {
            const Edge &e = (*edges)[eid];
            if (state[e.u] && !state[e.v]) { u = e.u; v = e.v; }
            else if (state[e.v] && !state[e.u]) { u = e.v; v = e.u; }
            else return;
        }
        state[v] = 1;
        parent[v] = u;
        depth[v] = depth[u] + 1;
        pdir[v] = dir_from_to(u, v, eid);
        if (v == target) reached = true;
        add_frontier(v);
    }

    string current_path_answer() const {
        if (!reached && parent[target] == -2) return string();
        string dirs;
        for (int cur = target; cur != root; cur = parent[cur]) {
            if (cur < 0 || parent[cur] == -2) return string();
            dirs.push_back(pdir[cur]);
        }
        reverse(dirs.begin(), dirs.end());
        if (root != 0) {
            string inv;
            inv.reserve(dirs.size());
            for (int i = (int)dirs.size() - 1; i >= 0; --i) inv.push_back(opposite_dir(dirs[i]));
            dirs.swap(inv);
        }
        string ans;
        ans.reserve(dirs.size() * 2);
        for (char d : dirs) { ans.push_back(d); ans.push_back(d); }
        return ans;
    }
};

void coop_parse_open_message(const string &body, const vector<Edge> &edges,
                             vector<unsigned char> &seen_open, DSU &dsu,
                             vector<vector<pair<int,char>>> &adj) {
    if (body.empty() || body[0] != 'E') return;
    for (int pos = 1; pos + 2 < (int)body.size(); pos += 3) {
        int eid = decode_id3(body, pos);
        if (eid < 0 || eid >= (int)edges.size()) continue;
        if (seen_open[eid]) continue;
        seen_open[eid] = 1;
        add_known_open_edge(eid, edges, dsu, adj);
    }
}

void coop_worker_flush(string &buf) {
    if (buf.empty()) return;
    ask("> 0 E" + buf);
    buf.clear();
}

void cooperative_worker(int m, int NUM_AGENTS, int AGENT_ID, int MAX_MSG_LEN,
                        const vector<Edge> &edges) {
    const int V = m * m;
    auto diag_node = [&](double t) {
        int x = (int)llround((m - 1) * t);
        if (x < 0) x = 0;
        if (x >= m) x = m - 1;
        return x * m + x;
    };

    int root = (AGENT_ID % 2 == 1) ? (V - 1) : 0;
    int target = (root == 0) ? (V - 1) : 0;
    int strat = (AGENT_ID <= 3 ? 0 : 1);
    bool use_dfs_local = (AGENT_ID == 2 || AGENT_ID == 3);
    bool endpoint_to_endpoint = true;

    // Waypoint workers: two agents start from the same middle room and search to
    // opposite endpoints.  If both succeed, agent 0 receives two verified tree
    // paths whose union already contains the answer path.
    if (NUM_AGENTS >= 5 && m <= 176 && AGENT_ID == 3) {
        root = diag_node(0.50);
        target = 0;
        strat = 0;
        use_dfs_local = false;
        endpoint_to_endpoint = false;
    } else if (NUM_AGENTS >= 5 && m <= 176 && AGENT_ID == 4) {
        root = diag_node(0.50);
        target = V - 1;
        strat = 0;
        use_dfs_local = false;
        endpoint_to_endpoint = false;
    } else if (NUM_AGENTS >= 6 && m <= 176 && AGENT_ID == 5) {
        root = diag_node(0.33);
        target = 0;
        strat = 1;
        use_dfs_local = false;
        endpoint_to_endpoint = false;
    }

    int flush_cap = (m <= 101 ? 24 : 40);
    int flush_ids = max(1, min(flush_cap, (MAX_MSG_LEN - 1) / 3));
    string buf;
    buf.reserve(3 * flush_ids);
    if (use_dfs_local) {
        DFSExplorer ex(m, root, target, strat, edges);
        while (true) {
            if ((int)buf.size() / 3 >= flush_ids) coop_worker_flush(buf);
            int eid = ex.next_query_or_claim();
            if (eid == -2) {
                coop_worker_flush(buf);
                if (endpoint_to_endpoint) claim_path(ex.current_path_answer());
                halt_now();
            }
            if (eid < 0) { coop_worker_flush(buf); halt_now(); }
            bool ok = query_cell(edges[eid].qr, edges[eid].qc);
            ex.record_result(eid, ok);
            if (ok) {
                buf += encode_id3(eid);
                if ((int)buf.size() / 3 >= flush_ids) coop_worker_flush(buf);
            }
        }
    } else {
        CoopBFExplorer ex(m, root, target, strat, edges);
        while (true) {
            if ((int)buf.size() / 3 >= flush_ids) coop_worker_flush(buf);
            int eid = ex.next_query();
            if (eid < 0) { coop_worker_flush(buf); halt_now(); }
            bool ok = query_cell(edges[eid].qr, edges[eid].qc);
            ex.record_result(eid, ok);
            if (ok) {
                buf += encode_id3(eid);
                if (ex.reached) {
                    if (endpoint_to_endpoint) claim_path(ex.current_path_answer());
                    coop_worker_flush(buf);
                    halt_now();
                }
                if ((int)buf.size() / 3 >= flush_ids) coop_worker_flush(buf);
            }
        }
    }
}

void cooperative_active_coordinator(int m, int NUM_AGENTS, int MAX_MSG_LEN,
                                    const vector<Edge> &edges) {
    const int V = m * m;
    DSU dsu(V);
    vector<vector<pair<int,char>>> adj(V);
    vector<unsigned char> seen_open(edges.size(), 0);
    CoopBFExplorer ex(m, 0, V - 1, 0, edges);

    int recv_period;
    if (m <= 101) {
        if (NUM_AGENTS <= 3) recv_period = 6;
        else if (NUM_AGENTS <= 5) recv_period = 5;
        else recv_period = 4;
    } else {
        if (NUM_AGENTS <= 3) recv_period = 10;
        else if (NUM_AGENTS <= 5) recv_period = 7;
        else recv_period = 5;
    }
    int since_recv = 0;
    bool explorer_done = false;

    auto maybe_claim_union = [&]() {
        if (dsu.find(0) == dsu.find(V - 1)) {
            string ans = answer_from_known_adj(m, adj);
            if (!ans.empty() || V == 1) claim_path(ans);
        }
    };

    while (true) {
        maybe_claim_union();
        bool do_recv = explorer_done || (since_recv >= recv_period);
        if (do_recv) {
            string rep = ask("< ?");
            since_recv = 0;
            if (rep != "- -") {
                size_t sp = rep.find(' ');
                if (sp != string::npos) {
                    string body = rep.substr(sp + 1);
                    coop_parse_open_message(body, edges, seen_open, dsu, adj);
                }
            }
            continue;
        }

        int eid = ex.next_query();
        if (eid < 0) {
            explorer_done = true;
            continue;
        }
        bool ok = query_cell(edges[eid].qr, edges[eid].qc);
        ++since_recv;
        ex.record_result(eid, ok);
        if (ok) {
            if (!seen_open[eid]) {
                seen_open[eid] = 1;
                add_known_open_edge(eid, edges, dsu, adj);
            }
            if (ex.reached) claim_path(ex.current_path_answer());
        }
    }
}

void cooperative_low_agent_solver(int m, int NUM_AGENTS, int AGENT_ID, int MAX_MSG_LEN,
                                  const vector<Edge> &edges) {
    if (AGENT_ID == 0) cooperative_active_coordinator(m, NUM_AGENTS, MAX_MSG_LEN, edges);
    else cooperative_worker(m, NUM_AGENTS, AGENT_ID, MAX_MSG_LEN, edges);
}

// Safe single-process fallback.  Used only outside the finals-like settings.
void single_agent_solver(int m, const vector<Edge> &edges) {
    int V = m * m;
    vector<vector<pair<int,char>>> adj(V);
    for (int eid = 0; eid < (int)edges.size(); ++eid) {
        if (query_cell(edges[eid].qr, edges[eid].qc)) {
            const Edge &e = edges[eid];
            adj[e.u].push_back({e.v, e.dir});
            adj[e.v].push_back({e.u, opposite_dir(e.dir)});
        }
    }
    claim_path(answer_from_known_adj(m, adj));
}

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;
    string dummy;
    getline(cin, dummy);

    if (N == 1) {
        if (AGENT_ID == 0) claim_path("");
        halt_now();
    }

    int m = (N + 1) / 2;
    vector<Edge> edges = build_edges(m);

    if (NUM_AGENTS <= 1 || MAX_MSG_LEN < 4) {
        if (AGENT_ID == 0) single_agent_solver(m, edges);
        halt_now();
    }

    const int E = (int)edges.size();

    // Few-agent DFS is useful on large boards, but it is noisy on small boards.
    // Otherwise use a batched diagonal scan; workers reduce within groups so agent 0
    // no longer has to read one message from every single process.
    bool use_coop = (NUM_AGENTS <= 3) || (NUM_AGENTS <= 6 && N >= 101);

    if (use_coop) {
        cooperative_low_agent_solver(m, NUM_AGENTS, AGENT_ID, MAX_MSG_LEN, edges);
    } else {
        vector<int> order = build_priority_order(m, edges);
        hierarchical_scan_solver(m, NUM_AGENTS, AGENT_ID, MAX_MSG_LEN, edges, order);
    }
    return 0;
}