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

// Datacenter Imprisonment agent.
//
// The maze is a perfect maze whose empty cells form a spanning tree of an
// RM x RM room lattice (RM = (N+1)/2).  Rooms sit at odd/odd 1-indexed cells and
// are always empty; the only unknowns are the corridor cells between adjacent
// rooms (EDGE_COUNT of them).  Querying those corridor cells fully determines the
// tree, and the (1,1)->(N,N) path is the unique room-tree path, each room step
// expanded to two identical cell steps.
//
// Two cooperative strategies, chosen by a turn-count estimate:
//   * SCAN: agents partition the corridor edges and stream them (diagonal order)
//     to a coordinator, which early-claims the moment its known-open forest joins
//     the two terminals -- it need not wait for every edge.
//   * ACTIVE: for few agents, autonomous greedy best-first traces from both
//     terminals, meeting in the middle; the coordinator merges the traces.
//
// The referee's generator is a randomized-Kruskal uniform spanning tree.

#ifndef FORCE_ACTIVE_MAX
#define FORCE_ACTIVE_MAX (-1)   // -1 = use normal estimator
#endif

static int N, NUM_AGENTS, AGENT_ID, MAX_MSG_LEN;
static int RM;
static long long ROOMS, H_EDGES, EDGE_COUNT;
static int PAYLOAD;
static int ACTIVE_AGENTS = 0;
static vector<int> EDGE_ORDER;
static constexpr long long INF = (long long)4e18;

[[noreturn]] static void quit_now() { exit(0); }
static string transact(const string &cmd) {
    cout << cmd << '\n' << flush;
    string reply;
    if (!getline(cin, reply)) quit_now();
    return reply;
}
static void send_msg(int to, const string &body) { (void)transact("> " + to_string(to) + " " + body); }
[[noreturn]] static void claim_path(const string &path) { cout << "! " << path << '\n' << flush; quit_now(); }
[[noreturn]] static void halt_agent() { cout << "halt\n" << flush; quit_now(); }

// ---- base-94 bit packing: 13 bits per 2 printable chars ----
static inline char enc94(int v) { return char(33 + v); }
static inline int dec94(char ch) { int v = (int)(unsigned char)ch - 33; return (0 <= v && v < 94) ? v : 0; }
struct BitPacker {
    string s; int acc = 0, cnt = 0, bits = 0;
    void add(bool bit) {
        if (bit) acc |= (1 << cnt);
        ++bits;
        if (++cnt == 13) { s.push_back(enc94(acc % 94)); s.push_back(enc94(acc / 94)); acc = cnt = 0; }
    }
    string finish() {
        if (cnt) { if (cnt <= 6) s.push_back(enc94(acc)); else { s.push_back(enc94(acc % 94)); s.push_back(enc94(acc / 94)); } }
        string out = s; s.clear(); acc = cnt = bits = 0; return out;
    }
};
template<class F> static void decode_bits(const string &enc, long long bit_count, F &&fn) {
    size_t pos = 0; long long done = 0;
    while (done < bit_count) {
        long long rem = bit_count - done; int take, v;
        if (rem >= 13) { v = dec94(pos < enc.size() ? enc[pos] : '!') + 94 * dec94(pos + 1 < enc.size() ? enc[pos + 1] : '!'); pos += 2; take = 13; }
        else if (rem <= 6) { v = dec94(pos < enc.size() ? enc[pos] : '!'); pos += 1; take = (int)rem; }
        else { v = dec94(pos < enc.size() ? enc[pos] : '!') + 94 * dec94(pos + 1 < enc.size() ? enc[pos + 1] : '!'); pos += 2; take = (int)rem; }
        for (int b = 0; b < take; ++b) fn(((v >> b) & 1) != 0);
        done += take;
    }
}
// full-13-bit-pair decode (active traces flush only on 13-bit boundaries)
template<class F> static void decode_pairs(const string &enc, F &&fn) {
    size_t pos = 0;
    while (pos + 1 < enc.size()) { int v = dec94(enc[pos]) + 94 * dec94(enc[pos + 1]); pos += 2; for (int b = 0; b < 13; ++b) fn(((v >> b) & 1) != 0); }
}
static inline long long part_count(long long total, int parts, int id) {
    if (id < 0 || id >= parts || id >= total) return 0;
    return (total - 1 - id) / parts + 1;
}
static bool parse_msg(const string &line, int &sender, string &body) {
    size_t sp = line.find(' ');
    if (sp == string::npos || sp == 0) return false;
    int x = 0;
    for (size_t i = 0; i < sp; ++i) { if (!isdigit((unsigned char)line[i])) return false; x = x * 10 + (line[i] - '0'); }
    sender = x; body = line.substr(sp + 1); return true;
}

