// 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.
#include <bits/stdc++.h>
using namespace std;

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 main(int argc, char** argv){
    (void)argc; (void)argv;
    for(int i=0;i<64;i++) b64inv[(unsigned char)B64[i]]=i;
    string first; if(!getline(cin, first)) return 0;
    { 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({});
    }
}