#include using namespace std; bool flag[40050]; int par[40050], dir[40050]; vector dirText = {"UL", "UR", "R", "LR", "LL", "L"}; int pairToInt(pair x, int n) { return x.first * n + x.second; } pair intToPair(int x, int n) { return make_pair(x / n, x % n); } void printShortestPath(int n, int i_start, int j_start, int i_end, int j_end) { memset(flag, false, sizeof(flag)); memset(par, -1, sizeof(par)); memset(dir, -1, sizeof(dir)); queue, int>> q; int prev = pairToInt(make_pair(0, -1), n); int cur = pairToInt(make_pair(i_start, j_start), n); q.push(make_pair(make_pair(prev, cur), -1)); while (q.size()) { prev = q.front().first.first; cur = q.front().first.second; int dr = q.front().second; pair prevPair = intToPair(prev, n); pair curPair = intToPair(cur, n); q.pop(); if ((curPair.first == i_end) && (curPair.second == j_end)) { vector steps; steps.push_back(dr); while (par[prev] != -1) { steps.push_back(dir[prev]); prev = par[prev]; } printf("%d\n", (int)steps.size()); for (int i = steps.size() - 1; i >= 0; i--) { cout << dirText[steps[i]]; if (i > 0) { printf(" "); } else { printf("\n"); } } return; } if (!flag[cur]) { flag[cur] = true; par[cur] = prev; dir[cur] = dr; pair nextPair; int next; nextPair = make_pair(curPair.first - 2, curPair.second - 1); if ((nextPair.first >= 0) && (nextPair.first < n) && (nextPair.second >= 0) && (nextPair.second < n)) { next = pairToInt(nextPair, n); if (!flag[next]) { q.push(make_pair(make_pair(cur, next), 0)); } } nextPair = make_pair(curPair.first - 2, curPair.second + 1); if ((nextPair.first >= 0) && (nextPair.first < n) && (nextPair.second >= 0) && (nextPair.second < n)) { next = pairToInt(nextPair, n); if (!flag[next]) { q.push(make_pair(make_pair(cur, next), 1)); } } nextPair = make_pair(curPair.first, curPair.second + 2); if ((nextPair.first >= 0) && (nextPair.first < n) && (nextPair.second >= 0) && (nextPair.second < n)) { next = pairToInt(nextPair, n); if (!flag[next]) { q.push(make_pair(make_pair(cur, next), 2)); } } nextPair = make_pair(curPair.first + 2, curPair.second + 1); if ((nextPair.first >= 0) && (nextPair.first < n) && (nextPair.second >= 0) && (nextPair.second < n)) { next = pairToInt(nextPair, n); if (!flag[next]) { q.push(make_pair(make_pair(cur, next), 3)); } } nextPair = make_pair(curPair.first + 2, curPair.second - 1); if ((nextPair.first >= 0) && (nextPair.first < n) && (nextPair.second >= 0) && (nextPair.second < n)) { next = pairToInt(nextPair, n); if (!flag[next]) { q.push(make_pair(make_pair(cur, next), 4)); } } nextPair = make_pair(curPair.first, curPair.second - 2); if ((nextPair.first >= 0) && (nextPair.first < n) && (nextPair.second >= 0) && (nextPair.second < n)) { next = pairToInt(nextPair, n); if (!flag[next]) { q.push(make_pair(make_pair(cur, next), 5)); } } } } printf("Impossible\n"); } 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; }