// ---- corridor-edge geometry ----
// ord in [0,H_EDGES): horizontal edge; [H_EDGES,EDGE_COUNT): vertical.
static inline void edge_cell(long long ord, int &r, int &c) {
    if (ord < H_EDGES) { long long rr = ord / (RM - 1), cc = ord % (RM - 1); r = (int)(2*rr+1); c = (int)(2*cc+2); }
    else { long long t = ord - H_EDGES, rr = t / RM, cc = t % RM; r = (int)(2*rr+2); c = (int)(2*cc+1); }
}
static bool ask(long long ord) { int r, c; edge_cell(ord, r, c); string rep = transact("? " + to_string(r) + " " + to_string(c)); return !rep.empty() && rep[0] == '1'; }
static inline long long horiz_ord(int rr, int cc) { return 1LL * rr * (RM - 1) + cc; }
static inline long long vert_ord(int rr, int cc) { return H_EDGES + 1LL * rr * RM + cc; }
static inline pair<int,int> edge_rooms(long long ord) {
    if (ord < H_EDGES) { int r = (int)(ord/(RM-1)), c = (int)(ord%(RM-1)); int u = r*RM+c; return {u, u+1}; }
    long long t = ord - H_EDGES; int r = (int)(t/RM), c = (int)(t%RM); int u = r*RM+c; return {u, u+RM};
}
static inline pair<int,int> edge_center2(long long ord) {
    if (ord < H_EDGES) { int r = (int)(ord/(RM-1)), c = (int)(ord%(RM-1)); return {2*r, 2*c+1}; }
    long long t = ord - H_EDGES; int r = (int)(t/RM), c = (int)(t%RM); return {2*r+1, 2*c};
}
static inline uint32_t mix32(uint32_t x){ x^=x>>16; x*=0x7feb352du; x^=x>>15; x*=0x846ca68bu; x^=x>>16; return x; }
// Scan edges from the s->t diagonal outward, so the known-open region is a stripe
// hugging the main diagonal; it joins the two terminals as soon as it covers the
// path's excursions.  Hash tie-break avoids systematically delaying one board end.
static vector<int> build_edge_order() {
    vector<int> ord((size_t)EDGE_COUNT);
    iota(ord.begin(), ord.end(), 0);
    const int M = 2 * (RM - 1);
    sort(ord.begin(), ord.end(), [&](int a, int b) {
        auto [ax, ay] = edge_center2(a); auto [bx, by] = edge_center2(b);
        int aband = abs(ax - ay), bband = abs(bx - by);
        if (aband != bband) return aband < bband;
        uint32_t ah = mix32((uint32_t)a*1000003u + (uint32_t)RM*9176u);
        uint32_t bh = mix32((uint32_t)b*1000003u + (uint32_t)RM*9176u);
        int amid = abs(ax+ay - M), bmid = abs(bx+by - M);
        long long ak = 1LL*amid*65536 + (ah&65535u), bk = 1LL*bmid*65536 + (bh&65535u);
        if (ak != bk) return ak < bk;
        return a < b;
    });
    return ord;
}

