#include #include #include #include #include using namespace std; struct mv { int di, dj; int id; mv() : mv(0, 0, -1) {} mv(int di, int dj, int id) : di(di), dj(dj), id(id) {} bool operator==(const mv& m) const { return di == m.di && dj == m.dj && id == m.id; } bool operator!=(const mv& m) const { return !(*this == m); } mv operator-() const { return {-di, -dj, (id + 3) % 6}; } }; struct cell { int i, j; cell() : cell(-1, -1) {} cell(int i, int j) : i(i), j(j) {} bool operator==(const cell &p) const { return i == p.i && j == p.j; } bool operator!=(const cell &p) const { return !(*this == p); } cell& operator+=(const mv &m) { i += m.di; j += m.dj; return *this; } }; cell operator+(cell p, const mv &m) { p += m; return p; } const vector move_codes{"UL", "UR", "R", "LR", "LL", "L"}; const vector moves{ {-2, -1, 0}, {-2, 1, 1}, {0, 2, 2}, {2, 1, 3}, {2, -1, 4}, {0, -2, 5} }; const mv non_move; bool is_valid(cell &p, int n) { return 0 <= p.i && p.i < n && 0 <= p.j && p.j < n; } int main() { int n; cell start, end; cin >> n >> start.i >> start.j >> end.i >> end.j; vector> seen(n, vector(n)); seen[start.i][start.j] = moves[0]; queue q; q.push(start); while (!q.empty()) { auto p = q.front(); q.pop(); if (p == end) { break; } for (auto &m : moves) { auto next_p = p + m; if (!is_valid(next_p, n)) { continue; } auto &s = seen[next_p.i][next_p.j]; if (s != non_move) { continue; } s = -m; q.push(next_p); } } auto &s = seen[end.i][end.j]; if (s == non_move) { cout << "Impossible\n"; } else { vector ans; cell p = end; while (p != start) { auto &m = seen[p.i][p.j]; p = p + m; ans.push_back(-m); } reverse(ans.begin(), ans.end()); cout << ans.size() << '\n'; for (auto &m : ans) { cout << move_codes[m.id] << ' '; } cout << '\n'; } return 0; }