// MCC 2026 Problem D — Datacenter Imprisonment.
//
// One binary, two cooperative strategies, chosen at startup from (N, NUM_AGENTS):
//
//   DIRECTED (bidirectional greedy search) — dependency-bound, ~flat in A.
//     Wins when agents are scarce relative to the maze. agent 0 seeds two tasks
//     (explore from S toward T and from T toward S) and hands the closest-to-goal
//     task to each idle walker; each walker runs a budgeted greedy DFS over its
//     subtree, streams the open tree-edges it finds, and re-queues its leftover
//     frontier on a cut. agent 0 unions every edge and claims the instant S and T
//     connect. Because agent 0 acts once per round and ~60% of its rounds at low A
//     are otherwise-empty polls (walkers still mid-probe), it fills those rounds
//     with its own greedy DFS toward T; that also guarantees progress if the fleet
//     ever stalls (no pending work), which a message-only broker would deadlock on.
//     A finished walker folds its "I'm free" signal into its last report (EF/TF/F)
//     rather than a separate Q, saving agent 0 one receive round per task.
//
//   SCAN (parallel passage scan) — throughput-bound, ~P/(A-1) turns.
//     Wins when agents are plentiful. Probers own disjoint passage stripes and
//     ship the open ones to agent 0, which unions and claims on connect. Each prober
//     sweeps its stripe nearest-the-diagonal first (a growing band): the S-T path hugs
//     the diagonal, so agent 0 usually connects before the whole map is scanned. The
//     full stripe is still covered, so a far-wandering path stays correct, just slower.
//
// Every agent makes the same deterministic choice, so all agree on the protocol.
// Score = max turns any agent took at the claim (fewer is better).
#include <cstdio>
#include <vector>
#include <string>
#include <queue>
#include <algorithm>
#include <cstdlib>
#include <cstdarg>
using namespace std;

static int N, A, ID, MSG, m;
static long long DN, P;
// Self-assignment enable, decided once in main() (deterministic from N,A,m so walker + aggregator
// agree). Gated to the agent0-saturated mid-N/mid-A regime where DIRECTED's serial dispatch starves
// walkers; there they self-probe SCAN-style instead. See main().
static int g_self=0;

// Env-overridable tuning knob (same value across all agents; merlin shares env).
static int ENVI(const char*k,int dv){ const char*v=getenv(k); return v?atoi(v):dv; }

// ---- opt-in visualizer log (off unless env D_VIZLOG names a directory) --------
// Records this agent's INTERNAL intent (role, aggregator queue depth, dispatch
// targets, walker task assignments) that merlin's event log cannot see. Writes to
// a per-agent side file, never stdout, so the protocol and turn counts are
// byte-for-byte identical to a non-logging build. `g_turn` tracks merlin's global
// turn: it is (readline calls - 1), i.e. 0 after the startup line and t after the
// reply to the command issued at turn t, so the command about to be issued is turn
// g_turn+1 (see the interaction protocol: one command + one reply per turn).
static FILE* g_vz=nullptr;
static long g_turn=0;
static void vzlog(const char*fmt,...){
    if(!g_vz) return;
    va_list ap; va_start(ap,fmt); vfprintf(g_vz,fmt,ap); va_end(ap);
    fputc('\n',g_vz);
}

static string readline(){
    static long rlc=0; g_turn = rlc++;   // rlc counts reads; call k -> g_turn=k-1
    string s; int ch;
    while((ch=getchar())!=EOF && ch!='\n') s.push_back((char)ch);
    if(ch==EOF && s.empty()) exit(0);
    return s;
}
static inline int rid(int i,int j){return i*m+j;}
static const int di[4]={-1,1,0,0}, dj[4]={0,0,-1,1};   // U D L R ; opposite = d^1

// Global passage index for the edge leaving room (i,j) in direction d.
static inline long long pidx(int i,int j,int d){
    switch(d){
        case 1: return (long long)i*m+j;              // Down
        case 0: return (long long)(i-1)*m+j;          // Up
        case 3: return DN + (long long)i*(m-1)+j;     // Right
        default:return DN + (long long)i*(m-1)+(j-1); // Left
    }
}
static inline void pcell(int i,int j,int d,int&pr,int&pc){ pr=2*i+1+di[d]; pc=2*j+1+dj[d]; }
// Decode a passage index to its two rooms and the ULDR chars for each direction.
static inline void decode(long long idx,int&ra,int&rb,char&ca,char&cb,int&pr,int&pc){
    if(idx<DN){ int i=idx/m,j=idx%m; ra=rid(i,j); rb=rid(i+1,j); ca='D'; cb='U'; pr=2*i+2; pc=2*j+1; }
    else{ long long r=idx-DN; int i=r/(m-1),j=r%(m-1); ra=rid(i,j); rb=rid(i,j+1); ca='R'; cb='L'; pr=2*i+1; pc=2*j+2; }
}

