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

static int N, K, ID, MAXL;
static int M;                 // room grid size = (N+1)/2
static long long Hcnt, Ecnt;  // horizontal edges, all edges
// Printable-ASCII base-95 packing.  A 16-byte block stores 105 bits
// (2^105 <= 95^16), substantially denser than 6-bit base64.
static const int PACK_G = 16;
static const int PACK_BITS[17] = {0,6,13,19,26,32,39,45,52,59,65,72,78,85,91,98,105};
static inline long long bits_per_chars(long long chars){
    if(chars <= 0) return 0;
    return (chars / PACK_G) * 105LL + PACK_BITS[chars % PACK_G];
}
static inline int chars_needed_for_bits(long long bits){
    if(bits <= 0) return 0;
    long long lo = 1, hi = 1;
    while(bits_per_chars(hi) < bits) hi <<= 1;
    while(lo < hi){
        long long mid = (lo + hi) >> 1;
        if(bits_per_chars(mid) >= bits) hi = mid; else lo = mid + 1;
    }
    return (int)lo;
}

struct Range { long long l, r; };

static inline long long ceil_div(long long a, long long b){ return b? (a + b - 1) / b : 0; }

Range range_for(int id, int P){
    long long base = Ecnt / P, rem = Ecnt % P;
    long long l = id * base + min<long long>(id, rem);
    long long len = base + (id < rem ? 1 : 0);
    return {l, l + len};
}

struct EdgeInfo { int u, v, qr, qc; };

EdgeInfo edge_info(long long eid){
    if(eid < Hcnt){
        long long r = eid / (M - 1);
        long long c = eid % (M - 1);
        int u = (int)(r * M + c);
        int v = u + 1;
        int qr = (int)(2*r + 1);
        int qc = (int)(2*c + 2);
        return {u, v, qr, qc};
    } else {
        long long t = eid - Hcnt;
        long long r = t / M;
        long long c = t % M;
        int u = (int)(r * M + c);
        int v = u + M;
        int qr = (int)(2*r + 2);
        int qc = (int)(2*c + 1);
        return {u, v, qr, qc};
    }
}

long long edge_id_between(int u, int v){
    if(u > v) swap(u, v);
    int ru = u / M, cu = u % M;
    int rv = v / M, cv = v % M;
    if(ru == rv){
        int c = min(cu, cv);
        return 1LL * ru * (M - 1) + c;
    } else {
        int r = min(ru, rv);
        return Hcnt + 1LL * r * M + cu;
    }
}

vector<int> neigh_rooms(int u){
    int r = u / M, c = u % M;
    vector<int> ns;
    if(r > 0) ns.push_back(u - M);
    if(c > 0) ns.push_back(u - 1);
    if(r + 1 < M) ns.push_back(u + M);
    if(c + 1 < M) ns.push_back(u + 1);
    return ns;
}

string ask_line(const string &cmd){
    cout << cmd << '\n' << flush;
    string line;
    if(!getline(cin, line)) exit(0);
    return line;
}

bool query_edge(long long eid){
    EdgeInfo e = edge_info(eid);
    string reply = ask_line("? " + to_string(e.qr) + " " + to_string(e.qc));
    return !reply.empty() && reply[0] == '1';
}

vector<char> query_range_bits(Range rg){
    vector<char> bits;
    bits.reserve((size_t)(rg.r - rg.l));
    for(long long eid = rg.l; eid < rg.r; ++eid) bits.push_back(query_edge(eid) ? 1 : 0);
    return bits;
}

string encode_bits(const vector<char>& bits, long long from_bit, long long bit_count){
    string s;
    if(bit_count <= 0) return s;
    int chars = chars_needed_for_bits(bit_count);
    s.reserve(chars);
    long long pos = 0;
    int used = 0;
    while(used < chars){
        int g = min(PACK_G, chars - used);
        int take = (int)min<long long>(PACK_BITS[g], bit_count - pos);
        unsigned __int128 x = 0;
        for(int b = 0; b < take; ++b){
            if(bits[(size_t)(from_bit + pos + b)]) x |= ((unsigned __int128)1 << b);
        }
        for(int j = 0; j < g; ++j){
            int digit = (int)(x % 95);
            s.push_back(char(32 + digit));
            x /= 95;
        }
        pos += take;
        used += g;
    }
    return s;
}

void decode_into(const string& body, vector<char>& out, long long start_bit, long long max_bits){
    long long pos = 0;
    int idx = 0, n = (int)body.size();
    while(idx < n && pos < max_bits){
        int g = min(PACK_G, n - idx);
        unsigned __int128 x = 0, mul = 1;
        for(int j = 0; j < g; ++j){
            int digit = int((unsigned char)body[idx++]) - 32;
            if(digit < 0 || digit >= 95) digit = 0;
            x += (unsigned __int128)digit * mul;
            mul *= 95;
        }
        int take = (int)min<long long>(PACK_BITS[g], max_bits - pos);
        for(int b = 0; b < take; ++b, ++pos){
            out[(size_t)(start_bit + pos)] = (char)((x >> b) & 1);
        }
    }
}

void send_bits_to(int target, const vector<char>& bits){
    long long B = max(1LL, bits_per_chars(MAXL));
    long long total = (long long)bits.size();
    long long chunks = ceil_div(total, B);
    for(long long ch = 0; ch < chunks; ++ch){
        long long st = ch * B;
        long long cnt = min(B, total - st);
        string body = encode_bits(bits, st, cnt);
        cout << "> " << target << " " << body << '\n' << flush;
        if(ch + 1 < chunks){
            string ok;
            if(!getline(cin, ok)) exit(0);
        }
    }
}

pair<int,string> parse_message_line(const string& line){
    if(line.size() >= 1 && line[0] == '-') return {-1, ""};
    size_t sp = line.find(' ');
    if(sp == string::npos) return {-1, ""};
    int sender = -1;
    try { sender = stoi(line.substr(0, sp)); } catch(...) { sender = -1; }
    string body = line.substr(sp + 1);
    return {sender, body};
}

string room_path_to_moves(const vector<int>& nodes){
    string path;
    path.reserve(nodes.size() * 2);
    for(size_t i = 1; i < nodes.size(); ++i){
        int a = nodes[i-1], b = nodes[i];
        int ar = a / M, ac = a % M, br = b / M, bc = b % M;
        char ch = '?';
        if(br == ar + 1 && bc == ac) ch = 'D';
        else if(br == ar - 1 && bc == ac) ch = 'U';
        else if(br == ar && bc == ac + 1) ch = 'R';
        else if(br == ar && bc == ac - 1) ch = 'L';
        path.push_back(ch);
        path.push_back(ch);
    }
    return path;
}

string solve_from_full_bits(const vector<char>& open){
    int V = M * M, start = 0, goal = V - 1;
    if(start == goal) return "";
    vector<array<int,4>> adj(V);
    vector<unsigned char> deg(V, 0);
    for(long long eid = 0; eid < Ecnt; ++eid){
        if(!open[(size_t)eid]) continue;
        EdgeInfo e = edge_info(eid);
        adj[e.u][deg[e.u]++] = e.v;
        adj[e.v][deg[e.v]++] = e.u;
    }
    vector<int> par(V, -2);
    queue<int> q;
    par[start] = -1;
    q.push(start);
    while(!q.empty()){
        int u = q.front(); q.pop();
        if(u == goal) break;
        for(int i = 0; i < deg[u]; ++i){
            int v = adj[u][i];
            if(par[v] == -2){ par[v] = u; q.push(v); }
        }
    }
    vector<int> nodes;
    for(int cur = goal; cur != -1; cur = par[cur]){
        nodes.push_back(cur);
        if(cur == start) break;
    }
    reverse(nodes.begin(), nodes.end());
    return room_path_to_moves(nodes);
}