// ---- known-open forest with incremental early-connect claim ----
struct DSU {
    vector<int> p, sz;
    void init(int n){ p.resize(n); sz.assign(n,1); iota(p.begin(),p.end(),0); }
    int find(int x){ while(p[x]!=x){ p[x]=p[p[x]]; x=p[x]; } return x; }
    void unite(int a,int b){ a=find(a); b=find(b); if(a==b) return; if(sz[a]<sz[b]) swap(a,b); p[b]=a; sz[a]+=sz[b]; }
};
static DSU DS;
static vector<array<int,4>> ADJ;
static vector<unsigned char> DEG;
static string solve_forest() {
    if (ROOMS == 1) return "";
    int goal = (int)ROOMS - 1;
    vector<int> par((size_t)ROOMS, -1); queue<int> q; par[0] = -2; q.push(0);
    while (!q.empty() && par[goal] == -1) { int u = q.front(); q.pop();
        for (int i = 0; i < DEG[u]; ++i) { int v = ADJ[u][i]; if (par[v] != -1) continue; par[v] = u; q.push(v); if (v == goal) break; } }
    if (par[goal] == -1) return "";
    string rp;
    for (int cur = goal; cur != 0; cur = par[cur]) { int pp = par[cur];
        if (cur == pp+1) rp.push_back('R'); else if (cur == pp-1) rp.push_back('L');
        else if (cur == pp+RM) rp.push_back('D'); else if (cur == pp-RM) rp.push_back('U'); else return ""; }
    reverse(rp.begin(), rp.end());
    string ans; ans.reserve(rp.size()*2); for (char ch : rp) { ans.push_back(ch); ans.push_back(ch); } return ans;
}
static inline void apply_edge(long long ord, bool open) {
    if (!open) return;
    auto [u,v] = edge_rooms(ord);
    if (u<0||v<0||u>=(int)ROOMS||v>=(int)ROOMS) return;
    if (DEG[u]<4) ADJ[u][DEG[u]++]=v;
    if (DEG[v]<4) ADJ[v][DEG[v]++]=u;
    DS.unite(u,v);
    if (DS.find(0)==DS.find((int)ROOMS-1)) { string p=solve_forest(); if(!p.empty()||ROOMS==1) claim_path(p); }
}

