#include using namespace std; bool impossible = false; void subtle(int n, int i_start, int i_end, int upleft, int upright) { int init_left = min(upleft, i_end); for (int i = 0; i < init_left; ++i) { cout << "UL "; } int remaining_left = upleft - init_left; for (int i = 0; i < remaining_left; ++i) { cout << "UR UL "; } for (int i = 0; i < upright - remaining_left; ++i) { cout << "UR "; } } void subtle2(int n, int i_start, int i_end, int downleft, int downright) { int init_right = min(downright, n - 1 - i_end); for (int i = 0; i < init_right; ++i) { cout << "LR "; } int remaining_right = downright - init_right; for (int i = 0; i < remaining_right; ++i) { cout << "LL LR "; } for (int i = 0; i < downleft - remaining_right; ++i) { cout << "LL "; } } void printShortestPath(int n, int i_start, int i_end, int j_start, int j_end) { // Impossible case if ((j_start - i_start) % 2 != 0) { impossible = true; // cout << "case1" << endl; return; } if ((j_start - i_start) % 4 == 0 and (j_end - i_end) % 2 != 0 ) { impossible = true; // cout << "case2" << endl; return; } if ((j_start - i_start) % 4 == 2 and (j_end - i_end) % 2 == 0 ) { impossible = true; // cout << "case3" << endl; return; } // External Bound Check if (!(i_start < n and j_start < n and j_end < n and i_end < n and i_start >= 0 and j_start >= 0 and i_end >= 0 and j_end >= 0)) { impossible = true; // cout << "case4" << endl; return; } // Possible cases //Case UpLeft if (i_start > j_start and i_end > j_end) { int upleft_moves = (i_start - j_start) / 2; if ((i_end - j_end) >= upleft_moves) { int left_moves = ((i_end - j_end) - upleft_moves) / 2; cout << upleft_moves + left_moves << endl; for (int i = 0; i < upleft_moves; ++i) { cout << "UL "; } for (int i = 0; i < left_moves; ++i) { cout << "L "; } } else { int left_moves = (i_end - j_end); int up_moves = (i_start - j_start) / 2 - left_moves; cout << up_moves + left_moves << endl; subtle(n, i_start, i_end, left_moves + up_moves/2, up_moves/2); } } //Case Up (INT CHECK) else if (i_start > j_start and i_end == j_end) { int up_moves = (i_start - j_start) / 2; cout << up_moves << endl; subtle(n, i_start, i_end, up_moves/2, up_moves/2); } //Case UpRight else if (i_start > j_start and i_end < j_end) { int upright_moves = (i_start - j_start) / 2; int right_moves = ((j_end - i_end) - upright_moves) / 2; if (right_moves >= 0) { cout << upright_moves + right_moves << endl; for (int i = 0; i < upright_moves; ++i) { cout << "UR "; } for (int i = 0; i < right_moves; ++i) { cout << "R "; } } else { right_moves = (j_end - i_end); int up_moves = upright_moves - right_moves; cout << up_moves + right_moves << endl; subtle(n, i_start, i_end, up_moves/2, up_moves/2 + right_moves); } } //Case Right else if (i_start == j_start and i_end < j_end) { int right_moves = (j_end - i_end) / 2; cout << right_moves << endl; for (int i = 0; i < right_moves; ++i) { cout << "R "; } } //Case DownRight else if (i_start < j_start and i_end < j_end) { int downright_moves = (j_start - i_start) / 2; int right_moves = ((j_end - i_end) - downright_moves) / 2; if (right_moves >= 0) { cout << downright_moves + right_moves << endl; for (int i = 0; i < right_moves; ++i) { cout << "R "; } for (int i = 0; i < downright_moves; ++i) { cout << "LR "; } } else { right_moves = (j_end - i_end); int down_moves = downright_moves - right_moves; cout << down_moves + right_moves << endl; subtle2(n, i_start, i_end, down_moves/2, down_moves/2 + right_moves); } } //Case Down (INT CHECK) else if (i_start < j_start and i_end == j_end) { int down_moves = (j_start - i_start) / 2; cout << down_moves << endl; subtle2(n, i_start, i_end, down_moves/2, down_moves/2); } //Case DownLeft else if (i_start < j_start and i_end > j_end) { int downleft_moves = (j_start - i_start) / 2; int left_moves = ((i_end - j_end) - downleft_moves) / 2; if (left_moves >= 0) { cout << downleft_moves + left_moves << endl; for (int i = 0; i < downleft_moves; ++i) { cout << "LL "; } for (int i = 0; i < left_moves; ++i) { cout << "L "; } } else { left_moves = (i_end - j_end); int down_moves = downleft_moves - left_moves; cout << down_moves + left_moves << endl; subtle2(n, i_start, i_end, down_moves/2 + left_moves, down_moves/2); } } //Case Left else if (i_start == j_start and i_end > j_end) { int left_moves = (i_end - j_end) / 2; cout << left_moves << endl; for (int i = 0; i < left_moves; ++i) { cout << "L "; } } cout << endl; } 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); if (impossible) { cout << "Impossible" << endl; } return 0; }