#include using namespace std; void printShortestPath(int n, int i_start, int j_start, int i_end, int j_end) { int visit[n+1][n+1], least[n+1][n+1], x[n+1][n+1], y[n+1][n+1], mode[n+1][n+1]; memset(visit, 0, sizeof(visit)); queue< pair > q; q.push(make_pair(j_start, i_start)); visit[j_start][i_start] = 1; least[j_start][i_start] = 0; x[j_start][i_start] = y[j_start][i_start] = -1; mode[j_start][i_start] = -1; while (!q.empty()) { pair temp = q.front(); q.pop(); //cout<= 0 and x1 < n and y1 >= 0 and y1 < n and visit[x1][y1] == 0) { visit[x1][y1] = 1; least[x1][y1] = least[temp.first][temp.second]+1; x[x1][y1] = temp.first; y[x1][y1] = temp.second; mode[x1][y1] = 1; q.push(make_pair(x1, y1)); } x1 += 2; if (x1 >= 0 and x1 < n and y1 >= 0 and y1 < n and visit[x1][y1] == 0) { visit[x1][y1] = 1; least[x1][y1] = least[temp.first][temp.second]+1; x[x1][y1] = temp.first; y[x1][y1] = temp.second; mode[x1][y1] = 2; q.push(make_pair(x1, y1)); } x1++; y1 += 2; if (x1 >= 0 and x1 < n and y1 >= 0 and y1 < n and visit[x1][y1] == 0) { visit[x1][y1] = 1; least[x1][y1] = least[temp.first][temp.second]+1; x[x1][y1] = temp.first; y[x1][y1] = temp.second; mode[x1][y1] = 3; q.push(make_pair(x1, y1)); } x1--; y1 += 2; if (x1 >= 0 and x1 < n and y1 >= 0 and y1 < n and visit[x1][y1] == 0) { visit[x1][y1] = 1; least[x1][y1] = least[temp.first][temp.second]+1; x[x1][y1] = temp.first; y[x1][y1] = temp.second; mode[x1][y1] = 4; q.push(make_pair(x1, y1)); } x1 -= 2; if (x1 >= 0 and x1 < n and y1 >= 0 and y1 < n and visit[x1][y1] == 0) { visit[x1][y1] = 1; least[x1][y1] = least[temp.first][temp.second]+1; x[x1][y1] = temp.first; y[x1][y1] = temp.second; mode[x1][y1] = 5; q.push(make_pair(x1, y1)); } x1--; y1 -= 2; if (x1 >= 0 and x1 < n and y1 >= 0 and y1 < n and visit[x1][y1] == 0) { visit[x1][y1] = 1; least[x1][y1] = least[temp.first][temp.second]+1; x[x1][y1] = temp.first; y[x1][y1] = temp.second; mode[x1][y1] = 6; q.push(make_pair(x1, y1)); } } if (visit[j_end][i_end] == 0) { cout<<"Impossible\n"; } else { cout< ans; int x1 = j_end, y1 = i_end; while (x1 != -1) { ans.push_back(mode[x1][y1]); int t1 = x[x1][y1], t2 = y[x1][y1]; x1 = t1; y1 = t2; } for (int i = ans.size()-2; i >= 0; i--) { if (ans[i] == 1) cout<<"UL "; else if (ans[i] == 2) cout<<"UR "; else if (ans[i] == 3) cout<<"R "; else if (ans[i] == 4) cout<<"LR "; else if (ans[i] == 5) cout<<"LL "; else cout<<"L "; } cout<<"\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; }