// ================= SCAN =================
#ifndef SCAN_FLUSH_DEF
#define SCAN_FLUSH_DEF 0
#endif
static int SCAN_FLUSH = SCAN_FLUSH_DEF;   // >0 forces a fixed chunk size; 0 = adaptive
static int scan_flush_bits() {
    int cap = max(13, (PAYLOAD / 2) * 13);
    // Larger chunks cut the coordinator's read count; smaller chunks reveal path edges
    // at a finer granularity so early-connect fires sooner.  Big boards with few agents
    // are query-bound and prefer coarser chunks; many agents prefer finer ones.
    int target = (SCAN_FLUSH > 0) ? SCAN_FLUSH : ((RM >= 180 && NUM_AGENTS <= 20) ? 390 : 208);
    return max(13, min(target, cap) / 13 * 13);
}
static void worker_scan(int coord, int W, int part_id) {
    BitPacker bp; const int F = scan_flush_bits();
    for (long long rank = part_id; rank < EDGE_COUNT; rank += W) {
        bp.add(ask(EDGE_ORDER[(size_t)rank]));
        if (bp.bits >= F) send_msg(coord, bp.finish());
    }
    if (bp.bits > 0) send_msg(coord, bp.finish());
    halt_agent();
}
// coordQueries: coordinator owns partition 0 (interleaves queries with reads via an
// arrival-time model).  Otherwise it is a pure receiver; workers are firstWorker..
static void coordinator_scan(int W, bool coordQueries, int firstWorker) {
    const int F = scan_flush_bits();
    int firstPid = coordQueries ? 1 : 0;
    vector<long long> need(W,0), got(W,0);
    long long remaining = 0;
    vector<long long> arrivals;
    for (int pid = firstPid; pid < W; ++pid) {
        long long bits = part_count(EDGE_COUNT, W, pid);
        long long ch = (bits + F - 1) / F;
        need[pid] = ch; remaining += ch;
        for (long long k = 0; k < ch; ++k) arrivals.push_back(min(bits,(k+1)*1LL*F) + (k+1) + 1);
    }
    sort(arrivals.begin(), arrivals.end());
    long long localTotal = coordQueries ? part_count(EDGE_COUNT, W, 0) : 0;
    long long localDone = 0, turn = 0, due = 0; size_t aptr = 0;
    auto consume = [&](const string &line){
        int sender=-1; string body;
        if (!parse_msg(line, sender, body)) return;
        int pid = coordQueries ? sender : (sender - firstWorker);
        if (pid < firstPid || pid >= W || got[pid] >= need[pid]) return;
        long long total = part_count(EDGE_COUNT, W, pid);
        long long off = got[pid]*F, take = min((long long)F, total-off), bit = 0;
        decode_bits(body, take, [&](bool one){ long long gr = pid + (off+bit)*1LL*W; if (gr < EDGE_COUNT) apply_edge(EDGE_ORDER[(size_t)gr], one); ++bit; });
        ++got[pid]; --remaining;
    };
    while (localDone < localTotal || remaining > 0) {
        while (aptr < arrivals.size() && arrivals[aptr] <= turn + 1) { ++due; ++aptr; }
        if (due > 0 && remaining > 0) { string line = transact("< ?"); ++turn; long long before = remaining; consume(line); if (before != remaining && due > 0) --due; continue; }
        if (localDone < localTotal) { long long rank = localDone*1LL*W; ++turn; apply_edge(EDGE_ORDER[(size_t)rank], ask(EDGE_ORDER[(size_t)rank])); ++localDone; continue; }
        if (remaining > 0) { string line = transact("< ?"); ++turn; consume(line); }
    }
    string p = solve_forest(); if (!p.empty() || ROOMS == 1) claim_path(p);
    halt_agent();
}
// Estimate the claim turn of a full scan (no early connect) for W workers, with the
// coordinator either querying a share or acting as a pure receiver.
static long long estimate_scan(int W, bool coordQueries) {
    if (W <= 0) return INF;
    const int F = scan_flush_bits();
    int firstPid = coordQueries ? 1 : 0;
    vector<long long> arrivals;
    for (int pid = firstPid; pid < W; ++pid) {
        long long bits = part_count(EDGE_COUNT, W, pid);
        long long ch = (bits + F - 1) / F;
        for (long long k = 0; k < ch; ++k) arrivals.push_back(min(bits,(k+1)*1LL*F) + (k+1) + 1);
    }
    sort(arrivals.begin(), arrivals.end());
    long long local = coordQueries ? part_count(EDGE_COUNT, W, 0) : 0;
    long long t = 0, localDone = 0, read = 0, pending = 0; size_t ptr = 0;
    long long totalReads = (long long)arrivals.size();
    while (localDone < local || read < totalReads) {
        if (pending == 0 && localDone >= local && ptr < arrivals.size() && t + 1 < arrivals[ptr]) t = arrivals[ptr] - 1;
        ++t;
        while (ptr < arrivals.size() && arrivals[ptr] <= t) { ++pending; ++ptr; }
        if (pending > 0) { --pending; ++read; }
        else if (localDone < local) ++localDone;
    }
    return t;
}
struct ScanPlan { int W = 1; bool coordQueries = true; int firstWorker = 0; long long est = INF; };
static ScanPlan choose_scan() {
    ScanPlan best;
    // coordinator queries: W in [1, NUM_AGENTS]
    for (int W = 1; W <= NUM_AGENTS; ++W) { long long e = estimate_scan(W, true); if (e < best.est) best = {W, true, 0, e}; }
    // pure receiver: W workers in [1, NUM_AGENTS-1]
    for (int W = 1; W <= NUM_AGENTS - 1; ++W) { long long e = estimate_scan(W, false); if (e < best.est) best = {W, false, 1, e}; }
    return best;
}

