#include using namespace std; #define MAXN 20010 #define INF 0x3f3f3f3f #define mo 1000000007 typedef long long LL; namespace Shortest_Path{ const int Maxn = 1e5 + 10; int n, s, t, dis[Maxn]; int pre[MAXN]; bool vis[Maxn]; vector< int > adj[Maxn]; queue< int > SPFA_que; void Init(int N, int S, int T){ n = N; s = S; t = T; memset(dis, 0x3f, sizeof(dis)); memset(pre, -1, sizeof(pre)); memset(vis, 0, sizeof(vis)); dis[s] = 0; for(int i = 0; i < n; ++i) adj[i].clear(); } inline void Addedge(int u, int v){ adj[u].push_back(v); } int SPFA(){ for(SPFA_que.push(s), vis[s]=true; !SPFA_que.empty(); ){ auto u = SPFA_que.front(); SPFA_que.pop(); vis[u] = false; for(auto &it: adj[u]){ if(dis[u] + 1 >= dis[it]) continue; dis[it] = dis[u] + 1; pre[it] = u; if(!vis[it]) vis[it] = true, SPFA_que.push(it); } } return dis[t]; } } int n, g[6][2] = {{-2, -1}, {-2, 1}, {0, 2}, {2, 1}, {2, -1}, {0, -2}}; void Init() { int x1, y1, x2, y2; scanf("%d %d %d %d %d", &n, &x1, &y1, &x2, &y2); Shortest_Path::Init(n * n, x1 * n + y1, x2 * n + y2); for(int i = 0; i < n; ++i) for(int j = 0; j < n; ++j){ for(int k = 0; k < 6; ++k){ int x = i + g[k][0]; int y = j + g[k][1]; if(x < 0 || x >= n || y < 0 || y >= n) continue; Shortest_Path::Addedge(i * n + j, x * n + y); } } } char s[6][10] = {"UL", "UR", "R", "LR", "LL", "L"}; char* Op(int u, int v) { int x1 = u / n, y1 = u % n, x2 = v / n, y2 = v % n; for(int k = 0; k < 6; ++k){ int x = x1 + g[k][0]; int y = y1 + g[k][1]; if(x == x2 && y == y2) return s[k]; } return NULL; } void Work() { Shortest_Path::SPFA(); if(Shortest_Path::dis[Shortest_Path::t] == INF){ printf("Impossible\n"); return; } vector< int > road; for(int u = Shortest_Path::t; u != -1; u = Shortest_Path::pre[u]) road.push_back(u); reverse(road.begin(), road.end()); printf("%d\n", (int)road.size() - 1); int pre = -1; for(auto &it: road){ if(pre != -1){ printf("%s ", Op(pre, it)); } pre = it; } } int main() { #ifdef MYCP freopen("data.in", "r", stdin); #endif // MYCP Init(); Work(); return 0; }