#include using namespace std; typedef pair P; struct cmp { bool operator()(const P& lhs, const P& rhs) { return lhs < rhs; } }; bool pos(int u, P di, int n) { int x=u/n,y=u%n; if(x+di.first>=n || x+di.first<0 || y+di.second>=n || y+di.second<0) return false; return true; } int new_pos(int u, P di, int n) { int x=u/n,y=u%n; return ((x+di.first)*n + (y+di.second)); } void printShortestPath(int n, int i_start, int j_start, int i_end, int j_end) { vector dist(n*n, INT_MAX), parent(n*n, -1); priority_queue< P, vector

, cmp > pq; vector

dir; dir.push_back({-2,-1});dir.push_back({-2,1});dir.push_back({0,2}); dir.push_back({2,1});dir.push_back({2,-1});dir.push_back({0,-2}); dist[i_start*n+j_start]=0; pq.push({0,i_start*n+j_start}); while(!pq.empty()) { int u = pq.top().second; pq.pop(); for(int i=0;i<6;i++) { if(pos(u, dir[i], n)) { int v = new_pos(u,dir[i],n); if(dist[v]>dist[u]+1) { parent[v]=u; dist[v] = dist[u] + 1; pq.push({dist[v], v}); } else if(dist[v]==dist[u]+1) { int x1=parent[v]/n,y1=parent[v]%n; int x2=u/n,y2=u%n; int vx=v/n,vy=v%n; int t1=vx-x2,t2=vy-y2,ind1; for(int i=0;i<6;i++) if(t1==dir[i].first && t2==dir[i].second) { ind1=i; break; } int t3=vx-x1,t4=vy-y1,ind2; for(int i=0;i<6;i++) if(t3==dir[i].first && t4==dir[i].second) { ind2=i; break; } if(ind1>ind2) parent[v]=u; } } } } vector moves; int v = ((i_end*n)+j_end); while(parent[v]!=-1) { int t=parent[v]; int x1=t/n,y1=t%n; int x2=v/n,y2=v%n; if((x2-x1)==2){ if(y2-y1==1) moves.push_back("LR"); else moves.push_back("LL"); } else if((x2-x1)==0){ if(y2-y1==2) moves.push_back("R"); else moves.push_back("L"); } if((x2-x1)==-2){ if(y2-y1==1) moves.push_back("UR"); else moves.push_back("UL"); } v=t; } if(dist[i_end*n + j_end]!=INT_MAX){ reverse(moves.begin(), moves.end()); cout << dist[i_end*n + j_end] << "\n"; for(vector::iterator it=moves.begin(); it!=moves.end(); it++) cout << *it << " "; cout << "\n"; } else { cout << "Impossible\n"; } return ; } int main() { int n; cin >> n; int i_start; int j_start; int i_end; int j_end; cin >> i_start >> j_start >> i_end >> j_end; printShortestPath(n, i_start, j_start, i_end, j_end); return 0; }