// 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>
using namespace std;

static int N, A, ID, MSG, m;
static long long DN, P;

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

static string readline(){
    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;
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; if(rnk[a]==rnk[b])rnk[a]++; } }
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}); uf_unite(ra,rb); seen[ra]=1; seen[rb]=1; }
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); }
// 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
        const int EBATCH=ENVI("D_EBATCH",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(); };
        vector<int> lq; size_t lqi=0;               // flattened (r,mask,g) triples from one `A` message
        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){ 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; lq.push_back(r); lq.push_back(mk); lq.push_back(g); }
                if(lq.empty()) continue;
            }
            int rr=lq[lqi], mm=lq[lqi+1], gg=lq[lqi+2]; lqi+=3;
            int gi=gg?(m-1):0, gj=gg?(m-1):0;
            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=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", 4);    // agent-0 self-probes per detected empty poll
    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)

    struct Task{int r,mask,g;};
    auto prio=[&](int r,int g){int i=r/m,j=r%m; int gi=g?(m-1):0,gj=g?(m-1):0; 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
    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.
    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
    };

    // Greedy direction order toward corner (gi,gj); nearest-first.
    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];
            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;}
    };

    // 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; o0(0,0,m-1,m-1,fr.ord); a0st.push_back(fr); a0vis[S]=A0G; }
    auto self_step=[&]()->bool{                          // true iff it consumed a round (probed)
        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; }
                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,m-1,m-1,ch.ord);
                    a0st.push_back(ch); descended=true; break;
                }
                int pr,pc; pcell(ci,cj,d,pr,pc);         // unknown: probe (one round)
                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,m-1,m-1,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
    };

    // 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). Caps: D_TBATCH and 16
            // (the 256-byte message holds ~20 triples; 16 leaves margin).
            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>16)K=16;
                int w=idle.back(); idle.pop_back();
                string body="A "+to_string(t.r)+" "+to_string(t.mask)+" "+to_string(t.g);
                for(int c=1;c<K;c++){ Task u; if(!pick(u))break; body+=" "+to_string(u.r)+" "+to_string(u.mask)+" "+to_string(u.g); }
                printf("> %d %s\n", w, body.c_str()); fflush(stdout); readline(); continue;
            }
        }
        // 2. Poll for one message.
        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){ self_step(); }
        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;

    // 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);

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