struct Plan { int P = 1; int A = 1; long long est = (1LL<<60); };

long long raw_chunks(long long bits){ return bits <= 0 ? 0 : ceil_div(bits, max(1LL, bits_per_chars(MAXL))); }

Plan best_static_plan(){
    Plan best;
    if(K < 2 || Ecnt == 0) return best;
    int maxP = (int)min<long long>(K, max(2LL, Ecnt));
    long long B = max(1LL, bits_per_chars(MAXL));
    for(int P = 2; P <= maxP; ++P){
        vector<long long> len(P);
        for(int i = 0; i < P; ++i){ Range r = range_for(i, P); len[i] = r.r - r.l; }
        int nonroot = P - 1;
        for(int A = 1; A <= nonroot; ++A){
            long long totalFinal = 0, maxReady = 0, maxAgent = len[0];
            for(int gs = 1; gs < P; gs += A){
                int ge = min(P, gs + A);
                long long groupBits = 0, rawNonLeader = 0, qmax = 0;
                for(int id = gs; id < ge; ++id){
                    groupBits += len[id];
                    qmax = max(qmax, len[id]);
                    if(id != gs) rawNonLeader += raw_chunks(len[id]);
                    if(id != gs) maxAgent = max(maxAgent, len[id] + raw_chunks(len[id]));
                }
                long long cgrp = raw_chunks(groupBits);
                // +2 covers the one-round delivery lag and the command after the last receive.
                long long ready = qmax + rawNonLeader + 2;
                maxReady = max(maxReady, ready);
                maxAgent = max(maxAgent, ready + cgrp);
                totalFinal += cgrp;
            }
            long long rootFinish = max(len[0] + 1, maxReady + 2) + totalFinal + 1;
            long long est = max(maxAgent, rootFinish);
            // Avoid silly plans with huge numbers of zero-length helpers.
            if(est < best.est){ best = {P, A, est}; }
        }
    }
    return best;
}

bool choose_independent(const Plan& sp){
    if(Ecnt == 0) return true;
    if(K == 1) return true;
    if(K > 6) return false;
    static double C[7] = {0, 0.58, 0.43, 0.40, 0.37, 0.35, 0.34};
    int kk = min(K, 6);
    double ind = C[kk] * double(M) * double(M) + 30.0;
    if(K <= 4) return ind <= double(sp.est) * 1.10;
    return ind <= double(sp.est) * 0.98;
}

// ---------- Independent search variants ----------
struct Item {
    long long key;
    int tie, side, u, v;
    bool operator<(const Item& other) const{
        if(key != other.key) return key > other.key;
        return tie > other.tie;
    }
};

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

long long edge_query_coord_key(int u, int v){
    long long eid = edge_id_between(u, v);
    return eid;
}

struct GreedyParams { int origin, target; int diagW; int gW; int randW; int seed; };

long long greedy_key(int u, int v, const vector<int>& dist, const GreedyParams& p){
    int vr = v / M, vc = v % M;
    int tr = p.target / M, tc = p.target % M;
    int h = abs(vr - tr) + abs(vc - tc);
    int diag = abs(abs(vr - tr) - abs(vc - tc));
    long long rnd = (long long)(splitmix64((uint64_t)edge_id_between(u,v) ^ (uint64_t)p.seed * 0x9e3779b97f4a7c15ULL) & 1023ULL);
    // h dominates; small weights break ties and make a portfolio of different searches.
    return 1000000LL * h + 1000LL * p.diagW * diag + 1000LL * p.gW * (dist[u] + 1) + p.randW * rnd;
}

string reconstruct_one_side(int origin, int target, const vector<int>& par){
    vector<int> nodes;
    for(int cur = target; cur != -1; cur = par[cur]){
        nodes.push_back(cur);
        if(cur == origin) break;
    }
    if(origin == 0) reverse(nodes.begin(), nodes.end());
    // If origin is the goal, nodes already run start -> goal.
    return room_path_to_moves(nodes);
}

void run_greedy_variant(const GreedyParams& p){
    int V = M * M;
    vector<unsigned char> reached(V, 0), queried((size_t)Ecnt, 0);
    vector<int> par(V, -1), dist(V, 0);
    priority_queue<Item> pq;
    int tie = 0;
    auto add_edges = [&](int u){
        vector<int> ns = neigh_rooms(u);
        for(int v : ns){
            long long eid = edge_id_between(u, v);
            if(queried[(size_t)eid]) continue;
            pq.push({greedy_key(u, v, dist, p), tie++, 0, u, v});
        }
    };
    reached[p.origin] = 1;
    add_edges(p.origin);
    while(true){
        Item it;
        do {
            if(pq.empty()) exit(0);
            it = pq.top(); pq.pop();
        } while(queried[(size_t)edge_id_between(it.u,it.v)] || !reached[it.u]);
        long long eid = edge_id_between(it.u, it.v);
        queried[(size_t)eid] = 1;
        bool open = query_edge(eid);
        if(open && !reached[it.v]){
            reached[it.v] = 1;
            par[it.v] = it.u;
            dist[it.v] = dist[it.u] + 1;
            if(it.v == p.target){
                string path = reconstruct_one_side(p.origin, p.target, par);
                cout << "! " << path << '\n' << flush;
                return;
            }
            add_edges(it.v);
        }
    }
}

long long bi_key(int side, int u, int v, int modeSeed, int diagW){
    int target = (side == 0 ? M*M - 1 : 0);
    int vr = v / M, vc = v % M;
    int tr = target / M, tc = target % M;
    int h = abs(vr - tr) + abs(vc - tc);
    int diag = abs(abs(vr - tr) - abs(vc - tc));
    long long rnd = (long long)(splitmix64((uint64_t)edge_id_between(u,v) ^ (uint64_t)(modeSeed+side*17) * 0x9e3779b97f4a7c15ULL) & 1023ULL);
    return 1000000LL*h + 1000LL*diagW*diag + rnd;
}

vector<int> path_to_root(int x, const vector<int>& par){
    vector<int> a;
    for(int cur = x; cur != -1; cur = par[cur]) a.push_back(cur);
    return a;
}

string reconstruct_bidir(int side, int u, int v, const vector<int>& par0, const vector<int>& par1){
    int aStartNode, bGoalNode;
    if(side == 0){ aStartNode = u; bGoalNode = v; }
    else { aStartNode = v; bGoalNode = u; }
    vector<int> left = path_to_root(aStartNode, par0); // node -> start
    reverse(left.begin(), left.end());                 // start -> node
    vector<int> right = path_to_root(bGoalNode, par1); // node -> goal
    vector<int> nodes = left;
    nodes.insert(nodes.end(), right.begin(), right.end());
    return room_path_to_moves(nodes);
}

