#include #include #include using namespace std; int c = 0; vector pila; int distance(int i, int j, int i2, int j2) { return abs(i2 - i) + abs(j2 - j); } bool solve(int n, int i, int j, int i2, int j2) { if (i == i2 && j == j2) { return true; } if (i < 0 || i >= n || j < 0 || j >= n) { return false; } int current_distance = distance(i, j, i2, j2); if (i - 2 == i2 && j - 1 == j2) { ++c; pila.push_back("UL"); return true; } if (i - 2 == i2 && j + 1 == j2) { ++c; pila.push_back("UR"); return true; } if (i + 2 == i2 && j + 1 == j2) { ++c; pila.push_back("LR"); return true; } if (i + 2 == i2 && j - 1 == j2) { ++c; pila.push_back("LL"); return true; } if (i == i2) { if (distance(i, j + 2, i2, j2) < current_distance && solve(n, i, j + 2, i2, j2)) { ++c; pila.push_back("R"); return true; } if (distance(i, j - 2, i2, j2) < current_distance && solve(n, i, j - 2, i2, j2)) { ++c; pila.push_back("L"); return true; } return false; } if (distance(i, j - 1, i2, j2) < current_distance) { if (distance(i - 2, j - 1, i2, j2) < current_distance && solve(n, i - 2, j - 1, i2, j2)) { ++c; pila.push_back("UL"); return true; } if (distance(i + 2, j - 1, i2, j2) < current_distance && solve(n, i + 2, j - 1, i2, j2)) { ++c; pila.push_back("LL"); return true; } } else{ if (distance(i - 2, j + 1, i2, j2) < current_distance && solve(n, i - 2, j + 1, i2, j2)) { ++c; pila.push_back("UR"); return true; } if (distance(i + 2, j + 1, i2, j2) < current_distance && solve(n, i + 2, j + 1, i2, j2)) { ++c; pila.push_back("LR"); return true; } } return false; } void printShortestPath(int n, int i_start, int j_start, int i_end, int j_end) { if (abs(i_end - i_start) % 2 != 0) { cout << "Impossible" << endl; return; } if (abs(i_end - i_start) % 4 == 0 && abs(j_end - j_start) % 2 != 0) { cout << "Impossible" << endl; return; } if (abs(i_end - i_start) % 4 != 0 && abs(i_end - i_start) % 2 == 0 && abs(j_end - j_start) % 2 == 0) { cout << "Impossible" << endl; return; } if (solve(n, i_start, j_start, i_end, j_end)) { cout << c << endl; for (int i = pila.size() - 1; i > 0; --i) { cout << pila[i] << " "; } cout << pila.front(); } } 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; }