#include using namespace std; struct Node { int x; int y; int depth = -1; int move; Node *edges[6] = {nullptr, nullptr, nullptr, nullptr, nullptr, nullptr}; }; void printMove(int ind) { switch(ind) { case 0: cout << "L "; break; case 1: cout << "LL "; break; case 2: cout << "LR "; break; case 3: cout << "R "; break; case 4: cout << "UR "; break; case 5: cout << "UL "; break; default: break; } } void printShortestPath(int n, int i_start, int j_start, int i_end, int j_end) { vector board(n*n); for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) { board[i*n + j].x = i; board[i*n + j].y = j; if (j + 2 < n) { board[i*n + j].edges[3] = &board[i*n + j + 2]; } if (j + 1 < n && i - 2 >= 0) { board[i*n + j].edges[4] = &board[(i-2)*n + j + 1]; } if (j - 1 >= 0 && i - 2 >= 0) { board[i*n + j].edges[5] = &board[(i-2)*n + j - 1]; } if (j - 2 >= 0) { board[i*n + j].edges[0] = &board[i*n + j - 2]; } if (j - 1 >= 0 && i + 2 < n) { board[i*n + j].edges[1] = &board[(i+2)*n + j - 1]; } if (j + 1 < n && i + 2 < n) { board[i*n + j].edges[2] = &board[(i+2)*n + j + 1]; } } } deque gray_nodes; board[i_end*n + j_end].depth = 0; gray_nodes.push_back(board[i_end*n + j_end]); while (!gray_nodes.empty()) { auto top = gray_nodes.front(); gray_nodes.pop_front(); for (int i = 0; i < 6; ++i) { if (top.edges[i]) { if (top.edges[i]->depth == -1) { top.edges[i]->depth = top.depth + 1; top.edges[i]->move = (3+i)%6; gray_nodes.push_back(*top.edges[i]); } else { if (top.edges[i]->depth == top.depth + 1) { top.edges[i]->move = max((3+i)%6, top.edges[i]->move); } } } } } int d = board[i_start*n + j_start].depth; if (d == -1) { cout << "Impossible" << endl; } else { vector path; Node *cur = &board[i_start*n + j_start]; cout << d << "\n"; while (d != 0) { path.push_back(cur->move); printMove(cur->move); cur = cur->edges[cur->move]; d = cur->depth; } } } 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; }