void run_bidir_variant(bool alternate, int diagW, int seed){
    int V = M * M, start = 0, goal = V - 1;
    vector<signed char> comp(V, -1);
    vector<int> par0(V, -1), par1(V, -1);
    vector<unsigned char> queried((size_t)Ecnt, 0);
    priority_queue<Item> pq[2];
    int tie = 0;
    auto add_edges = [&](int side, int u){
        for(int v : neigh_rooms(u)){
            long long eid = edge_id_between(u, v);
            if(queried[(size_t)eid]) continue;
            if(comp[v] == side) continue;
            pq[side].push({bi_key(side,u,v,seed,diagW), tie++, side, u, v});
        }
    };
    comp[start] = 0; comp[goal] = 1;
    add_edges(0, start); add_edges(1, goal);
    int turnSide = 0;
    while(true){
        int side = 0;
        if(alternate){
            bool found = false;
            for(int k2=0;k2<2 && !found;k2++){
                int s = turnSide; turnSide ^= 1;
                while(!pq[s].empty()){
                    Item it = pq[s].top();
                    long long eid = edge_id_between(it.u,it.v);
                    if(!queried[(size_t)eid] && comp[it.u] == s && comp[it.v] != s){ found = true; break; }
                    pq[s].pop();
                }
                if(found){ side = s; break; }
            }
            if(!found) exit(0);
        } else {
            long long bestKey = LLONG_MAX;
            bool found = false;
            for(int s=0;s<2;s++){
                while(!pq[s].empty()){
                    Item it = pq[s].top();
                    long long eid = edge_id_between(it.u,it.v);
                    if(!queried[(size_t)eid] && comp[it.u] == s && comp[it.v] != s) break;
                    pq[s].pop();
                }
                if(!pq[s].empty() && pq[s].top().key < bestKey){ bestKey = pq[s].top().key; side = s; found = true; }
            }
            if(!found) exit(0);
        }
        Item it = pq[side].top(); pq[side].pop();
        long long eid = edge_id_between(it.u, it.v);
        if(queried[(size_t)eid] || comp[it.u] != side || comp[it.v] == side) continue;
        queried[(size_t)eid] = 1;
        bool open = query_edge(eid);
        if(open){
            if(comp[it.v] == 1 - side){
                string path = reconstruct_bidir(side, it.u, it.v, par0, par1);
                cout << "! " << path << '\n' << flush;
                return;
            }
            if(comp[it.v] == -1){
                comp[it.v] = side;
                if(side == 0) par0[it.v] = it.u; else par1[it.v] = it.u;
                add_edges(side, it.v);
            }
        }
    }
}

void run_independent(){
    int V = M * M;
    if(V == 1){ if(ID == 0) cout << "! " << '\n' << flush; return; }
    int v = ID % 10;
    // Portfolio tuned separately for the low-agent cases.
    if(K == 1){
        if(M <= 35) run_greedy_variant({0, V-1, 300, 50, 0, 11});
        else run_bidir_variant(false, 300, 97);
    } else if(K == 2){
        if(ID == 0) run_greedy_variant({0, V-1, 300, 50, 0, 11});
        else run_greedy_variant({V-1, 0, 500, -20, 0, 61});
    } else if(K == 3){
        if(ID == 0) run_bidir_variant(false, 200, 31);
        else if(ID == 1) run_greedy_variant({0, V-1, 300, 50, 0, 11});
        else run_greedy_variant({V-1, 0, 500, -20, 0, 61});
    } else if(K == 4){
        if(ID == 0) run_bidir_variant(false, 200, 31);
        else if(ID == 1) run_greedy_variant({V-1, 0, 0, 0, 0, 61});
        else if(ID == 2) run_greedy_variant({0, V-1, 300, 50, 0, 11});
        else run_bidir_variant(false, 800, 97);
    } else if(K == 5){
        if(ID == 0) run_bidir_variant(false, 200, 31);
        else if(ID == 1) run_greedy_variant({0, V-1, 0, 0, 0, 59});
        else if(ID == 2) run_greedy_variant({V-1, 0, 0, 0, 0, 61});
        else if(ID == 3) run_greedy_variant({0, V-1, 300, 50, 0, 11});
        else run_bidir_variant(false, 800, 97);
    } else {
        if(ID == 0) run_bidir_variant(false, 200, 31);
        else if(ID == 1) run_greedy_variant({0, V-1, 0, 0, 0, 59});
        else if(ID == 2) run_greedy_variant({V-1, 0, 0, 0, 0, 61});
        else if(ID == 3) run_greedy_variant({0, V-1, 300, 50, 0, 11});
        else if(ID == 4) run_bidir_variant(false, 800, 97);
        else run_greedy_variant({V-1, 0, 500, -20, 0, 61});
    }
}


// ---------- Ranked phased prefix aggregation ----------
void run_static(const Plan& pl);

struct DSUFast {
    vector<int> p, sz;
    DSUFast(int n=0){ 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; }
};


// ---------- Cooperative focused-search union mode ----------
// Several agents run different biased searches.  They report only discovered
// open edges to agent 0, which unions them and can reconstruct the path as soon
// as the two corners become connected.  This beats full-map communication for
// the small-team cases where map aggregation is too expensive.
struct UVar { int kind; bool alt; int d, g, origin, seed; };

vector<UVar> union_vars(){
    auto B  = [&](int d, int g, bool alt=false)->UVar{ return {0, alt, d, g, 0, 777 + d*7 + g + (alt ? 9999 : 0)}; };
    auto GS = [&](int d, int g)->UVar{ return {1, false, d, g, 0, 123 + d*5 + g}; };
    auto GG = [&](int d, int g)->UVar{ return {1, false, d, g, 1, 321 + d*3 + g}; };
    if(M <= 40){
        return { B(300,100), B(800,100), B(0,-100), B(100,0), B(800,-200),
                 B(1000,-50), B(0,0), GS(0,-100), B(500,0,true), GS(300,-200),
                 GG(0,-100), B(-200,50), B(0,300), B(300,-100), B(100,200) };
    } else if(M <= 100){
        return { B(100,-200), GS(200,-200), B(1000,-100), B(300,150),
                 B(300,-200), GS(100,-200), B(0,-200), B(200,0,true),
                 B(1000,-50,true), B(-200,0), B(0,-50,true), GG(1000,-100),
                 GS(500,200), GS(0,-200), B(500,0) };
    } else {
        if(K == 2){
            return { B(500,-50), B(0,150), B(300,-200), GG(0,-100), B(800,-100),
                     B(1000,-200), GS(500,-200), B(800,0), B(300,-100), B(500,-200),
                     B(0,-200), B(500,0), B(200,50,true), B(0,50), B(800,-200),
                     GS(200,-200), B(200,-100), B(200,0,true), B(0,-100), B(0,-100,true) };
        }
        return { B(300,-200), GG(0,-100), B(0,50), B(800,-100), B(1000,-200),
                 GS(500,-200), B(800,0), B(300,-100), B(500,-200), B(0,-200),
                 B(500,0), B(200,50,true), B(800,-200), GS(200,-200), B(200,-100),
                 B(200,0,true), B(0,-100), B(500,-50), B(0,-100,true), B(0,150) };
    }
}

