// D — v5 hybrid: Vova's mirrored-gossip agent (superior turns, heavy CPU)
// for N < 291; a024_v4 coordinator agent (guaranteed fast) for N >= 291,
// where the mirrored per-phase inference blows the 10%-CPU wall-clock budget.
#include <bits/stdc++.h>
using namespace std;

namespace vova {
// Merlin cooperative maze — adaptive phased bidirectional search.
//
// Rooms sit at odd (r,c) and are always free; only the E candidate wall cells
// between adjacent rooms are unknown. All agents keep an IDENTICAL shared edge
// state, so each phase they deterministically agree on which edges to probe:
// all unknown edges are ranked by prio = 4*(dS+dG) + min(dS,dG), where dS/dG
// are BFS distances (through not-known-closed walls) from the start/goal
// components — an A*-corridor potential field. The top K*Pp edges are split
// round-robin; each agent probes its share, then a Bruck all-gather (ceil(log2
// K) send+read steps) merges everyone's results, followed by perfect-maze
// inference: an unknown edge inside one component must be CLOSED (no cycles),
// and a bridge of the not-closed component graph must be OPEN (connectivity).
// Any agent whose view (shared + own probes) links start to goal claims
// immediately.

static const char B64[] = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789-_";
static int b64inv[256];

int N, K, ID, MAXLEN, m, E;
vector<array<int,2>> eEnds;          // edge -> two room ids
vector<pair<int,int>> wallCell;      // edge -> wall cell (r,c)
vector<vector<int>> incid;           // room -> edge ids
vector<char> is_rel;

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

struct Dsu {
    vector<int> p;
    Dsu(int n=0):p(n){ 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; p[b]=a; return true; }
};

// ---- shared knowledge (identical on every agent after each gossip) ----
vector<char> st_;    // 0 unknown, 1 open, 2 closed
Dsu dsu;
vector<int> tin_, low_; int timer_;
vector<vector<pair<int,int>>> adjC;

void setOpen(int e){ if(st_[e]) return; st_[e]=1; dsu.unite(eEnds[e][0], eEnds[e][1]); }
void setClosed(int e){ if(st_[e]) return; st_[e]=2; }

void dfsBr(int u, int pe){
    tin_[u]=low_[u]=timer_++;
    for(auto& pr : adjC[u]){ int v=pr.first, e=pr.second;
        if(e==pe) continue;
        if(tin_[v]>=0) low_[u]=min(low_[u], tin_[v]);
        else { dfsBr(v,e); low_[u]=min(low_[u], low_[v]);
               if(low_[v]>tin_[u] && !st_[e]) setOpen(e); }
    }
}
void infer(){
    bool ch=true;
    while(ch){ ch=false;
        int opened=0, closed=0;
        int cur_open=0, cur_closed=0;
        for(int e=0;e<E;e++) { if(st_[e]==1)cur_open++; else if(st_[e]==2)cur_closed++; }
        int closed_target = (m-1)*(m-1);
        int open_target = m*(m) - 1;
        if (cur_closed == closed_target && cur_open < open_target) {
            for(int e=0;e<E;e++) if(!st_[e]){ setOpen(e); ++opened; }
        }
        if (cur_open == open_target && cur_open + cur_closed < E) {
            for(int e=0;e<E;e++) if(!st_[e]){ setClosed(e); ++closed; }
        }
        // degree rule: rooms with phys deg, if closed==phys-1 and no open yet -> force last open
        for(int u=0; u<m*m; u++){
            int ii = u / m, jj = u % m;
            int phys = 4;
            if (ii==0 || ii==m-1) phys--;
            if (jj==0 || jj==m-1) phys--;
            if (phys < 2) phys=2;
            int ccls=0, copen=0, unk_id=-1;
            for(int eid : incid[u]){
                if (st_[eid]==2) ccls++;
                else if (st_[eid]==1) copen++;
                else if (unk_id == -1) unk_id = eid;
                else unk_id = -2; // more than1 unk
            }
            if (copen == 0 && ccls == phys-1 && unk_id >=0 && !st_[unk_id]) {
                setOpen(unk_id); ++opened;
            }
        }
        for(int e=0;e<E;e++) if(!st_[e] && dsu.find(eEnds[e][0])==dsu.find(eEnds[e][1])){ setClosed(e); closed++; }
        int R=m*m;
        adjC.assign(R,{}); tin_.assign(R,-1); low_.assign(R,0); timer_=0;
        bool anyU=false;
        for(int e=0;e<E;e++) if(!st_[e]){
            int a=dsu.find(eEnds[e][0]), b=dsu.find(eEnds[e][1]);
            if(a==b) continue;
            adjC[a].push_back({b,e}); adjC[b].push_back({a,e}); anyU=true;
        }
        int stBefore=0; for(int e=0;e<E;e++) if(st_[e]==1) stBefore++;
        if(anyU) for(int r=0;r<R;r++) if(dsu.find(r)==r && tin_[r]<0) dfsBr(r,-1);
        int stAfter=0; for(int e=0;e<E;e++) if(st_[e]==1) stAfter++;
        opened = stAfter - stBefore;
        if(opened || closed) ch=true;
    }
}

void prune() {
    int V = m * m;
    vector<int> deg(V, 0);
    for(int e=0; e<E; e++) if(st_[e] != 2 && is_rel[e]) {
        deg[eEnds[e][0]]++;
        deg[eEnds[e][1]]++;
    }
    queue<int> q;
    for(int u=0; u<V; u++) if(u != 0 && u != V-1 && deg[u] <= 1) q.push(u);
    while(!q.empty()) {
        int u = q.front(); q.pop();
        for(int e: incid[u]) if(st_[e] !=2 && is_rel[e]) {
            is_rel[e] = 0;
            int v = (eEnds[e][0] == u ? eEnds[e][1] : eEnds[e][0]);
            if(--deg[v] <=1 && v !=0 && v != V-1) q.push(v);
        }
    }
}

// claim using currently-open edges (extraOpen: private probe results)
[[noreturn]] void claimAndExit(const vector<int>& extraOpen){
    vector<vector<char>> g(N+2, vector<char>(N+2, 0));
    for(int i=0;i<m;i++) for(int j=0;j<m;j++) g[2*i+1][2*j+1]=1;
    for(int e=0;e<E;e++) if(st_[e]==1) g[wallCell[e].first][wallCell[e].second]=1;
    for(int e : extraOpen) g[wallCell[e].first][wallCell[e].second]=1;
    vector<vector<int>> par(N+2, vector<int>(N+2, -1));
    deque<pair<int,int>> q; q.push_back({1,1}); par[1][1]=4;
    int DR[4]={-1,1,0,0}, DC[4]={0,0,-1,1}; const char MV[4]={'U','D','L','R'};
    while(!q.empty()){
        auto [r,c]=q.front(); q.pop_front();
        if(r==N&&c==N) break;
        for(int d=0;d<4;d++){ int nr=r+DR[d], nc=c+DC[d];
            if(nr>=1&&nr<=N&&nc>=1&&nc<=N&&g[nr][nc]&&par[nr][nc]<0){ par[nr][nc]=d; q.push_back({nr,nc}); } }
    }
    string path;
    int r=N,c=N;
    while(!(r==1&&c==1)){ int d=par[r][c]; path += MV[d]; r-=DR[d]; c-=DC[d]; }
    reverse(path.begin(), path.end());
    cout << "! " << path << "\n" << flush;
    exit(0);
}

int run(const string& first){
    for(int i=0;i<64;i++) b64inv[(unsigned char)B64[i]]=i;
    { istringstream is(first); is >> N >> K >> ID >> MAXLEN; }
    m=(N+1)/2;

    if(m==1){ if(ID==0){ cout << "!\n" << flush; } else cout << "halt\n" << flush; return 0; }

    for(int i=0;i<m;i++) for(int j=0;j<m;j++){
        int node=i*m+j;
        if(j+1<m){ eEnds.push_back({node,node+1}); wallCell.push_back({2*i+1, 2*j+2}); }
        if(i+1<m){ eEnds.push_back({node,node+m}); wallCell.push_back({2*i+2, 2*j+1}); }
    }
    E=(int)eEnds.size();
    incid.assign(m*m, {});
    for(int e=0;e<E;e++){ incid[eEnds[e][0]].push_back(e); incid[eEnds[e][1]].push_back(e); }
    st_.assign(E, 0);
    dsu = Dsu(m*m);
    is_rel.assign(E, 1);

    int start=0, goal=m*m-1;
    int S=0; while((1<<S) < K) S++;                 // gossip steps
    // cap the per-agent batch so the largest gossip message (up to 2^(S-1)
    // blocks of Pmax bits, base64) fits in MAX_MSG_LEN
    int maxBlocks = S>0 ? (1<<(S-1)) : 1;
    long long capBits = (long long)MAXLEN*6;
    int Pmax = (int)min<long long>(32, max<long long>(1, capBits/max(1,maxBlocks) ));

    long long phase=0;
    while(true){
        phase++;
        // ---- deterministic assignment from shared state ----
        auto bfs=[&](int comp, vector<int>& dist){
            dist.assign(m*m, INT_MAX); deque<int> q;
            for(int r=0;r<m*m;r++) if(dsu.find(r)==comp){ dist[r]=0; q.push_back(r); }
            while(!q.empty()){ int r=q.front(); q.pop_front();
                for(int e:incid[r]){ if(st_[e]==2) continue;
                    int o = eEnds[e][0]==r? eEnds[e][1]:eEnds[e][0];
                    if(dist[o]==INT_MAX){ dist[o]=dist[r]+1; q.push_back(o); } } }
        };
        int cs=dsu.find(start), cg=dsu.find(goal);
        vector<int> dS,dG; bfs(cs,dS); bfs(cg,dG);
        vector<pair<long long,int>> cand;
        for(int e=0;e<E;e++) if(!st_[e]){
            long long da=min(dS[eEnds[e][0]], dS[eEnds[e][1]]);
            long long db=min(dG[eEnds[e][0]], dG[eEnds[e][1]]);
            cand.push_back({(da+db)*3 + min(da,db), e});
        }
        sort(cand.begin(), cand.end());
        // batch scales with the current S-G gap: big when far apart, small when
        // close (avoid overshooting past the connection)
        long long gap = min((long long)dS[goal], (long long)dG[start]);
        if(gap > (long long)INT_MAX/2) gap = 2*m;
        long long Pp = max(4LL, min((long long)Pmax, (gap * 3LL + 2)/ 4 ));
        int take = (int)min<long long>((long long)cand.size(), (long long)K*Pp);
        take = (int)min<long long>((long long)cand.size(), (long long)(take+K-1)/K*K); // pad to equal blocks

        // block b = edges at positions b, b+K, ... within [0,take)
        auto blockLen=[&](int b){ return b<take ? (take-b-1)/K + 1 : 0; };

        // ---- probe my block; claim early if my private view links S to G ----
        Dsu priv = dsu;
        vector<int> myOpens;
        int myLen = blockLen(ID);
        vector<char> myBits(myLen, 0);
        for(int t=0;t<myLen;t++){
            int e = cand[ID + (long long)t*K].second;
            string rep = ask("? " + to_string(wallCell[e].first) + " " + to_string(wallCell[e].second));
            if(rep=="1"){
                myBits[t]=1; myOpens.push_back(e);
                priv.unite(eEnds[e][0], eEnds[e][1]);
                if(priv.find(start)==priv.find(goal)) claimAndExit(myOpens);
            }
        }

        // ---- Bruck all-gather of this phase's blocks ----
        vector<vector<char>> blocks(K);
        blocks[ID]=myBits;
        vector<char> have(K,0); have[ID]=1;
        for(int s2=0; s2<S; s2++){
            int cntHeld = min(K, 1<<s2);
            int dst = ((ID - (1<<s2)) % K + K) % K;
            int src = (ID + (1<<s2)) % K;
            // encode my held blocks [ID .. ID+cntHeld) in order
            string body; int acc=0, nb=0;
            for(int i=0;i<cntHeld;i++){
                int b=(ID+i)%K;
                for(char bit : blocks[b]){ acc=(acc<<1)|bit; if(++nb==6){ body+=B64[acc]; acc=0; nb=0; } }
            }
            if(nb) body += B64[acc<<(6-nb)];
            if(body.empty()) body = "A";      // never send an empty body
            ask("> " + to_string(dst) + " " + body);
            // read src's blocks [src .. src+cntHeld)
            string rep;
            while(true){ rep = ask("< " + to_string(src)); if(rep!="- -") break; }
            string bits = rep.substr(rep.find(' ')+1);
            long long bitPos=0;
            for(int i=0;i<cntHeld;i++){
                int b=(src+i)%K;
                int len=blockLen(b);
                if(!have[b]){
                    blocks[b].assign(len,0);
                    for(int t=0;t<len;t++){
                        long long p=bitPos+t;
                        blocks[b][t] = (b64inv[(unsigned char)bits[p/6]] >> (5-p%6)) & 1;
                    }
                    have[b]=1;
                }
                bitPos += len;
            }
        }

        // ---- merge + infer ----
        for(int b=0;b<K;b++){
            int len=blockLen(b);
            for(int t=0;t<len;t++){
                int e = cand[b + (long long)t*K].second;
                if(blocks[b].empty()) continue;
                if(blocks[b][t]) setOpen(e); else setClosed(e);
            }
        }
        infer();
        if(dsu.find(start)==dsu.find(goal)) claimAndExit({});
    }
}

} // namespace vova