// ---- Two-level aggregation, for the read-bound corner (small board, many agents).
// There, direct scan is bottlenecked by the coordinator reading one tiny message per
// worker.  Grouping W workers under G leaders that each forward a merged stream drops
// the coordinator's reads from ~W to ~G.  Agents 1..W scan; the G leaders are agents
// 1..G; member wid streams to leader (wid % G)+1; the coordinator reads G leaders.
static inline long long enc_len_bits(long long bits){ if(bits<=0) return 0; long long q=bits/13,r=bits%13; return 2*q+(r==0?0:(r<=6?1:2)); }
static inline long long chunks_chars(long long chars){ return chars<=0?0:(chars+PAYLOAD-1)/PAYLOAD; }
static string scan_partition_enc(int W, int wid){ BitPacker bp; for(long long rank=wid; rank<EDGE_COUNT; rank+=W) bp.add(ask(EDGE_ORDER[(size_t)rank])); return bp.finish(); }
static void send_stream(int to, const string &enc){ for(size_t p=0;p<enc.size();p+=(size_t)PAYLOAD) send_msg(to, enc.substr(p,min((size_t)PAYLOAD,enc.size()-p))); }
static void agg_member(int W, int G, int wid){ send_stream((wid % G) + 1, scan_partition_enc(W, wid)); halt_agent(); }
static void agg_leader(int W, int G, int gid){
    string agg = scan_partition_enc(W, gid);
    vector<int> mem; for(int wid=gid+G; wid<W; wid+=G) mem.push_back(wid);
    int M = (int)mem.size();
    vector<string> got(M); vector<long long> need(M); vector<long long> have(M,0); long long remaining=0;
    for(int i=0;i<M;++i){ need[i]=chunks_chars(enc_len_bits(part_count(EDGE_COUNT,W,mem[i]))); remaining+=need[i]; }
    while(remaining>0){ int s=-1; string b; if(!parse_msg(transact("< ?"),s,b)) continue; int wid=s-1,idx=-1; for(int i=0;i<M;++i) if(mem[i]==wid){idx=i;break;} if(idx<0||have[idx]>=need[idx]) continue; got[idx]+=b; ++have[idx]; --remaining; }
    for(int i=0;i<M;++i) agg += got[i];
    send_stream(0, agg); halt_agent();
}
static void agg_coordinator(int W, int G){
    vector<long long> need(G), have(G,0); vector<string> buf(G); long long remaining=0;
    for(int g=0;g<G;++g){ long long chars=0; for(int wid=g; wid<W; wid+=G) chars+=enc_len_bits(part_count(EDGE_COUNT,W,wid)); need[g]=chunks_chars(chars); remaining+=need[g]; }
    while(remaining>0){ int s=-1; string b; if(!parse_msg(transact("< ?"),s,b)) continue; int g=s-1; if(g<0||g>=G||have[g]>=need[g]) continue; buf[g]+=b; ++have[g]; --remaining; }
    for(int g=0;g<G;++g){ size_t pos=0; for(int wid=g; wid<W; wid+=G){ long long bits=part_count(EDGE_COUNT,W,wid); long long clen=enc_len_bits(bits);
        string piece = pos<buf[g].size() ? buf[g].substr(pos,(size_t)clen) : string();
        long long bit=0; decode_bits(piece,bits,[&](bool one){ long long rank=wid+bit*1LL*W; if(rank<EDGE_COUNT) apply_edge(EDGE_ORDER[(size_t)rank],one); ++bit; }); pos+=(size_t)clen; } }
    string p=solve_forest(); if(!p.empty()||ROOMS==1) claim_path(p); halt_agent();
}
// Rough claim-turn estimate for W workers under G leaders.
static long long estimate_agg(int W, int G){
    if (W<=0||G<=0||G>W) return INF;
    long long q = part_count(EDGE_COUNT, W, 0);                     // worker query time
    long long membersMax = (W - 0 + G - 1) / G;                    // wids in group 0
    long long leaderChars = 0; for(int wid=0; wid<W; wid+=G) leaderChars += enc_len_bits(part_count(EDGE_COUNT,W,wid));
    long long leaderDone = q + (membersMax - 1) + chunks_chars(leaderChars); // query + read members + emit
    return leaderDone + (long long)G + 2;                          // + coordinator reads G leaders
}
static int choose_agg_groups(int W, long long &est){
    est = INF; int bestG = 0;
    for (int G = 1; G <= W; ++G) { long long e = estimate_agg(W, G); if (e < est) { est = e; bestG = G; } }
    return bestG;
}