long long union_bi_key(int side, int u, int v, int depth, const UVar& var){
    int target = (side == 0 ? M*M - 1 : 0);
    int vr = v / M, vc = v % M;
    int tr = target / M, tc = target % M;
    int h = abs(vr - tr) + abs(vc - tc);
    int diag = abs(abs(vr - tr) - abs(vc - tc));
    long long rnd = (long long)(splitmix64((uint64_t)edge_id_between(u,v) ^ (uint64_t)(var.seed+side*17) * 0x9e3779b97f4a7c15ULL) & 1023ULL);
    return 1000000LL*h + 1000LL*var.d*diag + 1000LL*var.g*(depth + 1) + rnd;
}

struct SearchStepper {
    UVar var;
    int V, start, goal;
    vector<unsigned char> queried;
    vector<unsigned char> reached;
    vector<int> gpar, gdist;
    priority_queue<Item> gpq;
    vector<signed char> comp;
    vector<int> par0, par1, dep0, dep1;
    priority_queue<Item> bpq[2];
    int tie = 0, turnSide = 0;

    SearchStepper(const UVar& v): var(v) {
        V = M * M; start = 0; goal = V - 1;
        queried.assign((size_t)Ecnt, 0);
        if(var.kind == 1) init_greedy(); else init_bidir();
    }
    void init_greedy(){
        int origin = (var.origin == 0 ? start : goal);
        reached.assign(V, 0); gpar.assign(V, -1); gdist.assign(V, 0);
        reached[origin] = 1; add_greedy_edges(origin);
    }
    long long greedy_key2(int u, int v){
        int target = (var.origin == 0 ? goal : start);
        int vr = v / M, vc = v % M;
        int tr = target / M, tc = target % M;
        int h = abs(vr - tr) + abs(vc - tc);
        int diag = abs(abs(vr - tr) - abs(vc - tc));
        long long rnd = (long long)(splitmix64((uint64_t)edge_id_between(u,v) ^ (uint64_t)var.seed * 0x9e3779b97f4a7c15ULL) & 1023ULL);
        return 1000000LL*h + 1000LL*var.d*diag + 1000LL*var.g*(gdist[u] + 1) + rnd;
    }
    void add_greedy_edges(int u){
        for(int v : neigh_rooms(u)){
            long long eid = edge_id_between(u, v);
            if(queried[(size_t)eid] || reached[v]) continue;
            gpq.push({greedy_key2(u, v), tie++, 0, u, v});
        }
    }
    void init_bidir(){
        comp.assign(V, -1); par0.assign(V, -1); par1.assign(V, -1); dep0.assign(V, 0); dep1.assign(V, 0);
        comp[start] = 0; comp[goal] = 1;
        add_bidir_edges(0, start); add_bidir_edges(1, goal);
    }
    void add_bidir_edges(int side, int u){
        for(int v : neigh_rooms(u)){
            long long eid = edge_id_between(u, v);
            if(queried[(size_t)eid] || comp[v] == side) continue;
            int depth = (side == 0 ? dep0[u] : dep1[u]);
            bpq[side].push({union_bi_key(side, u, v, depth, var), tie++, side, u, v});
        }
    }
    pair<int,string> step(){ return (var.kind == 1 ? step_greedy() : step_bidir()); }
    pair<int,string> step_greedy(){
        int origin = (var.origin == 0 ? start : goal);
        int target = (var.origin == 0 ? goal : start);
        while(true){
            if(gpq.empty()) return {-1, ""};
            Item it = gpq.top(); gpq.pop();
            long long eid = edge_id_between(it.u, it.v);
            if(queried[(size_t)eid] || !reached[it.u] || reached[it.v]) continue;
            queried[(size_t)eid] = 1;
            bool open = query_edge(eid);
            if(open && !reached[it.v]){
                reached[it.v] = 1; gpar[it.v] = it.u; gdist[it.v] = gdist[it.u] + 1;
                if(it.v == target){ return {(int)eid, reconstruct_one_side(origin, target, gpar)}; }
                add_greedy_edges(it.v);
                return {(int)eid, ""};
            }
            return {-1, ""};
        }
    }
    pair<int,string> step_bidir(){
        int side = 0;
        if(var.alt){
            bool found = false;
            for(int k2 = 0; k2 < 2 && !found; ++k2){
                int s = turnSide; turnSide ^= 1;
                while(!bpq[s].empty()){
                    Item it = bpq[s].top();
                    long long eid = edge_id_between(it.u,it.v);
                    if(!queried[(size_t)eid] && comp[it.u] == s && comp[it.v] != s){ found = true; break; }
                    bpq[s].pop();
                }
                if(found){ side = s; break; }
            }
            if(!found) return {-1, ""};
        } else {
            long long bestKey = LLONG_MAX;
            bool found = false;
            for(int s = 0; s < 2; ++s){
                while(!bpq[s].empty()){
                    Item it = bpq[s].top();
                    long long eid = edge_id_between(it.u,it.v);
                    if(!queried[(size_t)eid] && comp[it.u] == s && comp[it.v] != s) break;
                    bpq[s].pop();
                }
                if(!bpq[s].empty() && bpq[s].top().key < bestKey){ bestKey = bpq[s].top().key; side = s; found = true; }
            }
            if(!found) return {-1, ""};
        }
        Item it = bpq[side].top(); bpq[side].pop();
        long long eid = edge_id_between(it.u, it.v);
        if(queried[(size_t)eid] || comp[it.u] != side || comp[it.v] == side) return {-1, ""};
        queried[(size_t)eid] = 1;
        bool open = query_edge(eid);
        if(open){
            if(comp[it.v] == 1 - side){ return {(int)eid, reconstruct_bidir(side, it.u, it.v, par0, par1)}; }
            if(comp[it.v] == -1){
                comp[it.v] = side;
                if(side == 0){ par0[it.v] = it.u; dep0[it.v] = dep0[it.u] + 1; }
                else { par1[it.v] = it.u; dep1[it.v] = dep1[it.u] + 1; }
                add_bidir_edges(side, it.v);
            }
            return {(int)eid, ""};
        }
        return {-1, ""};
    }
};

string encode_edge_ids(const vector<int>& edges, int l, int r){
    string s;
    s.reserve((r - l) * 3);
    for(int i = l; i < r; ++i){
        int x = edges[i];
        s.push_back(char(32 + (x % 95))); x /= 95;
        s.push_back(char(32 + (x % 95))); x /= 95;
        s.push_back(char(32 + (x % 95)));
    }
    return s;
}
vector<int> decode_edge_ids(const string& body){
    vector<int> out;
    for(size_t i = 0; i + 2 < body.size(); i += 3){
        int a = int((unsigned char)body[i]) - 32;
        int b = int((unsigned char)body[i+1]) - 32;
        int c = int((unsigned char)body[i+2]) - 32;
        if(a < 0 || a >= 95 || b < 0 || b >= 95 || c < 0 || c >= 95) continue;
        int x = a + 95 * b + 9025 * c;
        if(0 <= x && x < Ecnt) out.push_back(x);
    }
    return out;
}
void send_open_edges(vector<int>& buf){
    if(buf.empty()) return;
    int per = max(1, MAXL / 3);
    for(int st = 0; st < (int)buf.size(); st += per){
        int en = min((int)buf.size(), st + per);
        cout << "> 0 " << encode_edge_ids(buf, st, en) << '\n' << flush;
        string ok;
        if(!getline(cin, ok)) exit(0);
    }
    buf.clear();
}