namespace mine {
// D — Datacenter Imprisonment, v3 "coordinator-directed adaptive exploration".
//
// Metric = round of the claim (lockstep). Agent 0 = coordinator: global map,
// pooled bidirectional best-first frontier (keys: Euclid distance of the far
// room to the opposite corner, optimistic speculation past in-flight walls).
// Workers 1..K-1: bootstrap-probe a radial static slice, then follow a fixed
// deterministic timetable: recv task batch -> probe q walls -> send packed
// results. Cycle P = q+4 rounds; agent 0 spends 2 rounds per worker per cycle
// (recv+send) and self-probes the rest. Claims as soon as known-open walls
// connect (1,1) and (N,N).

static int N, K, ID, MSGLEN;
static int m, W, HW;   // HW = m*(m-1) horizontal wall count
static int Q_TASK, P_CYCLE, BLOCK1; // worker batch, cycle length, first cycle block start
static int REBUILD_EVERY = 400;

// ---------- wall indexing ----------
static inline pair<int,int> wallCell(int w) {
    if (w < HW) { int i = w / (m - 1), j = w % (m - 1); return {2*i+1, 2*j+2}; }
    int x = w - HW; int i = x / m, j = x % m; return {2*i+2, 2*j+1};
}
static inline void wallRooms(int w, int &a, int &b) {
    if (w < HW) { int i = w / (m - 1), j = w % (m - 1); a = i*m+j; b = a+1; }
    else { int x = w - HW; int i = x / m, j = x % m; a = i*m+j; b = a+m; }
}
static inline int wallOf(int u, int dir) { // 0=D 1=R 2=U 3=L
    int i=u/m, j=u%m;
    switch(dir){
        case 0: return i+1<m ? HW+i*m+j : -1;
        case 1: return j+1<m ? i*(m-1)+j : -1;
        case 2: return i>0 ? HW+(i-1)*m+j : -1;
        case 3: return j>0 ? i*(m-1)+(j-1) : -1;
    }
    return -1;
}
static inline int roomAcross(int u, int dir){
    int i=u/m,j=u%m;
    switch(dir){case 0:return i+1<m?u+m:-1;case 1:return j+1<m?u+1:-1;case 2:return i>0?u-m:-1;default:return j>0?u-1:-1;}
}

// ---------- raw I/O ----------
static char lineBuf[512];
static bool readLine() { return fgets(lineBuf, sizeof lineBuf, stdin) != nullptr; }
static void sendCmd(const char *s) { fputs(s, stdout); fputc('\n', stdout); fflush(stdout); }

// ---------- knowledge ----------
static vector<int8_t> wallSt; // -1 unknown, 0 closed, 1 open
static vector<int> dsu;
static int dsuFind(int x){ while(dsu[x]!=x){ dsu[x]=dsu[dsu[x]]; x=dsu[x]; } return x; }
static void dsuUnite(int a,int b){ a=dsuFind(a); b=dsuFind(b); if(a!=b) dsu[a]=b; }
static bool connectedST() { return dsuFind(0) == dsuFind(m*m - 1); }

static void claimPath() {
    int T = m*m - 1;
    vector<int> par(m*m, -2); par[0] = -1;
    deque<int> q{0};
    while (!q.empty()) {
        int u = q.front(); q.pop_front();
        if (u == T) break;
        for (int dir = 0; dir < 4; dir++) {
            int w = wallOf(u, dir);
            if (w < 0 || wallSt[w] != 1) continue;
            int v = roomAcross(u, dir);
            if (par[v] == -2) { par[v] = u; q.push_back(v); }
        }
    }
    if (par[T] == -2) return;
    string moves;
    for (int v = T; par[v] != -1; v = par[v]) {
        int p = par[v];
        char c = (v == p+1) ? 'R' : (v == p-1) ? 'L' : (v == p+m) ? 'D' : 'U';
        moves += c; moves += c;
    }
    reverse(moves.begin(), moves.end());
    string cmd = "! " + moves;
    sendCmd(cmd.c_str());
    exit(0);
}

// ---------- bit packing (6 bits/char, 0x30..0x6F) ----------
struct BitW {
    string s; int cur = 0, nb = 0;
    void put(int v, int bits) { for (int b = bits-1; b >= 0; b--) putBit((v>>b)&1); }
    void putBit(int b){ cur = cur*2 + b; if(++nb==6){ s += (char)(0x30+cur); cur=0; nb=0; } }
    int bitLen() const { return (int)s.size()*6 + nb; }
    string finish(){ while(nb) putBit(0); return s; }
};
struct BitR {
    string s; size_t pos = 0; int cur = 0, nb = 0;
    BitR(const string &str) : s(str) {}
    int getBit(){ if(!nb){ if(pos>=s.size()) return 0; cur = s[pos++]-0x30; nb=6; } nb--; return (cur>>nb)&1; }
    int get(int bits){ int v=0; while(bits--) v=v*2+getBit(); return v; }
};

// ---------- radial static order & bootstrap ----------
static bool staticMode();
static vector<int> radialOrder;
static void buildRadial() {
    // diagonal-band order: the s-t path in a random spanning tree concentrates
    // near the main diagonal, so covering a widening band around it completes
    // the path at ~0.6W instead of radial disks' ~0.85W (offline sim).
    vector<pair<float,int>> ord(W);
    for (int w = 0; w < W; w++) {
        int a, b; wallRooms(w, a, b);
        float i = (a/m + b/m) * 0.5f, j = (a%m + b%m) * 0.5f;
        float ds = sqrtf(i*i + j*j);
        float dt = sqrtf((i-(m-1))*(i-(m-1)) + (j-(m-1))*(j-(m-1)));
        // band order only where the stream is the workhorse (high K / static
        // mode); at low K the adaptive PQ leads and prefers radial knowledge
        if (K >= 23 || staticMode())
            ord[w] = {fabsf(i - j) + 0.15f * min(ds, dt), w};
        else
            ord[w] = {min(ds, dt), w};
    }
    sort(ord.begin(), ord.end());
    radialOrder.resize(W);
    for (int w = 0; w < W; w++) radialOrder[w] = ord[w].second;
}
static vector<int> bootstrapSeq(int h) { // worker h (1..K-1)
    vector<int> v;
    for (int p = h-1; p < W; p += (K-1)) v.push_back(radialOrder[p]);
    return v;
}
static inline int bootN(int h) { return 2*(h-1) + 1; } // bootstrap probe budget
// timetable (shared by coordinator and workers):
// coordinator receives worker h's cycle-c results at recvRound(h,c), sends
// next tasks one round later; worker h's cycle-c tasks arrive at
// taskArrive(h,c); worker sends results at recvRound(h,c)-1.
static inline long long recvRound(int h, long long c) { return BLOCK1 + (c-1)*(long long)P_CYCLE + 2*(h-1); }
static inline long long taskArriveRound(int h, long long c) {
    return c == 1 ? 2LL*(h-1) + 5 : recvRound(h, c-1) + 2;
}

// ---------- rice coding for task ids ----------
static int riceBits(const vector<int>&deltas, int k){
    long long total = 0;
    for (int d : deltas) total += (d >> k) + 1 + k;
    return total > 1e9 ? INT_MAX : (int)total;
}

// ---------- query ----------
static int askCell(int r, int c) {
    char cmd[32]; snprintf(cmd, sizeof cmd, "? %d %d", r, c);
    sendCmd(cmd);
    if (!readLine()) exit(0);
    return lineBuf[0] == '1';
}

static void setWallC(int w, int v);
static void markRoom(int u0, int rg, int lvl0);

// ---------- static mode (small W/(K-1)): v2-style radial streaming ----------
// Workers probe their whole radial slice, sending packed results at fixed
// checkpoints; coordinator just ingests and claims. No task machinery.
static bool staticMode() { return K >= 3 && W / (K - 1) <= 160; }
// (fwd-declared above buildRadial)
static vector<int> staticCheckpoints(int sliceLen) { // payload sizes
    vector<int> cps; int sent = 0, nxt = 64;
    int cap = max(60, MSGLEN*6 - 20);
    while (sent < sliceLen) {
        int sz = min(nxt, sliceLen - sent);
        cps.push_back(sz); sent += sz;
        nxt = min(nxt * 4, cap);
    }
    return cps;
}
static void runStaticWorker() {
    vector<int> slice = bootstrapSeq(ID);
    vector<int> cps = staticCheckpoints((int)slice.size());
    size_t qi = 0, ci = 0;
    BitW payload;
    int inBuf = 0;
    while (qi < slice.size()) {
        auto [r, c] = wallCell(slice[qi++]);
        payload.putBit(askCell(r, c)); inBuf++;
        if (ci < cps.size() && inBuf == cps[ci]) {
            BitW bw; bw.put(63, 6); bw.put(inBuf, 12);
            BitR pr(payload.finish());
            for (int i = 0; i < inBuf; i++) bw.putBit(pr.getBit());
            string msg = "> 0 " + bw.finish();
            sendCmd(msg.c_str()); if (!readLine()) exit(0);
            payload = BitW(); inBuf = 0; ci++;
        }
    }
    sendCmd("halt");
    exit(0);
}
static void runStaticCoordinator() {
    int nw = K - 1;
    // mirror worker schedules: worker h sends at deterministic rounds
    vector<long long> arrivals;
    vector<vector<pair<int,int>>> chunks(nw+1); // per worker: (sliceStart,len) per msg
    for (int h = 1; h <= nw; h++) {
        vector<int> slice = bootstrapSeq(h);
        vector<int> cps = staticCheckpoints((int)slice.size());
        long long r = 0; int start = 0;
        for (int sz : cps) { r += sz; r += 1; arrivals.push_back(r + 1); chunks[h].push_back({start, sz}); start += sz; }
    }
    sort(arrivals.begin(), arrivals.end());
    vector<size_t> nextChunk(nw+1, 0);
    size_t arrIdx = 0; long long recvDone = 0, round = 0;
    int misses = 0;
    // fallback self-probe pointer
    int sp = 0;
    for (;;) {
        round++;
        if (connectedST()) claimPath();
        while (arrIdx < arrivals.size() && arrivals[arrIdx] <= round) arrIdx++;
        long long pending = (long long)arrIdx - recvDone;
        if (pending > 0 && misses < 16) {
            sendCmd("< ?");
            if (!readLine()) exit(0);
            if (lineBuf[0] == '-') { misses++; continue; }
            recvDone++;
            int sender = atoi(lineBuf);
            char *spc = strchr(lineBuf, ' ');
            if (spc && sender >= 1 && sender <= nw && nextChunk[sender] < chunks[sender].size()) {
                string body(spc+1);
                while (!body.empty() && (body.back()=='\n'||body.back()=='\r')) body.pop_back();
                BitR br(body);
                br.get(6);
                int n = br.get(12);
                auto [start, len] = chunks[sender][nextChunk[sender]++];
                vector<int> slice = bootstrapSeq(sender);
                for (int i = 0; i < n && i < len && start + i < (int)slice.size(); i++)
                    setWallC(slice[start+i], br.getBit());
            }
        } else {
            // self-probe unknown walls in radial order (duplicates ok)
            while (sp < W && wallSt[radialOrder[sp]] != -1) sp++;
            if (sp < W) { auto [r,c] = wallCell(radialOrder[sp]); setWallC(radialOrder[sp], askCell(r,c)); }
            else { sendCmd("."); if (!readLine()) exit(0); }
        }
        if (connectedST()) claimPath();
    }
}

// ============================ WORKER ============================
static void runWorker() {
    buildRadial();
    vector<int> boot = bootstrapSeq(ID);
    int bn = bootN(ID);
    long long round = 0;
    auto probeOrDot = [&](int w, BitW &bw) {
        round++;
        if (w >= 0) { auto [r,c] = wallCell(w); bw.putBit(askCell(r, c)); }
        else { sendCmd("."); if (!readLine()) exit(0); }
    };
    // bootstrap: bn rounds of probing, then send at round bn+1
    {
        BitW bw; bw.put(63, 6); // seq 63 = bootstrap
        int cnt = min(bn, (int)boot.size());
        BitW payload;
        for (int i = 0; i < bn; i++) probeOrDot(i < (int)boot.size() ? boot[i] : -1, payload);
        bw.put(cnt, 12);
        // append payload bits (only first cnt bits are real)
        BitR pr(payload.finish());
        for (int i = 0; i < cnt; i++) bw.putBit(pr.getBit());
        string msg = "> 0 " + bw.finish();
        sendCmd(msg.c_str()); if (!readLine()) exit(0); round++;
    }
    for (long long cyc = 1; ; cyc++) {
        // idle until this cycle's tasks arrive
        long long arrive = taskArriveRound(ID, cyc);
        while (round + 1 < arrive) { round++; sendCmd("."); if (!readLine()) exit(0); }
        // recv tasks
        round++;
        sendCmd("< 0");
        if (!readLine()) exit(0);
        vector<int> tasks; int seq = 62; // 62 = missing
        if (lineBuf[0] != '-') {
            char *sp = strchr(lineBuf, ' ');
            if (sp) {
                string body(sp+1);
                while (!body.empty() && (body.back()=='\n'||body.back()=='\r')) body.pop_back();
                BitR br(body);
                seq = br.get(6);
                int n = br.get(12);
                int k = br.get(5);
                int prev = -1;
                for (int i = 0; i < n; i++) {
                    int q = 0; while (br.getBit()) q++;
                    int d = (q << k) | br.get(k);
                    prev += d + 1;
                    if (prev >= 0 && prev < W) tasks.push_back(prev);
                }
            }
        }
        // probe tasks, then idle until the send round
        long long sendAt = recvRound(ID, cyc) - 1;
        BitW payload;
        size_t ti = 0;
        while (round + 1 < sendAt) {
            round++;
            if (ti < tasks.size()) { auto [r,c] = wallCell(tasks[ti++]); payload.putBit(askCell(r,c)); }
            else { sendCmd("."); if (!readLine()) exit(0); }
        }
        // send results
        BitW bw; bw.put(seq, 6); bw.put((int)ti, 12);
        BitR pr(payload.finish());
        for (size_t i = 0; i < ti; i++) bw.putBit(pr.getBit());
        string msg = "> 0 " + bw.finish();
        round++; sendCmd(msg.c_str()); if (!readLine()) exit(0);
    }
}

// ============================ COORDINATOR ============================
struct PQItem { float key; int wall; };
struct PQCmp { bool operator()(const PQItem&a, const PQItem&b) const {
    return a.key > b.key || (a.key == b.key && a.wall > b.wall); } };

static priority_queue<PQItem, vector<PQItem>, PQCmp> pq;
static vector<int8_t> inFlight;   // per wall
static vector<int8_t> regMark;    // per room: 0 none, 1 s-side, 2 t-side (incl. speculative)
static vector<int16_t> roomLevel; // speculation depth (0 = confirmed in region)
static float LAMBDA = 1.5f;       // per-speculation-level key penalty

static inline float keyOf(int v, int rg) {
    int i = v/m, j = v%m;
    float ti = (rg == 1) ? (float)(m-1) : 0.0f;
    return sqrtf((i-ti)*(i-ti) + (j-ti)*(j-ti));
}
// room u belongs (speculatively at depth lvl, or confirmed at 0) to side rg;
// (re)push its unknown walls when this improves the room's level. Level
// propagates unchanged along known-open walls, +1 across unknown walls.
static void markRoom(int u0, int rg, int lvl0) {
    // one-shot marking keeps total work O(rooms + walls): a room is marked at
    // most twice — once speculatively (level > 0), once realized (level 0)
    static vector<pair<int,int>> stk;
    stk.clear();
    stk.push_back({u0, lvl0});
    while (!stk.empty()) {
        auto [u, lvl] = stk.back(); stk.pop_back();
        bool improve = (lvl == 0) ? (roomLevel[u] > 0) : (roomLevel[u] == INT16_MAX);
        if (!improve) continue;
        roomLevel[u] = (int16_t)lvl;
        regMark[u] = (int8_t)rg;
        for (int dir = 0; dir < 4; dir++) {
            int w = wallOf(u, dir);
            if (w < 0 || wallSt[w] == 0) continue;
            int v = roomAcross(u, dir);
            if (wallSt[w] == 1) {
                if ((lvl == 0 && roomLevel[v] > 0) || roomLevel[v] == INT16_MAX)
                    stk.push_back({v, lvl});
            } else if (roomLevel[v] == INT16_MAX || lvl == 0) {
                float key = (roomLevel[v] == 0 && regMark[v] != rg) ? 0.0f
                          : keyOf(v, rg) + LAMBDA * (float)(lvl + 1);
                pq.push({key, w});
            }
        }
    }
}
// tree-property inference: same-component wall => closed; a room with 3
// (known or inferred) closed walls => 4th open. Cascades via work queue.
static vector<int> inferQ;
static void setWallRaw(int w, int v) {
    inFlight[w] = 0;
    if (wallSt[w] != -1) return;
    wallSt[w] = (int8_t)v;
    int a, b; wallRooms(w, a, b);
    if (v == 1) {
        dsuUnite(a, b);
        if (roomLevel[a] == 0 || roomLevel[b] == 0) {
            int rg = roomLevel[a] == 0 ? regMark[a] : regMark[b];
            markRoom(a, rg, 0); markRoom(b, rg, 0);
        }
    }
    inferQ.push_back(a); inferQ.push_back(b);
}
static void setWallC(int w, int v) { // record result + run inference cascade
    setWallRaw(w, v);
    while (!inferQ.empty()) {
        int u = inferQ.back(); inferQ.pop_back();
        int unkW = -1, unkFar = -1, closedCnt = 0, unkCnt = 0;
        for (int dir = 0; dir < 4; dir++) {
            int ww = wallOf(u, dir);
            if (ww < 0) { closedCnt++; continue; }
            if (wallSt[ww] == 0) { closedCnt++; continue; }
            if (wallSt[ww] == 1) continue;
            int a2, b2; wallRooms(ww, a2, b2);
            if (dsuFind(a2) == dsuFind(b2)) { setWallRaw(ww, 0); closedCnt++; continue; }
            unkCnt++; unkW = ww; unkFar = roomAcross(u, dir);
        }
        if (unkCnt == 1 && closedCnt == 3) { (void)unkFar; setWallRaw(unkW, 1); }
    }
}
static long long popsSinceRebuild2 = 0;
// drop stale speculation, rebuild PQ from the realized frontier
static void rebuildPQ() {
    while (!pq.empty()) pq.pop();
    for (int u = 0; u < m*m; u++)
        if (roomLevel[u] != 0 && roomLevel[u] != INT16_MAX) { roomLevel[u] = INT16_MAX; regMark[u] = 0; }
    for (int u = 0; u < m*m; u++) {
        if (roomLevel[u] != 0) continue;
        int rg = regMark[u];
        for (int dir = 0; dir < 4; dir++) {
            int w = wallOf(u, dir);
            if (w < 0 || wallSt[w] != -1) continue;
            int v = roomAcross(u, dir);
            if (roomLevel[v] == 0 && regMark[v] == rg) continue;
            float key = (roomLevel[v] == 0 && regMark[v] != rg) ? 0.0f : keyOf(v, rg) + LAMBDA;
            pq.push({key, w});
        }
    }
}
// pop the best assignable wall; optimistically extend region past it
static int popTask() {
    if (++popsSinceRebuild2 >= REBUILD_EVERY) { popsSinceRebuild2 = 0; rebuildPQ(); }
    while (!pq.empty()) {
        auto [key, w] = pq.top(); pq.pop();
        if (wallSt[w] != -1 || inFlight[w]) continue;
        int a, b; wallRooms(w, a, b);
        if (regMark[a] && regMark[b] && regMark[a] == regMark[b]
            && roomLevel[a] == 0 && roomLevel[b] == 0) continue; // internal wall
        inFlight[w] = 1;
        // speculate past it from the shallower side
        int u = (roomLevel[a] <= roomLevel[b]) ? a : b;
        int far = (u == a) ? b : a;
        if (regMark[u] && roomLevel[u] < INT16_MAX)
            markRoom(far, regMark[u], roomLevel[u] + 1);
        return w;
    }
    return -1;
}

static void runCoordinator() {
    buildRadial();
    inFlight.assign(W, 0);
    regMark.assign(m*m, 0);
    roomLevel.assign(m*m, INT16_MAX);
    markRoom(0, 1, 0);
    markRoom(m*m-1, 2, 0);

    int nw = K - 1;
    // bootstrap assignments (already being probed by workers)
    vector<vector<int>> bootAssigned(nw+1);
    for (int h = 1; h <= nw; h++) {
        vector<int> seq = bootstrapSeq(h);
        int cnt = min(bootN(h), (int)seq.size());
        for (int i = 0; i < cnt; i++) { bootAssigned[h].push_back(seq[i]); inFlight[seq[i]] = 1; }
    }
    // per-worker current assignment
    vector<vector<int>> assigned(nw+1);
    vector<int> lastSeq(nw+1, 63);
    vector<int> misses(nw+1, 0);
    vector<int8_t> dead(nw+1, 0);
    int radialPtr = 0; // fallback pointer for leftovers
    int selfDupPtr = 0; // duplicate-probe pointer for idle rounds
    deque<int> bandBacklog; // capacity-dropped band tasks to reassign

    int capacityBits = MSGLEN * 6;
    long long round = 0;

    auto ingest = [&](int h, const string &body, bool bootstrap) {
        BitR br(body);
        int seq = br.get(6);
        int n = br.get(12);
        vector<int> &lst = bootstrap ? bootAssigned[h] : assigned[h];
        if (!bootstrap && seq != lastSeq[h]) {
            // desync: drop, requeue
            for (int w : lst) if (inFlight[w]) { inFlight[w] = 0;
                int a,b; wallRooms(w,a,b); int rg = regMark[a]?regMark[a]:(regMark[b]?regMark[b]:1);
                pq.push({keyOf(regMark[a]?b:a, rg), w}); }
            lst.clear();
            return;
        }
        for (int i = 0; i < n && i < (int)lst.size(); i++) setWallC(lst[i], br.getBit());
        lst.clear();
    };
    auto requeue = [&](vector<int> &lst) {
        for (int w : lst) if (wallSt[w] == -1) { inFlight[w] = 0;
            int a,b; wallRooms(w,a,b); int rg = regMark[a]?regMark[a]:(regMark[b]?regMark[b]:1);
            pq.push({keyOf(regMark[a]?b:a, rg), w}); }
        lst.clear();
    };

    for (;;) {
        round++;
        if (connectedST()) claimPath();
        // timetable: bootstrap block rounds [3, 2*nw+2]; cycle blocks start
        // blockStart1 + (c-1)*P, width 2*nw
        int action = 0, h = 0; // 0 self, 1 recv, 2 send
        if (round >= 3 && round <= 2*nw + 2) {
            long long off = round - 3;
            h = (int)(off / 2) + 1;
            action = (off % 2 == 0) ? 1 : 2;
        } else if (round >= BLOCK1) {
            long long off = (round - BLOCK1) % P_CYCLE;
            if (off < 2*nw) { h = (int)(off / 2) + 1; action = (off % 2 == 0) ? 1 : 2; }
        }
        if (h > 0 && dead[h]) action = 0;

        if (action == 1) { // recv from h (bootstrap if within bootstrap block)
            bool isBoot = (round <= 2*nw + 2);
            char cmd[16]; snprintf(cmd, sizeof cmd, "< %d", h);
            sendCmd(cmd);
            if (!readLine()) exit(0);
            if (lineBuf[0] == '-') {
                misses[h]++;
                if (misses[h] >= 2) { dead[h] = 1; requeue(bootAssigned[h]); requeue(assigned[h]); }
            } else {
                misses[h] = 0;
                char *sp = strchr(lineBuf, ' ');
                if (sp) {
                    string body(sp+1);
                    while (!body.empty() && (body.back()=='\n'||body.back()=='\r')) body.pop_back();
                    ingest(h, body, isBoot);
                }
            }
        } else if (action == 2) { // send tasks to h
            vector<int> tasks;
            // pop up to Q_TASK tasks; ensure encodable.
            // K >= 23: assignments come purely from the diagonal-band stream
            // (adaptive PQ at this staleness degrades to corner blobs, which
            // lose to the band); the PQ still drives fresh self-probes.
            bool bandOnly = (K >= 23);
            while ((int)tasks.size() < Q_TASK) {
                int w = -1;
                while (!bandBacklog.empty() && w < 0) {
                    int c = bandBacklog.front(); bandBacklog.pop_front();
                    if (wallSt[c] == -1 && !inFlight[c]) { w = c; inFlight[c] = 1; }
                }
                if (w < 0 && !bandOnly) w = popTask();
                if (w < 0) {
                    // next unknown, unassigned band-order wall
                    while (radialPtr < W && (wallSt[radialOrder[radialPtr]] != -1 || inFlight[radialOrder[radialPtr]])) radialPtr++;
                    if (radialPtr >= W) break;
                    w = radialOrder[radialPtr]; inFlight[w] = 1;
                }
                tasks.push_back(w);
            }
            sort(tasks.begin(), tasks.end());
            // encode with rice; shrink until it fits
            string body;
            for (;;) {
                vector<int> deltas; int prev = -1;
                for (int w : tasks) { deltas.push_back(w - prev - 1); prev = w; }
                int bestK = 0, bestBits = INT_MAX;
                for (int k = 0; k <= 17; k++) { int bb = riceBits(deltas, k); if (bb < bestBits) { bestBits = bb; bestK = k; } }
                if (23 + bestBits <= capacityBits || tasks.empty()) {
                    BitW bw;
                    int seq = (int)((round / P_CYCLE) % 60);
                    lastSeq[h] = seq;
                    bw.put(seq, 6); bw.put((int)tasks.size(), 12); bw.put(bestK, 5);
                    for (int d : deltas) { int qd = d >> bestK; while (qd--) bw.putBit(1); bw.putBit(0); bw.put(d & ((1<<bestK)-1), bestK); }
                    body = bw.finish();
                    break;
                }
                // drop the last task, requeue it
                int w = tasks.back(); tasks.pop_back();
                inFlight[w] = 0;
                bandBacklog.push_back(w);
            }
            assigned[h] = tasks;
            string msg = "> " + to_string(h) + " " + body;
            sendCmd(msg.c_str());
            if (!readLine()) exit(0);
        } else { // self-probe
            int w = popTask();
            if (w < 0) {
                while (radialPtr < W && (wallSt[radialOrder[radialPtr]] != -1 || inFlight[radialOrder[radialPtr]])) radialPtr++;
                if (radialPtr < W) { w = radialOrder[radialPtr]; inFlight[w] = 1; }
            }
            if (w < 0) {
                // nothing fresh: duplicate-probe an in-flight unknown wall
                // (idle rounds are free; helps tiny mazes / dead workers)
                while (selfDupPtr < W && wallSt[radialOrder[selfDupPtr]] != -1) selfDupPtr++;
                if (selfDupPtr < W) w = radialOrder[selfDupPtr];
            }
            if (w >= 0) { auto [r,c] = wallCell(w); int v = askCell(r, c); setWallC(w, v); }
            else { sendCmd("."); if (!readLine()) exit(0); }
        }
        if (connectedST()) claimPath();
    }
}

// ============================ solo (K==1) ============================
static void runSolo() {
    buildRadial();
    inFlight.assign(W, 0);
    regMark.assign(m*m, 0);
    roomLevel.assign(m*m, INT16_MAX);
    markRoom(0, 1, 0); markRoom(m*m-1, 2, 0);
    for (;;) {
        if (connectedST()) claimPath();
        int w = popTask();
        if (w < 0) { sendCmd("."); if (!readLine()) exit(0); continue; }
        auto [r, c] = wallCell(w);
        setWallC(w, askCell(r, c));
    }
}

int run(const string& first) {
    if (sscanf(first.c_str(), "%d %d %d %d", &N, &K, &ID, &MSGLEN) != 4) return 0;
    m = (N + 1) / 2;
    W = 2 * m * (m - 1);
    HW = m * (m - 1);
    // staleness B=(K-1)*q vs throughput tradeoff: smaller batches for small K
    if (K <= 6) Q_TASK = 64;
    else if (K <= 22) Q_TASK = 32;
    else Q_TASK = min(96, 2*K - 4); // tightest cycle the coordinator can serve
    P_CYCLE = max(2*(K-1) + 2, Q_TASK + 4);
    BLOCK1 = max(Q_TASK + 7, 2*(K-1) + 3);
    if (N == 1) { if (ID == 0) sendCmd("! "); else sendCmd("halt"); return 0; }
    wallSt.assign(W, -1);
    dsu.resize(m*m); iota(dsu.begin(), dsu.end(), 0);
    if (K == 1) runSolo();
    else if (staticMode()) {
        buildRadial();
        if (ID == 0) {
            inFlight.assign(W, 0);
            regMark.assign(m*m, 0);
            roomLevel.assign(m*m, INT16_MAX);
            markRoom(0, 1, 0); markRoom(m*m-1, 2, 0);
            runStaticCoordinator();
        } else runStaticWorker();
    }
    else if (ID == 0) runCoordinator();
    else runWorker();
    return 0;
}

} // namespace mine

int main() {
    string first;
    if (!getline(cin, first)) return 0;
    int n = 0; sscanf(first.c_str(), "%d", &n);
    if (n < 291) return vova::run(first);
    return mine::run(first);
}