// ================= ACTIVE bidirectional trace =================
static const int DR[4] = {-1,1,0,0}, DC[4] = {0,0,-1,1};
static const int OPP[4] = {1,0,3,2};
static const int PREFS[8][4] = { {1,3,2,0},{3,1,0,2},{1,3,0,2},{3,1,2,0},{0,2,1,3},{2,0,3,1},{1,0,3,2},{3,2,1,0} };
static inline int move_room(int u, int dir) { int r=u/RM, c=u%RM; r+=DR[dir]; c+=DC[dir]; if(r<0||r>=RM||c<0||c>=RM) return -1; return r*RM+c; }
static inline long long edge_between_rooms(int u, int v) { int ur=u/RM,uc=u%RM,vr=v/RM,vc=v%RM; if(ur==vr) return horiz_ord(ur,min(uc,vc)); return vert_ord(min(ur,vr),uc); }
static inline unsigned hash_edge_tie(int a, int b, int aid){ if(a>b) swap(a,b); unsigned x=(unsigned)a*1000003u+(unsigned)b*9176u+(unsigned)aid*19260817u; x^=x>>16; x*=0x7feb352du; x^=x>>15; return x; }
// Greedy best-first frontier: instead of DFS (which fully explores a wrong
// subtree before backtracking), always expand the known-open frontier node
// closest to the target.  A wrong branch is abandoned as soon as a better
// frontier exists, so trap subtrees cost only their promising rim.  Both the
// worker and the coordinator run identical deterministic frontier logic, so a
// streamed open/closed bit sequence replays to the same node on both sides.
struct StepResult { bool queried=false, bit=false; int new_node=-1; bool found=false, exhausted=false; };
struct SearchState {
    int aid=0, side=0, mode=0, root=0, target=0, tr=0, tc=0;
    vector<signed char> parent_dir;
    struct FE { long long key; int u; signed char dir; };
    struct FECmp { bool operator()(const FE&a, const FE&b) const {
        if (a.key != b.key) return a.key > b.key;      // min-heap by key
        if (a.u   != b.u)   return a.u   > b.u;
        return a.dir > b.dir;
    }};
    priority_queue<FE, vector<FE>, FECmp> pq;
    long long node_key(int v) const {
        int vr=v/RM, vc=v%RM;
        long long man=llabs(vr-tr)+llabs(vc-tc);
        long long cheb=max(llabs(vr-tr),llabs(vc-tc));
        long long diag=llabs((vr-vc)-(tr-tc));
        long long anti=llabs((vr+vc)-(tr+tc));
        long long base;
        switch (mode % 5) {
            case 1:  base = man*2 + diag; break;
            case 2:  base = cheb*2 + man;  break;
            case 3:  base = man*2 + anti;  break;
            case 4:  base = diag + man;    break;
            default: base = man;           break;
        }
        return base*4096LL + (hash_edge_tie(v, v, aid) & 4095);
    }
    void push_edges(int u) {
        for (int d=0; d<4; ++d) { int v=move_room(u,d); if (v<0 || parent_dir[v]!=(signed char)-1) continue; pq.push({node_key(v), u, (signed char)d}); }
    }
    void init(int aid_, int side_, int mode_) {
        aid=aid_; side=side_; mode=mode_;
        root=(side==0?0:(int)ROOMS-1); target=(side==0?(int)ROOMS-1:0);
        tr=(side==0?RM-1:0); tc=tr;
        parent_dir.assign((size_t)ROOMS,(signed char)-1);
        while (!pq.empty()) pq.pop();
        parent_dir[root]=(signed char)-2; push_edges(root);
    }
    bool peek(int &u, int &dir, int &v) {   // next valid frontier edge (drops stale ones)
        while (!pq.empty()) { FE f=pq.top(); int vv=move_room(f.u,f.dir); if (vv<0 || parent_dir[vv]!=(signed char)-1) { pq.pop(); continue; } u=f.u; dir=f.dir; v=vv; return true; }
        return false;
    }
    StepResult step_query() {
        StepResult res; int u,dir,v;
        if (!peek(u,dir,v)) { res.exhausted=true; return res; }
        pq.pop();
        bool open = ask(edge_between_rooms(u,v));
        res.queried=true; res.bit=open;
        if (open) { parent_dir[v]=(signed char)OPP[dir]; res.new_node=v; push_edges(v); if (v==target) res.found=true; }
        return res;
    }
    int apply_bit(bool open) {
        int u,dir,v; if (!peek(u,dir,v)) return -1;
        pq.pop();
        if (open) { parent_dir[v]=(signed char)OPP[dir]; push_edges(v); return v; }
        return -1;
    }
};
static vector<int> nodes_root_to(const SearchState &s, int node) {
    vector<int> rev; int cur=node, guard=0;
    while (true) {
        if (cur<0||cur>=(int)ROOMS||++guard>(int)ROOMS+1) return {};
        rev.push_back(cur); if (cur==s.root) break;
        int d=(int)s.parent_dir[cur]; if (d<0||d>3) return {};
        cur = move_room(cur, d);
    }
    reverse(rev.begin(), rev.end()); return rev;
}
static char dir_between(int a, int b) { if(b==a-RM) return 'U'; if(b==a+RM) return 'D'; if(b==a-1) return 'L'; if(b==a+1) return 'R'; return '?'; }
static string expand_rooms(const string &rp){ string full; full.reserve(rp.size()*2); for(char ch:rp){ full.push_back(ch); full.push_back(ch);} return full; }
static string direct_claim(const SearchState &s) {
    vector<int> a = nodes_root_to(s, s.target); if (a.empty()) return "";
    string rp;
    if (s.side==0) for (size_t i=1;i<a.size();++i) rp.push_back(dir_between(a[i-1],a[i]));
    else for (int i=(int)a.size()-1;i>=1;--i) rp.push_back(dir_between(a[i],a[i-1]));
    return expand_rooms(rp);
}
// Fold an open edge (any agent found) into the shared known-open forest and claim
// the moment it links the two terminals.  Adjacent rooms already in one component
// means the edge was seen before -- a clean dedup, since the true maze is a tree.
static inline void apply_room_edge(int u, int v) {
    if (u<0 || v<0 || u>=(int)ROOMS || v>=(int)ROOMS) return;
    if (DS.find(u) == DS.find(v)) return;
    ADJ[u][DEG[u]++]=v; ADJ[v][DEG[v]++]=u;
    DS.unite(u,v);
    if (DS.find(0)==DS.find((int)ROOMS-1)) { string p=solve_forest(); if(!p.empty()||ROOMS==1) claim_path(p); }
}
static int active_side_for(int id) { if (id==0) return 0; if (ACTIVE_AGENTS<=3) return 1; return (id&1)?1:0; }
static int active_mode_for(int id) {
    if (id==0) return 0;
    static const int modes[] = {8,6,10,11,4,5,12,13,1,3,0,2,9,7};
    int side=active_side_for(id), rank=0;
    for (int j=1;j<id;++j) if (active_side_for(j)==side) ++rank;
    return modes[rank % (int)(sizeof(modes)/sizeof(modes[0]))];
}
static int trace_flush_bits() {
    // Best-first tracers connect the union sooner with small chunks (fresh edges reach
    // the coordinator quickly); reads are never the bottleneck at these agent counts.
    int cap = max(13, (PAYLOAD/2)*13);
    int target = (RM <= 60) ? 104 : 208;
    return max(13, min(target,cap)/13*13);
}
static void active_worker() {
    SearchState s; s.init(AGENT_ID, active_side_for(AGENT_ID), active_mode_for(AGENT_ID));
    BitPacker bp; const int F = trace_flush_bits();
    while (true) {
        if (bp.bits >= F) { send_msg(0, bp.finish()); continue; }
        StepResult r = s.step_query();
        if (r.queried) { bp.add(r.bit); if (r.found) claim_path(direct_claim(s)); }
        else if (r.found) claim_path(direct_claim(s));
        else if (r.exhausted) halt_agent();
    }
}
static void active_coordinator() {
    vector<SearchState> states(ACTIVE_AGENTS);
    for (int id=0; id<ACTIVE_AGENTS; ++id) states[id].init(id, active_side_for(id), active_mode_for(id));
    // Every edge any tracer confirms open feeds one shared forest; the union links
    // the terminals far earlier than waiting for a single s/t tracer pair to meet,
    // and each extra agent grows the union faster -- so ACTIVE now scales with count.
    auto add = [&](SearchState &st, int v){ if (v>=0) apply_room_edge(move_room(v, st.parent_dir[v]), v); };
    const int TRACE_FLUSH = trace_flush_bits();
    long long turn=0, next_recv=(long long)TRACE_FLUSH+2; int burst=0;
    while (true) {
        ++turn;
        bool do_recv = (burst>0) || (turn>=next_recv);
        if (do_recv) {
            int sender=-1; string body; bool got = parse_msg(transact("< ?"), sender, body);
            if (!got || sender<=0 || sender>=ACTIVE_AGENTS || body.empty()) {
                burst=0; while (next_recv<=turn) next_recv += (long long)TRACE_FLUSH+1; continue;
            }
            if (burst==0) burst=max(0,ACTIVE_AGENTS-2); else --burst;
            SearchState &st=states[sender];
            decode_pairs(body, [&](bool bit){ add(st, st.apply_bit(bit)); });
        } else {
            StepResult r = states[0].step_query();
            if (r.queried) { add(states[0], r.new_node); if(r.found) claim_path(direct_claim(states[0])); }
            else if (r.found) claim_path(direct_claim(states[0]));
            else if (r.exhausted) (void)transact("< ?");
        }
    }
}
// ACTIVE's best-first cost is roughly flat in agent count while SCAN falls as
// ~EDGE_COUNT/agents, so ACTIVE wins only up to a small crossover count (measured
// against the referee's generator).  It is a touch lower on tiny boards, where SCAN
// parallelises almost for free.
static int active_max_agents() {
    if (MAX_MSG_LEN < 16 || NUM_AGENTS < 3 || N < 51) return 0;
    if (FORCE_ACTIVE_MAX >= 0) return FORCE_ACTIVE_MAX;   // tuning override
    return RM <= 30 ? 4 : 6;
}
static bool use_active() { int m = active_max_agents(); return m >= 3 && NUM_AGENTS <= m; }

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    if (!(cin >> N >> NUM_AGENTS >> AGENT_ID >> MAX_MSG_LEN)) return 0;
    string dummy; getline(cin, dummy);
    RM = (N + 1) / 2; ROOMS = 1LL*RM*RM; H_EDGES = (RM>=1)?1LL*RM*(RM-1):0; EDGE_COUNT = 2*H_EDGES; PAYLOAD = max(1, MAX_MSG_LEN);

    if (N == 1) { if (AGENT_ID == 0) claim_path(""); halt_agent(); }

    EDGE_ORDER = build_edge_order();
    DS.init((int)ROOMS); ADJ.assign((size_t)ROOMS, array<int,4>{}); DEG.assign((size_t)ROOMS, 0);

    // Tiny-message safety: a single agent scans and early-connects on its own.
    if (PAYLOAD < 2) {
        if (AGENT_ID == 0) { for (long long rank=0; rank<EDGE_COUNT; ++rank) apply_edge(EDGE_ORDER[(size_t)rank], ask(EDGE_ORDER[(size_t)rank])); string p=solve_forest(); if(!p.empty()||ROOMS==1) claim_path(p); }
        halt_agent();
    }

    if (use_active()) {
        ACTIVE_AGENTS = NUM_AGENTS;
        if (AGENT_ID < ACTIVE_AGENTS) { if (AGENT_ID == 0) active_coordinator(); else active_worker(); }
        else halt_agent();
    }

    // SCAN: pick the cheapest of direct (early-connect) and two-level aggregation.
    ScanPlan scan = choose_scan();
    // Aggregation helps only when workers cannot pipeline: if each worker's share is
    // under one chunk (W * F > EDGE_COUNT) it sends a single message at the very end,
    // so the coordinator's ~W reads serialize AND arrive too late for early-connect to
    // help.  There the coarse full-scan estimates are accurate and aggregation (which
    // cuts reads from ~W to ~G) genuinely wins.  Below that threshold, direct scan
    // pipelines and early-connects -- gains the estimates cannot see -- so never switch.
    long long aggEst = INF; int aggW = NUM_AGENTS - 1, aggG = 0;
    if (aggW >= 2 && 5LL * aggW * scan_flush_bits() > 3 * EDGE_COUNT) aggG = choose_agg_groups(aggW, aggEst);

    if (aggG >= 1 && aggEst < scan.est) {
        int W = aggW, G = aggG;
        if (AGENT_ID == 0) agg_coordinator(W, G);
        else if (AGENT_ID <= G) agg_leader(W, G, AGENT_ID - 1);        // leaders = agents 1..G
        else if (AGENT_ID <= W) agg_member(W, G, AGENT_ID - 1);        // members
        else halt_agent();
    } else if (scan.coordQueries) {
        if (AGENT_ID == 0) coordinator_scan(scan.W, true, 0);
        else if (AGENT_ID < scan.W) worker_scan(0, scan.W, AGENT_ID);
        else halt_agent();
    } else {
        if (AGENT_ID == 0) coordinator_scan(scan.W, false, scan.firstWorker);
        else if (AGENT_ID >= scan.firstWorker && AGENT_ID < scan.firstWorker + scan.W) worker_scan(0, scan.W, AGENT_ID - scan.firstWorker);
        else halt_agent();
    }
    return 0;
}