bool choose_union_mode(){
    if(MAXL < 3 || K < 2 || K > 6) return false;
    if(K == 2) return M >= 25;
    if(K == 3) return M >= 25;
    if(K == 4) return M >= 25;
    if(K == 5) return M >= 75;
    if(K == 6) return M >= 75;
    return false;
}

void run_union_mode(){
    int V = M * M;
    vector<UVar> vars = union_vars();
    UVar var = vars[ID % (int)vars.size()];
    SearchStepper st(var);
    const int BATCH = (M < 50 ? 48 : 96);
    int POLL = (K <= 4 ? 6 : (K == 5 ? 8 : 13));
    POLL = min(32, max(4, POLL));
    vector<int> opened;
    if(ID == 0){
        vector<char> edgeOpen((size_t)Ecnt, 0);
        DSUFast dsu(V);
        auto add_edge = [&](int eid){
            if(eid < 0 || eid >= Ecnt || edgeOpen[(size_t)eid]) return;
            edgeOpen[(size_t)eid] = 1;
            EdgeInfo e = edge_info(eid);
            dsu.unite(e.u, e.v);
        };
        auto connected = [&](){ return dsu.find(0) == dsu.find(V - 1); };
        while(true){
            for(int i = 0; i < BATCH; ++i){
                auto [eid, path] = st.step();
                if(eid >= 0) add_edge(eid);
                if(!path.empty()){ cout << "! " << path << '\n' << flush; return; }
                if(connected()){ cout << "! " << solve_from_full_bits(edgeOpen) << '\n' << flush; return; }
            }
            for(int j = 0; j < POLL; ++j){
                string line = ask_line("< ?");
                auto [sender, body] = parse_message_line(line);
                if(sender >= 1){
                    for(int eid : decode_edge_ids(body)) add_edge(eid);
                    if(connected()){ cout << "! " << solve_from_full_bits(edgeOpen) << '\n' << flush; return; }
                }
            }
        }
    } else {
        while(true){
            for(int i = 0; i < BATCH; ++i){
                auto [eid, path] = st.step();
                if(eid >= 0) opened.push_back(eid);
                if(!path.empty()){ cout << "! " << path << '\n' << flush; return; }
            }
            send_open_edges(opened);
        }
    }
}

struct PhaseInfo { long long s, e, len; int A; };

long long raw_chunks_chars(long long bits, long long chars){
    long long B = max(1LL, bits_per_chars(chars));
    return bits <= 0 ? 0 : ceil_div(bits, B);
}

Range phase_range_for_id(int id, int P, long long phaseStart, long long phaseLen){
    long long base = phaseLen / P, rem = phaseLen % P;
    long long off = 1LL * id * base + min<long long>(id, rem);
    long long len = base + (id < rem ? 1 : 0);
    return {phaseStart + off, phaseStart + len + off};
}

vector<int> build_rank_order(){
    struct Key { int d, anti; long long eid; };
    vector<Key> a;
    a.reserve((size_t)Ecnt);
    for(long long eid = 0; eid < Ecnt; ++eid){
        int r2, c2;
        if(eid < Hcnt){
            long long r = eid / (M - 1);
            long long c = eid % (M - 1);
            r2 = (int)(2 * r);
            c2 = (int)(2 * c + 1);
        } else {
            long long t = eid - Hcnt;
            long long r = t / M;
            long long c = t % M;
            r2 = (int)(2 * r + 1);
            c2 = (int)(2 * c);
        }
        int d = abs(r2 - c2);
        int anti = abs((r2 + c2) - 2 * (M - 1));
        a.push_back({d, anti, eid});
    }
    sort(a.begin(), a.end(), [](const Key& x, const Key& y){
        if(x.d != y.d) return x.d < y.d;
        if(x.anti != y.anti) return x.anti < y.anti;
        return x.eid < y.eid;
    });
    vector<int> order;
    order.reserve((size_t)Ecnt);
    for(auto &k : a) order.push_back((int)k.eid);
    return order;
}

int best_phase_A(long long phaseLen, long long payloadChars){
    if(K <= 2) return 1;
    vector<long long> len(K), pref(K + 1, 0), prefChunks(K + 1, 0);
    for(int i = 0; i < K; ++i){
        Range r = phase_range_for_id(i, K, 0, phaseLen);
        len[i] = r.r - r.l;
        pref[i+1] = pref[i] + len[i];
        prefChunks[i+1] = prefChunks[i] + raw_chunks_chars(len[i], payloadChars);
    }
    long long bestEst = (1LL<<60);
    int bestA = 1;
    for(int A = 1; A <= K - 1; ++A){
        long long totalRoot = 0, maxReady = 0, maxLeader = 0;
        for(int gs = 1; gs < K; gs += A){
            int ge = min(K, gs + A);
            long long groupBits = pref[ge] - pref[gs];
            long long rawNonLeader = prefChunks[ge] - prefChunks[gs + 1];
            long long qmax = 0;
            for(int id = gs; id < ge; ++id) qmax = max(qmax, len[id]);
            long long cgrp = raw_chunks_chars(groupBits, payloadChars);
            long long ready = qmax + rawNonLeader + 1;
            maxReady = max(maxReady, ready);
            maxLeader = max(maxLeader, ready + cgrp);
            totalRoot += cgrp;
        }
        long long est = max(maxLeader, max(len[0], maxReady) + totalRoot + 1);
        if(est < bestEst){ bestEst = est; bestA = A; }
    }
    return bestA;
}

vector<PhaseInfo> build_phases(long long payloadChars){
    vector<int> pct;
    if(K >= 250) pct = {80, 100};
    else if(K >= 150) pct = {60, 80, 100};
    else pct = {55, 70, 85, 100};
    vector<PhaseInfo> phases;
    long long prev = 0;
    for(int pc : pct){
        long long end = (Ecnt * pc + 50) / 100;
        if(pc == 100) end = Ecnt;
        if(end <= prev) continue;
        PhaseInfo ph;
        ph.s = prev; ph.e = end; ph.len = end - prev;
        ph.A = best_phase_A(ph.len, payloadChars);
        phases.push_back(ph);
        prev = end;
    }
    if(prev < Ecnt){
        PhaseInfo ph;
        ph.s = prev; ph.e = Ecnt; ph.len = Ecnt - prev;
        ph.A = best_phase_A(ph.len, payloadChars);
        phases.push_back(ph);
    }
    return phases;
}

void send_bits_phase_wait(int target, const vector<char>& bits, int phase, long long payloadChars){
    long long B = max(1LL, bits_per_chars(payloadChars));
    long long total = (long long)bits.size();
    long long chunks = raw_chunks_chars(total, payloadChars);
    for(long long ch = 0; ch < chunks; ++ch){
        long long st = ch * B;
        long long cnt = min(B, total - st);
        string body;
        body.reserve((size_t)payloadChars + 1);
        body.push_back(char('A' + phase));
        body += encode_bits(bits, st, cnt);
        cout << "> " << target << " " << body << '\n' << flush;
        string ok;
        if(!getline(cin, ok)) exit(0);
    }
}