// ---- shared aggregator state + claim -----------------------------------------
static vector<int> par; static vector<char> rnk; static vector<char> seen;
static vector<vector<pair<int,char>>> adj;
// Per-root running centroid of the confirmed rooms in each component (D_CENTROID). csi/csj/csz
// are only meaningful at a uf root; uf_unite folds child into parent so a component's centroid
// is (csi/csz, csj/csz). Lets a task exploring toward the opposite tree aim at that tree's
// current mass instead of a fixed corner.
static vector<long long> csi, csj; static vector<int> csz;
static int uf_find(int x){ while(par[x]!=x){ par[x]=par[par[x]]; x=par[x]; } return x; }
static void uf_unite(int a,int b){ a=uf_find(a); b=uf_find(b); if(a!=b){ if(rnk[a]<rnk[b])swap(a,b); par[b]=a; csi[a]+=csi[b]; csj[a]+=csj[b]; csz[a]+=csz[b]; if(rnk[a]==rnk[b])rnk[a]++; } }
static void mark_seen(int r){ if(!seen[r]){ seen[r]=1; int root=uf_find(r); csi[root]+=r/m; csj[root]+=r%m; csz[root]++; } }
static void ingest(long long idx){ int ra,rb,pr,pc; char ca,cb; decode(idx,ra,rb,ca,cb,pr,pc);
    adj[ra].push_back({rb,ca}); adj[rb].push_back({ra,cb}); mark_seen(ra); mark_seen(rb); uf_unite(ra,rb); }
static void agg_init(){ par.resize(m*m); rnk.assign(m*m,0); for(int i=0;i<m*m;i++)par[i]=i; adj.assign(m*m,{}); seen.assign(m*m,0); csi.assign(m*m,0); csj.assign(m*m,0); csz.assign(m*m,0); }
// BFS S->T over confirmed edges, expand each room-step x2, claim.
static void claim_path(){
    const int S=rid(0,0), T=rid(m-1,m-1);
    vector<int> ppar(m*m,-2); vector<char> pdir(m*m,0);
    vector<int> q; q.push_back(S); ppar[S]=-1;
    for(size_t h=0;h<q.size();h++){ int u=q[h]; if(u==T)break;
        for(auto&e:adj[u]) if(ppar[e.first]==-2){ ppar[e.first]=u; pdir[e.first]=e.second; q.push_back(e.first);} }
    string moves,rev; { int cur=T; while(cur!=S && cur>=0){ rev.push_back(pdir[cur]); cur=ppar[cur]; }
        for(int i=(int)rev.size()-1;i>=0;i--){ moves.push_back(rev[i]); moves.push_back(rev[i]); } }
    printf("! %s\n",moves.c_str()); fflush(stdout);
}

// ============================== SCAN ==========================================
static void run_scan(){
    const int S=rid(0,0), T=rid(m-1,m-1);
    if(ID!=0 && A>1){                          // prober: own passages idx % (A-1) == ID-1
        int stripe=A-1, off=ID-1; string batch; int cnt=0; const int BATCH=ENVI("D_SBATCH",34);
        auto flush=[&](){ if(!cnt)return; printf("> 0 %s\n",batch.c_str()); fflush(stdout); readline(); batch.clear(); cnt=0; };
        // Probe order within the stripe. Default: index order. With D_DIAG, probe passages
        // nearest the main diagonal first (a growing band), since the S-T path tends to hug the
        // diagonal, so agent 0 can connect before the whole map is scanned. Still covers the
        // entire stripe, so correctness is unchanged even for a far-wandering path.
        auto diagkey=[&](long long idx)->int{
            int i,j; if(idx<DN){ i=idx/m; j=idx%m; } else { long long r=idx-DN; i=r/(m-1); j=r%(m-1); }
            return i>j? i-j : j-i;
        };
        vector<long long> order;
        for(long long idx=off; idx<P; idx+=stripe) order.push_back(idx);
        if(ENVI("D_DIAG",1)) sort(order.begin(),order.end(),
                                  [&](long long a,long long b){ return diagkey(a)<diagkey(b); });
        for(long long idx: order){
            int ra,rb,pr,pc; char ca,cb; decode(idx,ra,rb,ca,cb,pr,pc);
            printf("? %d %d\n",pr,pc); fflush(stdout); string s=readline();
            if(!s.empty()&&s[0]=='1'){ if(cnt)batch.push_back(' '); batch+=to_string(idx); if(++cnt>=BATCH)flush(); }
        }
        flush(); printf("halt\n"); fflush(stdout); return;
    }
    agg_init();
    if(A==1){ for(long long idx=0;idx<P;idx++){ int ra,rb,pr,pc;char ca,cb; decode(idx,ra,rb,ca,cb,pr,pc);
                printf("? %d %d\n",pr,pc); fflush(stdout); string s=readline(); if(!s.empty()&&s[0]=='1') ingest(idx); } }
    else {
        while(uf_find(S)!=uf_find(T)){
            printf("< ?\n"); fflush(stdout); string s=readline();
            if(s.size()<2||s[0]=='-') continue;
            size_t sp=s.find(' '); if(sp==string::npos) continue;
            const char* p=s.c_str()+sp+1;
            while(*p){ while(*p==' ')p++; if(!*p)break; char*e; long long idx=strtoll(p,&e,10); if(e==p)break; ingest(idx); p=e; }
        }
    }
    claim_path();
}

