#include using namespace std; void printShortestPath(int n, int y1, int x1, int y2, int x2) { constexpr array names = {"UL", "UR", "R", "LR", "LL", "L"}; constexpr array dx = {-1, 1, 2, 1,-1,-2}; constexpr array dy = {-2,-2, 0, 2, 2, 0}; vector> board(n*n, {numeric_limits::max(), -1}); auto len = [&board, n](int x, int y) -> unsigned& { return board[x*n+y].first; }; auto back = [&board, n](int x, int y) -> char& { return board[x*n+y].second; }; len(x1, y1) = 0; vector> curr = {{x1, y1}}, next; unsigned cur_len = 1; while (!curr.empty()) { for (const auto& p: curr) { int x, y; tie(x, y) = p; if (x == x2 && y == y2) { cout << len(x, y) << '\n'; vector path; path.reserve(len(x, y)); while (back(x, y) != -1) { auto idx = back(x, y); path.push_back(idx); x -= dx[idx]; y -= dy[idx]; } for (auto it = path.rbegin(); it != path.rend(); ++it) cout << names[*it] << ' '; cout << '\n'; return; } for (char i = 0; i < 6; ++i) { int xx = x + dx[i], yy = y + dy[i]; if (xx >= 0 && xx < n && yy >= 0 && yy < n && len(xx, yy) == numeric_limits::max()) { len(xx, yy) = cur_len; back(xx, yy) = i; next.emplace_back(xx, yy); } } } cur_len++; curr = move(next); } cout << "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; }