void run_ranked_phased(){
    vector<int> rankEdge = build_rank_order();
    long long payloadChars = max(1, MAXL - 1);
    long long B = max(1LL, bits_per_chars(payloadChars));
    vector<PhaseInfo> phases = build_phases(payloadChars);
    int PHS = (int)phases.size();

    if(ID == 0){
        int V = M * M;
        vector<char> edgeOpen((size_t)Ecnt, 0);
        DSUFast dsu(V);
        vector<vector<long long>> recvCnt(PHS, vector<long long>(K, 0));
        vector<long long> gotPhase(PHS, 0), needPhase(PHS, 0);

        auto group_bits = [&](int ph, int leader)->long long{
            int A = phases[ph].A;
            if(leader < 1 || leader >= K) return 0;
            if((leader - 1) % A != 0) return 0;
            int ge = min(K, leader + A);
            Range first = phase_range_for_id(leader, K, phases[ph].s, phases[ph].len);
            Range last = phase_range_for_id(ge - 1, K, phases[ph].s, phases[ph].len);
            return max(0LL, last.r - first.l);
        };
        auto group_start = [&](int ph, int leader)->long long{
            Range first = phase_range_for_id(leader, K, phases[ph].s, phases[ph].len);
            return first.l;
        };
        for(int ph = 0; ph < PHS; ++ph){
            int A = phases[ph].A;
            for(int leader = 1; leader < K; leader += A){
                needPhase[ph] += raw_chunks_chars(group_bits(ph, leader), payloadChars);
            }
        }
        vector<Range> rootRanges(PHS);
        vector<long long> rootPtr(PHS);
        for(int ph = 0; ph < PHS; ++ph){
            rootRanges[ph] = phase_range_for_id(0, K, phases[ph].s, phases[ph].len);
            rootPtr[ph] = rootRanges[ph].l;
        }

        auto add_open_rank = [&](long long rank){
            if(rank < 0 || rank >= Ecnt) return;
            int eid = rankEdge[(size_t)rank];
            if(edgeOpen[(size_t)eid]) return;
            edgeOpen[(size_t)eid] = 1;
            EdgeInfo e = edge_info(eid);
            dsu.unite(e.u, e.v);
        };
        auto decode_rank_payload = [&](const string& payload, long long startRank, long long maxBits){
            long long pos = 0;
            int idx = 0, n = (int)payload.size();
            while(idx < n && pos < maxBits){
                int g = min(PACK_G, n - idx);
                unsigned __int128 x = 0, mul = 1;
                for(int j = 0; j < g; ++j){
                    int digit = int((unsigned char)payload[idx++]) - 32;
                    if(digit < 0 || digit >= 95) digit = 0;
                    x += (unsigned __int128)digit * mul;
                    mul *= 95;
                }
                int take = (int)min<long long>(PACK_BITS[g], maxBits - pos);
                for(int b = 0; b < take; ++b, ++pos){
                    if((x >> b) & 1) add_open_rank(startRank + pos);
                }
            }
        };
        auto connected = [&](){ return dsu.find(0) == dsu.find(V - 1); };
        auto claim_now = [&](){
            string path = solve_from_full_bits(edgeOpen);
            cout << "! " << path << '\n' << flush;
        };
        auto query_one_future_root = [&](int afterPh)->bool{
            if(K < 50) return false;
            for(int fp = afterPh + 1; fp < PHS; ++fp){
                if(rootPtr[fp] < rootRanges[fp].r){
                    long long rank = rootPtr[fp]++;
                    if(query_edge(rankEdge[(size_t)rank])) add_open_rank(rank);
                    return true;
                }
            }
            return false;
        };
        auto handle_root_message = [&](int sender, const string& body){
            if(sender < 1 || sender >= K || body.empty()) return;
            int ph = body[0] - 'A';
            if(ph < 0 || ph >= PHS) return;
            long long gb = group_bits(ph, sender);
            if(gb <= 0) return;
            long long ch = recvCnt[ph][sender]++;
            long long off = ch * B;
            if(off >= gb) return;
            long long cnt = min(B, gb - off);
            decode_rank_payload(body.substr(1), group_start(ph, sender) + off, cnt);
            gotPhase[ph]++;
        };

        for(int ph = 0; ph < PHS; ++ph){
            while(rootPtr[ph] < rootRanges[ph].r){
                long long rank = rootPtr[ph]++;
                if(query_edge(rankEdge[(size_t)rank])) add_open_rank(rank);
                if(connected()){ claim_now(); return; }
            }
            while(gotPhase[ph] < needPhase[ph]){
                string line = ask_line("< ?");
                auto [sender, body] = parse_message_line(line);
                if(sender >= 0) handle_root_message(sender, body);
                else if(query_one_future_root(ph) && connected()){ claim_now(); return; }
                if(connected()){ claim_now(); return; }
            }
            if(connected()){ claim_now(); return; }
        }
        claim_now();
        return;
    }

    vector<vector<pair<int,string>>> pending(PHS);
    auto parse_phase_payload = [&](const string& body, int &ph, string &payload)->bool{
        if(body.empty()) return false;
        ph = body[0] - 'A';
        if(ph < 0 || ph >= PHS) return false;
        payload = body.substr(1);
        return true;
    };

    for(int ph = 0; ph < PHS; ++ph){
        const PhaseInfo& pi = phases[ph];
        Range my = phase_range_for_id(ID, K, pi.s, pi.len);
        vector<char> local;
        local.reserve((size_t)(my.r - my.l));
        for(long long rank = my.l; rank < my.r; ++rank){
            local.push_back(query_edge(rankEdge[(size_t)rank]) ? 1 : 0);
        }
        int A = pi.A;
        int gs = 1 + ((ID - 1) / A) * A;
        int ge = min(K, gs + A);
        if(ID != gs){
            send_bits_phase_wait(gs, local, ph, payloadChars);
            continue;
        }

        Range first = phase_range_for_id(gs, K, pi.s, pi.len);
        Range last = phase_range_for_id(ge - 1, K, pi.s, pi.len);
        long long groupStart = first.l;
        long long groupBits = max(0LL, last.r - first.l);
        vector<char> group((size_t)groupBits, 0);
        for(long long i = 0; i < (long long)local.size(); ++i){
            long long off = (my.l - groupStart) + i;
            if(0 <= off && off < groupBits) group[(size_t)off] = local[(size_t)i];
        }
        vector<long long> recvCnt(K, 0);
        long long needRaw = 0;
        for(int id = gs + 1; id < ge; ++id){
            Range r = phase_range_for_id(id, K, pi.s, pi.len);
            needRaw += raw_chunks_chars(r.r - r.l, payloadChars);
        }
        long long gotRaw = 0;
        auto decode_worker_payload = [&](int sender, const string& payload)->bool{
            if(sender < gs + 1 || sender >= ge) return false;
            Range sr = phase_range_for_id(sender, K, pi.s, pi.len);
            long long ch = recvCnt[sender]++;
            long long offset = (sr.l - groupStart) + ch * B;
            long long remain = (sr.r - sr.l) - ch * B;
            if(remain <= 0) return false;
            long long cnt = min(B, remain);
            decode_into(payload, group, offset, cnt);
            gotRaw++;
            return true;
        };
        if(!pending[ph].empty()){
            vector<pair<int,string>> old;
            old.swap(pending[ph]);
            for(auto &pr : old){
                if(gotRaw >= needRaw) { pending[ph].push_back(pr); continue; }
                decode_worker_payload(pr.first, pr.second);
            }
        }
        while(gotRaw < needRaw){
            string line = ask_line("< ?");
            auto [sender, body] = parse_message_line(line);
            if(sender < 0) continue;
            int mph; string payload;
            if(!parse_phase_payload(body, mph, payload)) continue;
            if(mph == ph) decode_worker_payload(sender, payload);
            else if(mph > ph) pending[mph].push_back({sender, payload});
        }
        send_bits_phase_wait(0, group, ph, payloadChars);
    }
}



