#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
static const string ALPH = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz._";
static int INV[256];

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;
    long long end = from_bit + bit_count;
    for(long long p = from_bit; p < end; p += 6){
        int val = 0;
        for(int b = 0; b < 6; ++b){
            long long idx = p + b;
            if(idx < end && bits[(size_t)idx]) val |= (1 << b);
        }
        s.push_back(ALPH[val]);
    }
    return s;
}

void decode_into(const string& body, vector<char>& out, long long start_bit, long long max_bits){
    long long pos = 0;
    for(unsigned char ch : body){
        int val = INV[ch];
        if(val < 0) continue;
        for(int b = 0; b < 6 && pos < max_bits; ++b, ++pos){
            out[(size_t)(start_bit + pos)] = (val >> b) & 1;
        }
        if(pos >= max_bits) break;
    }
}

void send_bits_to(int target, const vector<char>& bits){
    long long B = max(1, 6 * 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(1, 6 * 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(1, 6 * 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){
        run_greedy_variant({0, V-1, 500, 50, 0, 11});
    } 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; }
};

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, 6LL * 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, 6LL * 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, 6LL * 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;
            for(unsigned char ch : payload){
                int val = INV[ch];
                if(val < 0) continue;
                for(int b = 0; b < 6 && pos < maxBits; ++b, ++pos){
                    if((val >> b) & 1) add_open_rank(startRank + pos);
                }
                if(pos >= maxBits) break;
            }
        };
        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);
    }
}

// ---------- 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(1, 6 * 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);
    for(int i=0;i<256;i++) INV[i] = -1;
    for(int i=0;i<(int)ALPH.size();++i) INV[(unsigned char)ALPH[i]] = i;

    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(K >= 5 && MAXL >= 8) run_ranked_phased();
    else if(choose_independent(sp)) run_independent();
    else run_static(sp);
    return 0;
}