// ============================== DIRECTED ======================================
static vector<int> vis; static int gen=0;
struct Frame { int i,j; int ord[4]; int k; int forb; };
static void run_directed(){
    const int S=rid(0,0), T=rid(m-1,m-1);
    if(ID!=0 && A>1){                          // walker
        vis.assign(m*m,-1);
        // Persistent per-walker probe cache (passage state is immutable): a walker
        // never re-probes or re-reports a passage it has already seen across tasks.
        vector<unsigned char> pcache((size_t)P,0);   // 0 unknown,1 open,2 closed
        string ebuf; int ecnt=0;
        auto esend=[&](){ if(!ecnt)return; string body="E "+ebuf; printf("> 0 %s\n",body.c_str()); fflush(stdout); readline(); ebuf.clear(); ecnt=0; };
        auto orderDirs=[&](int i,int j,int gi,int gj,int ord[4]){
            int cost[4];
            for(int d=0;d<4;d++){ int ni=i+di[d],nj=j+dj[d];
                cost[d]=(ni<0||nj<0||ni>=m||nj>=m)?(1<<30):abs(ni-gi)+abs(nj-gj); ord[d]=d; }
            for(int a=0;a<4;a++)for(int b=a+1;b<4;b++) if(cost[ord[b]]<cost[ord[a]]){int t=ord[a];ord[a]=ord[b];ord[b]=t;}
        };
        // No registration handshake: agent 0 pre-seeds every walker as idle (all are alive at
        // game start), so a walker goes straight to polling for its first task.
        const int BUDGET=ENVI("D_BUDGET",128);   // finer tasks load-balance better; batching (TBATCH) pays the extra per-task message cost
        // Adaptive E-batch: in the self-assign regime pack as many indices as fit in MAX_MSG_LEN so
        // agent0 reads fewer report messages. Keep the tuned 28 elsewhere (bigger batches delay edge
        // propagation, the dominant cost in the probe-bound regime).
        int pdig=1; for(long long t=P;t>=10;t/=10) pdig++;
        int ebauto=(MSG-4)/(pdig+1); if(ebauto<8) ebauto=8;
        const int EBATCH=ENVI("D_EBATCH", g_self? ebauto : 28);
        // tbuf (leftover-frontier report) and lq (local task queue) persist ACROSS the tasks of one
        // dispatched batch, so a multi-task batch reports its frontier + free-signal in aggregate.
        string tbuf; int tcnt=0;
        auto tflush=[&](){ if(!tcnt)return; string body="T "+tbuf; printf("> 0 %s\n",body.c_str()); fflush(stdout); readline(); tbuf.clear(); tcnt=0; };
        auto tpush=[&](int r,int mask,int g){ if(tcnt)tbuf.push_back(' '); tbuf+=to_string(r); tbuf.push_back(' '); tbuf+=to_string(mask); tbuf.push_back(' '); tbuf+=to_string(g); if(++tcnt>=16) tflush(); };
        // The broker prepends the budget for THIS dispatch (it owns the QADAPT/warmup policy — it knows
        // the queue depth and how many walkers are still idle). A starved queue -> smaller budget so the
        // walker reports frontier back fast and refills the queue, killing the early starvation where the
        // 2 seed tasks can't feed A-1 walkers for a full BUDGET of probes.
        vector<int> lq; size_t lqi=0; int cur_bud=BUDGET;  // per-batch budget from the broker; 5-tuples (r,mask,g,gi,gj)
        // SELF-ASSIGN: probe an own disjoint passage stripe (idx % nw == wk) diagonal-first from round 1,
        // streaming open edges like SCAN (no first-dispatch round-trip, no idle wait). Every passage is
        // covered by exactly one walker, so this alone is complete; the directed task loop below runs after
        // as cleanup + claim path. Removes agent0's serial dispatch bottleneck in the saturated regime.
        if(g_self){
            int nw=A-1, wk=ID-1;
            auto diagkey=[&](long long idx)->int{ int i,j; if(idx<DN){i=idx/m;j=idx%m;} else {long long r=idx-DN;i=r/(m-1);j=r%(m-1);} return i>j?i-j:j-i; };
            vector<long long> order; for(long long idx=wk; idx<P; idx+=nw) order.push_back(idx);
            sort(order.begin(),order.end(),[&](long long a,long long b){return diagkey(a)<diagkey(b);});
            for(long long idx: order){ unsigned char &cst=pcache[idx]; if(cst) continue;
                int ra,rb,pr,pc; char ca,cb; decode(idx,ra,rb,ca,cb,pr,pc);
                printf("? %d %d\n",pr,pc); fflush(stdout); string s=readline();
                bool open=(!s.empty()&&s[0]=='1'); cst=open?1:2;
                if(open){ if(ecnt)ebuf.push_back(' '); ebuf+=to_string(idx); if(++ecnt>=EBATCH) esend(); } }
            esend(); printf("> 0 F\n"); fflush(stdout); readline();   // done: report free, fall through to cleanup
        }
        while(true){
            if(lqi>=lq.size()){                     // local queue drained: refill from one (maybe multi-task) message
                lq.clear(); lqi=0;
                string as;
                while(true){ printf("< 0\n"); fflush(stdout); as=readline(); if(!as.empty()&&as[0]!='-') break; }
                char* p=(char*)as.c_str(); strtol(p,&p,10); while(*p==' ')p++;   // skip sender id
                if(*p!='A') continue; p++;
                while(*p==' ')p++; cur_bud=strtol(p,&p,10);   // broker-chosen budget for this dispatch
                while(*p){ while(*p==' ')p++; if(!*p)break; char*e;
                    int r=strtol(p,&e,10); if(e==p)break; p=e; while(*p==' ')p++;
                    int mk=strtol(p,&e,10); p=e; while(*p==' ')p++;
                    int g=strtol(p,&e,10); p=e; while(*p==' ')p++;
                    int gi=strtol(p,&e,10); p=e; while(*p==' ')p++;
                    int gj=strtol(p,&e,10); p=e;
                    lq.push_back(r); lq.push_back(mk); lq.push_back(g); lq.push_back(gi); lq.push_back(gj); }
                if(lq.empty()) continue;
            }
            int rr=lq[lqi], mm=lq[lqi+1], gg=lq[lqi+2], gi=lq[lqi+3], gj=lq[lqi+4]; lqi+=5;
            vzlog("{\"turn\":%ld,\"ev\":\"task\",\"id\":%d,\"r\":%d,\"goal\":%d,\"budget\":%d}",
                  g_turn+1,ID,rr,gg,BUDGET);
            gen++;
            vector<Frame> st;
            { Frame fr; fr.i=rr/m; fr.j=rr%m; fr.forb=mm; fr.k=0; orderDirs(fr.i,fr.j,gi,gj,fr.ord); st.push_back(fr); vis[rr]=gen; }
            int budget = cur_bud>0 ? cur_bud : BUDGET;
            while(!st.empty() && budget>0){
                int top=(int)st.size()-1; bool descended=false;
                while(st[top].k<4){
                    int ci=st[top].i, cj=st[top].j; int d=st[top].ord[st[top].k++];
                    if(st[top].forb&(1<<d)) continue;
                    int ni=ci+di[d], nj=cj+dj[d];
                    if(ni<0||nj<0||ni>=m||nj>=m) continue;
                    int nr=rid(ni,nj); if(vis[nr]==gen) continue;
                    long long idx=pidx(ci,cj,d);
                    unsigned char &cst=pcache[idx];
                    bool open;
                    if(cst){                                   // cache hit: no turn, already reported by us
                        open=(cst==1);
                    } else {                                   // cache miss: probe (costs a turn), report if open
                        int pr,pc; pcell(ci,cj,d,pr,pc); budget--;
                        printf("? %d %d\n",pr,pc); fflush(stdout); string s=readline();
                        open=(!s.empty()&&s[0]=='1'); cst=open?1:2;
                        if(open){ if(ecnt)ebuf.push_back(' '); ebuf+=to_string(idx); if(++ecnt>=EBATCH) esend(); }
                    }
                    if(open){
                        vis[nr]=gen;
                        Frame ch; ch.i=ni; ch.j=nj; ch.forb=(1<<(d^1)); ch.k=0; orderDirs(ni,nj,gi,gj,ch.ord);
                        st.push_back(ch); descended=true; break;
                    }
                    if(budget<=0) break;
                }
                if(descended) continue;
                if(st.back().k>=4) st.pop_back(); else break;
            }
            if(budget<=0){
                for(auto &fr: st){
                    bool has=false;
                    for(int t=fr.k;t<4;t++){ int d=fr.ord[t]; int ni=fr.i+di[d],nj=fr.j+dj[d];
                        if(ni<0||nj<0||ni>=m||nj>=m) continue; if(vis[rid(ni,nj)]==gen) continue; has=true; }
                    if(!has) continue;
                    int mask=fr.forb; for(int t=0;t<fr.k;t++) mask|=(1<<fr.ord[t]);
                    tpush(rid(fr.i,fr.j), mask, gg);
                }
            }
            if(lqi<lq.size()) continue;   // more tasks queued in this batch: defer report+free, keep E/T buffered
            // Batch drained. Fold the "I'm free" signal into the final report (EF/TF/F) instead of a
            // separate Q, so agent 0 spends ONE re-dispatch round per BATCH, not per task. Mid-batch
            // flushes stayed plain E/T; only this last message per batch is terminal.
            {
                auto sendf=[&](const char*tg,const string&buf){ string body=string(tg)+(buf.empty()?"":(" "+buf)); printf("> 0 %s\n",body.c_str()); fflush(stdout); readline(); };
                if(ecnt && tcnt){ esend(); sendf("TF",tbuf); tbuf.clear(); tcnt=0; }
                else if(ecnt){ sendf("EF",ebuf); ebuf.clear(); ecnt=0; }
                else if(tcnt){ sendf("TF",tbuf); tbuf.clear(); tcnt=0; }
                else { sendf("F",""); }
            }
        }
    }

    // ---- aggregator (agent 0) ----------------------------------------------
    agg_init();
    if(A==1){ for(long long idx=0;idx<P;idx++){ int ra,rb,pr,pc;char ca,cb; decode(idx,ra,rb,ca,cb,pr,pc);
                printf("? %d %d\n",pr,pc); fflush(stdout); string s=readline(); if(!s.empty()&&s[0]=='1') ingest(idx); } claim_path(); return; }

    // Score = rounds until agent 0 claims, and agent 0 acts once per round. Profiling shows
    // ~60% of its rounds at low/mid A are EMPTY `< ?` polls (walkers still mid-probe), so the
    // dominant lever is to spend those rounds probing the path itself (see self_step below).
    // BURST/BRIDGE are env-overridable for hill-climbing; the defaults are the shipped tuning.
    auto envi=[&](const char*k,int dv){ const char*v=getenv(k); return v?atoi(v):dv; };
    const int BURST = envi("D_BURST", g_self?8:4);    // agent-0 self-probes per empty poll; self-assign frees agent0 to probe more
    const int BR    = envi("D_BRIDGE",1);    // prioritize BRIDGE tasks (near a component meet)
    const int TBATCH= envi("D_TBATCH",4);    // max tasks packed per dispatch message (1 = one at a time)
    const int CENTROID = envi("D_CENTROID",1);   // aim a task at the opposite tree's centroid, not its corner
    const int SPLIT = envi("D_SPLIT",0);         // split the 2 corner seeds by direction to feed >2 walkers at round 1
    const int PRUNE = envi("D_PRUNE",1);         // agent0 self-DFS skips classify-dead pockets; scan_step is the completeness fallback
    // Broker-owned walker-budget policy. QADAPT: shrink budget to QSMALL when the queue can't feed all
    // walkers (qrem<QLOW) so frontier flows back fast. WARMUP: while walkers are STILL waiting after this
    // dispatch, hand out a tiny BWARM budget so the lead walker reports its real discovered branches within
    // ~BWARM turns (vs QSMALL) -- cuts the round-1 fan-out latency without the tree wrong-subtree commit.
    const int BUDGET = envi("D_BUDGET",128);
    const int QADAPT = envi("D_QADAPT",1), QLOW = envi("D_QLOW",A-1), QSMALL = envi("D_QSMALL",64);
    const int WARMUP = envi("D_WARMUP",0), BWARM = envi("D_BWARM",16);

    // Goal a task with tree-tag g heads toward: g=1 (S-tree) -> T's component, g=0 -> S's. With
    // D_CENTROID that goal is the opposite component's current room-centroid (homes the two fronts
    // onto each other's growing mass); otherwise the fixed opposite corner (shipped behavior).
    if(CENTROID){ mark_seen(S); mark_seen(T); }   // seed so centroids start at the corners
    auto goalof=[&](int g,int&gi,int&gj){
        int anchor = g?T:S;
        if(CENTROID){ int root=uf_find(anchor); if(csz[root]>0){ gi=(int)(csi[root]/csz[root]); gj=(int)(csj[root]/csz[root]); return; } }
        gi = anchor/m; gj = anchor%m;
    };

    struct Task{int r,mask,g;};
    auto prio=[&](int r,int g){ int gi,gj; goalof(g,gi,gj); int i=r/m,j=r%m; return abs(i-gi)+abs(j-gj); };
    auto cmp=[&](const Task&a,const Task&b){return prio(a.r,a.g)>prio(b.r,b.g);};
    priority_queue<Task,vector<Task>,decltype(cmp)> Q(cmp);   // frontier tasks, closest-to-goal first
    // Seed tasks. The 2 corner seeds (S,T) starve any walker past the 2nd until the first budget-cut
    // frontier report (~QSMALL turns). With >2 walkers, SPLIT seeds one task per in-bounds exit of S and
    // T instead: a corner's exit-subtrees are disjoint in a tree, so this is complete + non-redundant,
    // feeds up to 4 walkers at round 1, and keeps both endpoints (bidirectional search) represented.
    if(SPLIT && A-1>=3){
        for(int d=0;d<4;d++){ int ni=di[d],nj=dj[d]; if(ni>=0&&nj>=0&&ni<m&&nj<m) Q.push({S,(~(1<<d))&0xF,1}); }
        for(int d=0;d<4;d++){ int ni=(m-1)+di[d],nj=(m-1)+dj[d]; if(ni>=0&&nj>=0&&ni<m&&nj<m) Q.push({T,(~(1<<d))&0xF,0}); }
    } else { Q.push({S,0,1}); Q.push({T,0,0}); }
    vector<int> idle;
    // All walkers are alive and idle at game start, so pre-register the pool instead of waiting for
    // each to send a `Q` handshake: saves the walkers' first round and the A-1 rounds agent 0 would
    // otherwise spend draining registrations before it can dispatch the S->T and T->S seed tasks.
    // With self-assign ON, walkers are busy probing their own stripe from round 1, so agent0 starts with
    // an EMPTY idle pool and learns a walker is free only from its terminal F report.
    if(!g_self) for(int w=1; w<A; w++) idle.push_back(w);

    // Enclosure classify over UNCONFIRMED rooms out of r, capped at KCAP:
    //   DEAD   (1): bounded and reconnects ONLY to r's own component -> a sealed pocket the
    //               true path can't enter (tree leave-once); drop the task.
    //   BRIDGE (2): reaches a DIFFERENT confirmed component within the cap -> r sits between
    //               two fronts, so exploring it may complete the S-T meet or seal a pocket
    //               that then prunes; raise its priority.
    //   NORMAL (0): escaped the cap (unknown-large region) or r not yet confirmed.
    // Keyed on r's OWN component (not the goal's), so it is safe under out-of-order messages.
    vector<int> fvis(m*m,0); int fgen=0; vector<int> fq; fq.reserve(m*m);
    const int KCAP = 12*m + 64;
    auto classify=[&](int r)->int{
        if(!seen[r]) return 0;                          // r not yet confirmed: NORMAL (safe)
        int rc=uf_find(r);
        fgen++; fq.clear();
        int ri=r/m, rj=r%m;
        for(int d=0;d<4;d++){ int ni=ri+di[d],nj=rj+dj[d]; if(ni<0||nj<0||ni>=m||nj>=m)continue;
            int nr=rid(ni,nj); if(seen[nr]||fvis[nr]==fgen)continue; fvis[nr]=fgen; fq.push_back(nr); }
        int head=0;
        while(head<(int)fq.size()){
            if(head>KCAP) return 0;                     // escaped cap: NORMAL
            int u=fq[head++]; int ui=u/m, uj=u%m;
            for(int d=0;d<4;d++){ int vi=ui+di[d],vj=uj+dj[d]; if(vi<0||vj<0||vi>=m||vj>=m)continue;
                int v=rid(vi,vj);
                if(seen[v]){ if(uf_find(v)!=rc) return 2; }   // reaches another comp: BRIDGE
                else if(fvis[v]!=fgen){ fvis[v]=fgen; fq.push_back(v); } }
        }
        return 1;                                        // bounded, only own comp: DEAD
    };

    // Is the UNSEEN room (ni,nj) inside a DEAD pocket? Flood unseen rooms from it (cap KCAP); dead iff
    // bounded and its seen boundary touches <=1 component (a hanging subtree that holds no new S-T spine).
    // Lets agent0's self-DFS skip pockets its own global map already proves dead. classify is not sound
    // on its own, so scan_step is the completeness fallback if this over-prunes.
    auto dead_target=[&](int ni,int nj)->bool{
        int start=rid(ni,nj);
        if(seen[start]) return false;                    // already confirmed: probing it may be a BRIDGE
        fgen++; fq.clear(); fvis[start]=fgen; fq.push_back(start);
        int head=0, comp=-1;
        while(head<(int)fq.size()){
            if(head>KCAP) return false;                  // escaped cap: NORMAL (unknown-large)
            int u=fq[head++]; int ui=u/m, uj=u%m;
            for(int d=0;d<4;d++){ int vi=ui+di[d],vj=uj+dj[d]; if(vi<0||vj<0||vi>=m||vj>=m)continue;
                int v=rid(vi,vj);
                if(seen[v]){ int cc=uf_find(v); if(comp<0)comp=cc; else if(cc!=comp) return false; }  // 2 comps: BRIDGE
                else if(fvis[v]!=fgen){ fvis[v]=fgen; fq.push_back(v); } }
        }
        return true;                                     // bounded, <=1 boundary component: DEAD pocket
    };

    // Greedy direction order toward (gi,gj); nearest-first, then hug the diagonal band. The S-T path
    // hugs the main diagonal, so among dirs of EQUAL goal-distance, preferring the one nearer the diagonal
    // steers agent0's self-DFS (its dominant probe source at low A) down the true corridor. OTIE keeps it
    // a pure tie-break (dist*4096+pen) so it never overrides goal progress; OBAND exempts a band half-width.
    const int OTIE = envi("D_OTIE",1);
    const int WBAND = envi("D_OBAND",4);
    const int WDIAGW = envi("D_ODIAGW",0);
    auto o0=[&](int i,int j,int gi,int gj,int ord[4]){
        int cost[4];
        for(int d=0;d<4;d++){ int ni=i+di[d],nj=j+dj[d];
            if(ni<0||nj<0||ni>=m||nj>=m){ cost[d]=(1<<30); }
            else { int dist=abs(ni-gi)+abs(nj-gj); int off=ni>nj?ni-nj:nj-ni; int pen=off>WBAND?off-WBAND:0;
                   cost[d]= OTIE ? dist*4096+pen : dist+WDIAGW*pen; }
            ord[d]=d; }
        for(int a=0;a<4;a++)for(int b=a+1;b<4;b++) if(cost[ord[b]]<cost[ord[a]]){int t=ord[a];ord[a]=ord[b];ord[b]=t;}
    };

    // agent-0 self-search: a greedy DFS from S toward T that probes one frontier passage per
    // call, run only in rounds that would otherwise be an empty poll. Its probes union directly
    // (no message round), so idle aggregator time becomes path progress and a walker stall can't
    // deadlock the run. Correctness rests on the union-find + claim_path BFS, so a suboptimal
    // self-DFS only costs speed, never a wrong path. Edges walkers report are marked in a0c, so
    // the self-DFS rides confirmed structure for free and probes only the true leading edge.
    vector<int> a0vis(m*m,0); const int A0G=1;
    vector<unsigned char> a0c((size_t)P,0);              // 0 unknown,1 open,2 closed
    vector<Frame> a0st;
    { Frame fr; fr.i=0; fr.j=0; fr.k=0; fr.forb=0; int gti,gtj; goalof(1,gti,gtj); o0(0,0,gti,gtj,fr.ord); a0st.push_back(fr); a0vis[S]=A0G; }
    auto self_step=[&]()->bool{                          // true iff it consumed a round (probed)
        int gti,gtj; goalof(1,gti,gtj);                  // agent-0 self-DFS aims at T's tree (corner or, w/ D_CENTROID, its centroid)
        while(!a0st.empty()){
            Frame &f=a0st.back();
            bool descended=false;
            while(f.k<4){
                int d=f.ord[f.k];
                int ci=f.i, cj=f.j, ni=ci+di[d], nj=cj+dj[d];
                if((f.forb&(1<<d))||ni<0||nj<0||ni>=m||nj>=m){ f.k++; continue; }
                int nr=rid(ni,nj);
                if(a0vis[nr]==A0G){ f.k++; continue; }
                long long idx=pidx(ci,cj,d);
                unsigned char st=a0c[idx];
                if(st==2){ f.k++; continue; }
                if(PRUNE && st==0 && dead_target(ni,nj)){ f.k++; continue; }   // skip dead pocket (scan_step recovers if over-pruned)
                f.k++;
                if(st==1){                               // known open: descend without a probe
                    a0vis[nr]=A0G;
                    Frame ch; ch.i=ni; ch.j=nj; ch.forb=(1<<(d^1)); ch.k=0; o0(ni,nj,gti,gtj,ch.ord);
                    a0st.push_back(ch); descended=true; break;
                }
                int pr,pc; pcell(ci,cj,d,pr,pc);         // unknown: probe (one round)
                vzlog("{\"turn\":%ld,\"ev\":\"self\",\"id\":0,\"pr\":%d,\"pc\":%d}",g_turn+1,pr,pc);
                printf("? %d %d\n",pr,pc); fflush(stdout); string s=readline();
                bool open=(!s.empty()&&s[0]=='1'); a0c[idx]=open?1:2;
                if(open){ ingest(idx); a0vis[nr]=A0G;
                          Frame ch; ch.i=ni; ch.j=nj; ch.forb=(1<<(d^1)); ch.k=0; o0(ni,nj,gti,gtj,ch.ord); a0st.push_back(ch); }
                return true;
            }
            if(descended) continue;
            if(a0st.back().k>=4) a0st.pop_back();
        }
        return false;                                    // frontier exhausted: nothing to probe
    };

    // Completeness fallback for PRUNE: when the self-DFS has exhausted its non-pruned frontier AND the
    // fleet is stalled (nothing to dispatch or receive), linearly probe the next unprobed passage. This
    // guarantees the S-T link is eventually found even if dead_target over-pruned the only route, so the
    // self-DFS prune can never livelock (the failure mode the plain classify prune has without a fallback).
    long long a0scan=0;
    auto scan_step=[&]()->bool{
        while(a0scan<P){ long long idx=a0scan++; if(a0c[idx]==0){
            int ra,rb,pr,pc; char ca,cb; decode(idx,ra,rb,ca,cb,pr,pc);
            printf("? %d %d\n",pr,pc); fflush(stdout); string s=readline();
            bool open=(!s.empty()&&s[0]=='1'); a0c[idx]=open?1:2; if(open) ingest(idx);
            return true; } }
        return false;
    };

    // Pick the next task off the global queue for an idle walker: pop the closest-to-goal
    // task, drop it if DEAD, and (with BR) look a few deeper for a BRIDGE task to run first
    // since exploring near a component meet either completes the S-T join or seals a prunable
    // pocket. Affinity/work-stealing was tried and measured worse: frontier-rooted tasks give
    // walkers almost no region to reuse a probe cache over, and pinning a walker to its own
    // frontier sacrifices the global closest-to-goal ordering that dominates the score.
    auto pick=[&](Task&out)->bool{
        while(!Q.empty()){
            Task t=Q.top(); Q.pop();
            int c=classify(t.r);
            if(c==1) continue;                        // dead pocket: drop
            if(BR && c!=2){                           // prefer a BRIDGE task if one is near the top
                Task keep=t; vector<Task> stash;
                for(int k=0;k<6 && !Q.empty();k++){
                    Task u=Q.top(); Q.pop(); int cu=classify(u.r);
                    if(cu==1) continue;               // drop dead while scanning
                    if(cu==2){ for(auto&z:stash)Q.push(z); Q.push(keep); out=u; return true; }
                    stash.push_back(u);
                }
                for(auto&z:stash)Q.push(z);
                out=keep; return true;
            }
            out=t; return true;
        }
        return false;
    };

    while(uf_find(S)!=uf_find(T)){
        // 1. Assign work to an idle walker if any is available (a productive round).
        if(!idle.empty()){
            // Batch up to K tasks into one dispatch message. K grows with the task SURPLUS
            // (Q.size()/(A-1)), so extra tasks are reserved to a walker only when there's a backlog;
            // K=1 when the queue is tight, which preserves the global closest-to-goal ordering that
            // dominates the score (per-walker affinity was measured harmful). Each task is 5 fields
            // (r mask g gi gj); cap K at 12 to stay under the 256-byte limit. The message is prefixed
            // with the broker's REMAINING queue size (the QADAPT starvation signal for walkers).
            Task t;
            if(pick(t)){
                int K=TBATCH; { int share=(int)Q.size()/(A-1); if(share<1)share=1; if(K>share)K=share; } if(K>12)K=12;
                int w=idle.back(); idle.pop_back();
                vector<Task> batch; batch.push_back(t);
                for(int c=1;c<K;c++){ Task u; if(!pick(u))break; batch.push_back(u); }
                int qrem=(int)Q.size();
                int bud = (QADAPT && qrem < QLOW) ? QSMALL : BUDGET;
                if(WARMUP && !idle.empty() && qrem < QLOW && bud > BWARM) bud = BWARM;   // walkers still waiting: fan out fast
                string body="A "+to_string(bud);
                for(auto&x:batch){ int gi,gj; goalof(x.g,gi,gj);
                    body+=" "+to_string(x.r)+" "+to_string(x.mask)+" "+to_string(x.g)+" "+to_string(gi)+" "+to_string(gj); }
                vzlog("{\"turn\":%ld,\"ev\":\"dispatch\",\"id\":0,\"to\":%d,\"r\":%d,\"goal\":%d,\"k\":%d,\"q\":%d,\"idle\":%d}",
                      g_turn+1,w,t.r,t.g,(int)batch.size(),qrem,(int)idle.size());
                printf("> %d %s\n", w, body.c_str()); fflush(stdout); readline(); continue;
            }
        }
        // 2. Poll for one message.
        vzlog("{\"turn\":%ld,\"ev\":\"poll\",\"id\":0,\"q\":%d,\"idle\":%d}",g_turn+1,(int)Q.size(),(int)idle.size());
        printf("< ?\n"); fflush(stdout); string s=readline();
        if(!(s.size()<3||s[0]=='-')){
            char* p=(char*)s.c_str(); int sndr=strtol(p,&p,10);
            while(*p==' ')p++; char tag=*p;
            if(tag){ p++;
                bool fin=false; if(*p=='F'){ fin=true; p++; }   // EF/TF/F = report + "I'm free"
                if(tag=='E'){ while(*p){ while(*p==' ')p++; if(!*p)break; char*e; long long idx=strtoll(p,&e,10); if(e==p)break; ingest(idx); if(idx>=0&&idx<P)a0c[(size_t)idx]=1; p=e; if(uf_find(S)==uf_find(T))break; } }
                else if(tag=='T'){ while(*p){ while(*p==' ')p++; if(!*p)break; char*e;
                        int r=strtol(p,&e,10); if(e==p)break; p=e; while(*p==' ')p++;
                        int mask=strtol(p,&e,10); p=e; while(*p==' ')p++;
                        int g=strtol(p,&e,10); p=e; Q.push({r,mask,g}); } }
                else if(tag=='F'){ fin=true; }         // bare "F" = free with nothing to report
                if(fin && sndr>0 && sndr<A) idle.push_back(sndr);
            }
            continue;
        }
        // 3. Empty poll. If the whole fleet is idle with no work left, only agent 0's own
        // probes can make progress (this is the livelock the plain broker deadlocks on), so
        // self-probe unconditionally. Otherwise self-probe up to BURST times to fill the wait
        // for busy walkers (helps miss-dominated large-N/low-A, off by default elsewhere).
        bool stalled = ((int)idle.size() >= A-1) && Q.empty();
        if(stalled){ if(!self_step() && PRUNE) scan_step(); }   // PRUNE: self-DFS may over-prune; scan_step guarantees progress
        else for(int b=0;b<BURST && uf_find(S)!=uf_find(T); b++){ if(!self_step()) break; }
    }
    claim_path();
}