// ---------- Root-controlled batched speculative bidirectional search ----------
// Agent 0 adaptively chooses batches of unknown edges near the currently known
// start/goal frontiers.  Workers query assigned edge IDs and return packed bits.
// This trades some adaptivity for much better parallelism than independent search.
struct CVar { int d, g, seed; };

long long controller_key(int side, int u, int v, int depth, const CVar& var){
    int target = (side == 0 ? M*M - 1 : 0);
    int vr = v / M, vc = v % M;
    int tr = target / M, tc = target % M;
    int h = abs(vr - tr) + abs(vc - tc);
    int diag = abs(abs(vr - tr) - abs(vc - tc));
    long long rnd = (long long)(splitmix64((uint64_t)edge_id_between(u,v) ^ (uint64_t)(var.seed+side*17) * 0x9e3779b97f4a7c15ULL) & 1023ULL);
    return 1000000LL*h + 1000LL*var.d*diag + 1000LL*var.g*(depth + 1) + rnd;
}

string encode_task_edges(const vector<int>& edges, int l, int r){
    string s; s.reserve(1 + (r-l)*3); s.push_back('Q');
    for(int i=l;i<r;i++){
        int x=edges[i];
        s.push_back(char(32 + (x % 95))); x/=95;
        s.push_back(char(32 + (x % 95))); x/=95;
        s.push_back(char(32 + (x % 95)));
    }
    return s;
}
vector<int> decode_task_edges(const string& body){
    vector<int> out;
    size_t st = (!body.empty() && body[0]=='Q') ? 1 : 0;
    for(size_t i=st; i+2<body.size(); i+=3){
        int a=int((unsigned char)body[i])-32, b=int((unsigned char)body[i+1])-32, c=int((unsigned char)body[i+2])-32;
        if(a<0||a>=95||b<0||b>=95||c<0||c>=95) continue;
        int x=a+95*b+9025*c;
        if(0<=x && x<Ecnt) out.push_back(x);
    }
    return out;
}

void controller_add_result_edge(int eid, bool isOpen, vector<signed char>& known, DSUFast& dsu){
    if(eid < 0 || eid >= Ecnt) return;
    if(known[(size_t)eid] != -1) return;
    known[(size_t)eid] = isOpen ? 1 : 0;
    if(isOpen){ EdgeInfo e = edge_info(eid); dsu.unite(e.u, e.v); }
}

void select_with_cvar(const vector<signed char>& known, vector<unsigned char>& chosen, const CVar& var, int limit, vector<int>& out){
    if((int)out.size() >= limit) return;
    int V = M*M;
    vector<signed char> comp(V, -1);
    vector<int> dep(V, 0);
    priority_queue<Item> pq[2];
    int tie = 0;
    auto push_frontier = [&](int side, int u){
        for(int v: neigh_rooms(u)){
            long long eid = edge_id_between(u, v);
            if(known[(size_t)eid] == 0 || chosen[(size_t)eid]) continue;
            if(comp[v] == side) continue;
            pq[side].push({controller_key(side,u,v,dep[u],var), tie++, side, u, v});
        }
    };
    auto activate = [&](int side, int startNode, int startDepth){
        if(comp[startNode] == 1 - side) return;
        queue<int> q;
        if(comp[startNode] == -1){ comp[startNode] = side; dep[startNode] = startDepth; q.push(startNode); }
        while(!q.empty()){
            int u = q.front(); q.pop();
            for(int v: neigh_rooms(u)){
                long long eid = edge_id_between(u, v);
                if(known[(size_t)eid] == 1 && comp[v] == -1){
                    comp[v] = side; dep[v] = dep[u] + 1; q.push(v);
                }
            }
            push_frontier(side, u);
        }
    };
    activate(0, 0, 0);
    activate(1, V-1, 0);
    while((int)out.size() < limit){
        int side = -1; long long best = LLONG_MAX;
        for(int s=0;s<2;s++){
            while(!pq[s].empty()){
                Item it = pq[s].top(); long long eid = edge_id_between(it.u,it.v);
                if(known[(size_t)eid] != 0 && !chosen[(size_t)eid] && comp[it.u] == s && comp[it.v] != s) break;
                pq[s].pop();
            }
            if(!pq[s].empty() && pq[s].top().key < best){ best = pq[s].top().key; side = s; }
        }
        if(side < 0) break;
        Item it = pq[side].top(); pq[side].pop();
        long long eid = edge_id_between(it.u, it.v);
        if(known[(size_t)eid] == 0 || chosen[(size_t)eid] || comp[it.u] != side || comp[it.v] == side) continue;
        if(known[(size_t)eid] == 1){
            if(comp[it.v] == -1) activate(side, it.v, dep[it.u] + 1);
            continue;
        }
        chosen[(size_t)eid] = 1;
        out.push_back((int)eid);
        if(comp[it.v] == -1) activate(side, it.v, dep[it.u] + 1);
    }
}

vector<int> controller_select_batch(const vector<signed char>& known, int need, const vector<int>& rankEdge){
    vector<int> out; out.reserve(need);
    vector<unsigned char> chosen((size_t)Ecnt, 0);
    vector<CVar> vars;
    if(M <= 60) vars = {{300,0,31},{800,0,97},{0,0,59},{300,100,77}};
    else vars = {{300,-100,31},{0,50,59},{800,-100,97},{1000,-200,73},{200,50,113},{500,0,151}};
    int rounds = 0;
    while((int)out.size() < need && rounds < 2){
        int before = out.size();
        for(auto &v: vars){
            int lim = min(need, (int)out.size() + max(8, need / (int)vars.size() / 2));
            select_with_cvar(known, chosen, v, lim, out);
            if((int)out.size() >= need) break;
        }
        if((int)out.size() == before) break;
        rounds++;
    }
    if((int)out.size() < need){
        for(int eid: rankEdge){
            if((int)out.size() >= need) break;
            if(known[(size_t)eid] == -1 && !chosen[(size_t)eid]){ chosen[(size_t)eid] = 1; out.push_back(eid); }
        }
    }
    return out;
}

