#include using namespace std; #include using namespace atcoder; using ll = long long; using P = pair; using TUP = tuple; map state_idx; int N; int dx[] = {1,0,-1,0}; int dy[] = {0,1,0,-1}; string ds = "DRUL"; string buff; int roopst = -1; void dfs(TUP cur,int turn){ if(state_idx.count(cur)&&turn%4==0){ auto [nxp,nxg] = cur; //cout<=5)continue; if(nxp.second<0||nxp.second>=5)continue; if(turn%4==3){ auto tmp = get<0>(cur); for(int i = 0;i<3;i++){ auto move = buff[buff.size()-1-i]; if(move=='U')tmp.first++; if(move=='D')tmp.first--; if(move=='L')tmp.second++; if(move=='R')tmp.second--; } nxg = tmp; } if(nxp.first==nxg.first||nxp.second==nxg.second){ continue; } TUP nx(nxp,nxg); buff.push_back(ds[i]); dfs(nx,turn+1); if(roopst!=-1)break; buff.pop_back();; } state_idx.erase(cur); } void solve(){ auto cur = TUP(P(0,0),P(-1,-1)); dfs(cur,0); ll loopsize = buff.size()-roopst; string loop = buff.substr(roopst,loopsize); while(buff.size()> N; solve(); }