int main(){
    { string f=readline(); if(sscanf(f.c_str(),"%d %d %d %d",&N,&A,&ID,&MSG)!=4) return 0; }
    if(N==1){ if(ID==0){ printf("! \n"); fflush(stdout);} return 0; }
    m=(N+1)/2; DN=(long long)(m-1)*m; P=2*(long long)(m-1)*m;

    // Visualizer log: one file per agent under $D_VIZLOG. Line-buffered so a line
    // survives even if merlin SIGKILLs the agent right after a claim ends the run.
    if(const char*vd=getenv("D_VIZLOG")){
        char pth[600]; snprintf(pth,sizeof pth,"%s/agent_%d.jsonl",vd,ID);
        g_vz=fopen(pth,"w"); if(g_vz) setvbuf(g_vz,nullptr,_IOLBF,0);
    }

    // Strategy pick (deterministic, identical across all agents).
    // scan costs ~P/(A-1) turns; directed's capability floor ~0.13*m^2 (empirical).
    double scan_est = (A>1) ? (double)P/(A-1) : 1e18;
    double dcap     = 330.0; if(0.13*(double)m*m > dcap) dcap = 0.13*(double)m*m;
    bool useScan = (A<=1) ? true : (scan_est <= dcap);

    // Self-assign gate (deterministic, identical across agents). Enable in the agent0-saturated sweet
    // spot: m>=MMIN (tiny mazes solve too fast for stripe coverage to pay), A>=AMIN (few walkers -> the
    // directed search wins), scan_est<=SCAP (large N -> directed is far more probe-efficient than a stripe
    // scan). Only bites when useScan is false (else run_scan runs). Env D_SELF overrides the whole decision.
    // AMIN=12: A=10-11 measured neutral-to-regressive (directed still wins with few walkers); A>=12 is a
    // clean win across N, growing with A. A>=17 routes to run_scan anyway, so self-assign bites A in [12,16].
    const int SCAP = ENVI("D_SCAP",3000), MMIN = ENVI("D_MMIN",60), AMIN = ENVI("D_AMIN",12);
    g_self = (m>=MMIN && A>=AMIN && scan_est <= SCAP) ? 1 : 0;
    if(getenv("D_SELF")) g_self = atoi(getenv("D_SELF"));

    const char* role = (A<=1)?"SOLO" : (ID==0)?"AGG" : (useScan?"PROBER":"WALKER");
    vzlog("{\"turn\":0,\"ev\":\"start\",\"id\":%d,\"N\":%d,\"A\":%d,\"m\":%d,\"P\":%lld,\"strat\":\"%s\",\"role\":\"%s\"}",
          ID,N,A,m,P, useScan?"SCAN":"DIRECTED", role);

    if(useScan) run_scan(); else run_directed();
    return 0;
}