void run_controller_mode(){
    int V = M*M;
    int maxTask = max(1, (MAXL - 1) / 3);
    int wantL = 80;
    if(K == 7 && M >= 140) wantL = 40;
    if(K == 9 && M >= 140) wantL = 48;
    int L = min(maxTask, wantL);
    if(L <= 0) L = 1;

    if(ID != 0){
        while(true){
            string line = ask_line("< 0");
            auto [sender, body] = parse_message_line(line);
            if(sender != 0 || body.empty() || body[0] != 'Q') continue;
            vector<int> edges = decode_task_edges(body);
            vector<char> bits; bits.reserve(edges.size());
            for(int eid: edges) bits.push_back(query_edge(eid) ? 1 : 0);
            string res; res.reserve(1 + chars_needed_for_bits((long long)bits.size()));
            res.push_back('R');
            res += encode_bits(bits, 0, (long long)bits.size());
            cout << "> 0 " << res << '\n' << flush;
            string ok; if(!getline(cin, ok)) exit(0);
        }
    }

    vector<int> rankEdge = build_rank_order();
    vector<signed char> known((size_t)Ecnt, -1);
    vector<char> openBits((size_t)Ecnt, 0);
    DSUFast dsu(V);
    vector<vector<int>> assigned(K);
    auto add_result = [&](int eid, bool op){
        if(eid < 0 || eid >= Ecnt) return;
        if(known[(size_t)eid] != -1) return;
        known[(size_t)eid] = op ? 1 : 0;
        if(op){ openBits[(size_t)eid] = 1; EdgeInfo e = edge_info(eid); dsu.unite(e.u, e.v); }
    };
    auto connected = [&](){ return dsu.find(0) == dsu.find(V-1); };
    auto claim = [&](){ cout << "! " << solve_from_full_bits(openBits) << '\n' << flush; };

    while(true){
        int active = K;
        int need = active * L;
        vector<int> batch = controller_select_batch(known, need, rankEdge);
        if(batch.empty()) { claim(); return; }
        // Split: root gets first slice, workers get subsequent slices.
        int ptr = 0;
        assigned[0].clear();
        for(int i=0; i<L && ptr<(int)batch.size(); ++i) assigned[0].push_back(batch[ptr++]);
        for(int w=1; w<K; ++w){
            assigned[w].clear();
            for(int i=0; i<L && ptr<(int)batch.size(); ++i) assigned[w].push_back(batch[ptr++]);
            string body = encode_task_edges(assigned[w], 0, (int)assigned[w].size());
            cout << "> " << w << " " << body << '\n' << flush;
            string ok; if(!getline(cin, ok)) exit(0);
        }
        for(int eid: assigned[0]){
            bool op = query_edge(eid);
            add_result(eid, op);
            if(connected()){ claim(); return; }
        }
        int got = 0;
        vector<unsigned char> received(K, 0);
        while(got < K-1){
            string line = ask_line("< ?");
            auto [sender, body] = parse_message_line(line);
            if(sender < 1 || sender >= K || body.empty() || body[0] != 'R' || received[sender]) continue;
            received[sender] = 1; got++;
            vector<char> tmp(assigned[sender].size(), 0);
            decode_into(body.substr(1), tmp, 0, (long long)tmp.size());
            for(size_t i=0; i<assigned[sender].size(); ++i) add_result(assigned[sender][i], tmp[i] != 0);
            if(connected()){ claim(); return; }
        }
    }
}

bool choose_controller_mode(){
    if(MAXL < 16 || K < 7 || K > 15) return false;
    if(K <= 9) return M >= 60;
    if(K <= 11) return M >= 95;
    return M >= 140;
}

// ---------- Static aggregation ----------
void run_static(const Plan& pl){
    int P = pl.P, A = pl.A;
    if(ID >= P){
        return; // EOF; the judge marks this agent dead without costing turns.
    }
    long long B = max(1LL, bits_per_chars(MAXL));
    Range my = range_for(ID, P);

    if(ID == 0){
        vector<char> all((size_t)Ecnt, 0);
        // Root also queries its own slice before switching to collection.
        for(long long eid = my.l; eid < my.r; ++eid) all[(size_t)eid] = query_edge(eid) ? 1 : 0;

        struct GInfo { int leader; long long start, bits, chunks; };
        vector<GInfo> groups;
        unordered_map<int,int> leaderIndex;
        long long need = 0;
        for(int gs = 1; gs < P; gs += A){
            int ge = min(P, gs + A);
            Range first = range_for(gs, P);
            Range last = range_for(ge - 1, P);
            long long bits = last.r - first.l;
            long long chunks = raw_chunks(bits);
            leaderIndex[gs] = (int)groups.size();
            groups.push_back({gs, first.l, bits, chunks});
            need += chunks;
        }
        vector<long long> got(groups.size(), 0);
        long long received = 0;
        while(received < need){
            string line = ask_line("< ?");
            auto [sender, body] = parse_message_line(line);
            if(sender < 0) continue;
            auto it = leaderIndex.find(sender);
            if(it == leaderIndex.end()) continue;
            int gi = it->second;
            long long ch = got[gi]++;
            long long startBit = ch * B;
            if(startBit >= groups[gi].bits) continue;
            long long cnt = min(B, groups[gi].bits - startBit);
            decode_into(body, all, groups[gi].start + startBit, cnt);
            received++;
        }
        string path = solve_from_full_bits(all);
        cout << "! " << path << '\n' << flush;
        return;
    }

    // Determine this agent's aggregation group.
    int gs = 1 + ((ID - 1) / A) * A;
    int ge = min(P, gs + A);
    int leader = gs;
    Range grFirst = range_for(gs, P);
    Range grLast = range_for(ge - 1, P);
    long long groupStart = grFirst.l;
    long long groupBits = grLast.r - grFirst.l;

    vector<char> local = query_range_bits(my);

    if(ID != leader){
        send_bits_to(leader, local);
        return;
    }

    vector<char> group((size_t)groupBits, 0);
    for(long long i = 0; i < (long long)local.size(); ++i) group[(size_t)(my.l - groupStart + i)] = local[(size_t)i];

    vector<long long> recvCnt(P, 0);
    long long needRaw = 0;
    for(int id = gs + 1; id < ge; ++id){
        Range r = range_for(id, P);
        needRaw += raw_chunks(r.r - r.l);
    }
    long long gotRaw = 0;
    while(gotRaw < needRaw){
        string line = ask_line("< ?");
        auto [sender, body] = parse_message_line(line);
        if(sender < gs + 1 || sender >= ge) continue;
        Range sr = range_for(sender, P);
        long long ch = recvCnt[sender]++;
        long long offset = (sr.l - groupStart) + ch * B;
        long long remain = sr.r - sr.l - ch * B;
        if(remain <= 0) continue;
        long long cnt = min(B, remain);
        decode_into(body, group, offset, cnt);
        gotRaw++;
    }
    send_bits_to(0, group);
    return;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string startup;
    if(!getline(cin, startup)) return 0;
    stringstream ss(startup);
    ss >> N >> K >> ID >> MAXL;
    if(MAXL <= 0) MAXL = 1;
    M = (N + 1) / 2;
    Hcnt = 1LL * M * (M - 1);
    Ecnt = 2 * Hcnt;
    if(Ecnt == 0){
        if(ID == 0) cout << "! " << '\n' << flush;
        return 0;
    }

    Plan sp = best_static_plan();
    if(choose_controller_mode()) run_controller_mode();
    else if(choose_union_mode()) run_union_mode();
    else if(K >= 5 && MAXL >= 8) run_ranked_phased();
    else if(choose_independent(sp)) run_independent();
    else run_static(sp);
    return 0;
}