import sys class Node(): value = None direction = None children = [] parent = None visited = False depth = 0 def __init__(self, value=None, direction=None): self.value = value self.direction = direction def isLeaf(self): return len(self.children) == 0 def isRoot(self): return (not self.parent) def asChildOf(self, parentNode): self.parent = parentNode self.depth = parentNode.depth + 1 parentNode.children.append(self) def getUL(self): return (self.value[0] - 2, self.value[1] - 1) def getUR(self): return (self.value[0] - 2, self.value[1] + 1) def getL(self): return (self.value[0], self.value[1] - 2) def getR(self): return (self.value[0], self.value[1] + 2) def getLL(self): return (self.value[0] + 2, self.value[1] - 1) def getLR(self): return (self.value[0] + 2, self.value[1] + 1) def legalCoor(self, coor, n): r = coor[0] c = coor[1] return (r >= 0 and r < n) and (c >=0 and c < n) def isReached(self, cur, des): return cur == des def getLegalChild(self, nodes, n): order = ['UL', 'UR', 'R', 'LR', 'LL', 'L'] res = dict() if self.legalCoor(self.getUL(), n): res['UL'] = self.getUL() if self.legalCoor(self.getUR(), n): res['UR'] = self.getUR() if self.legalCoor(self.getR(), n): res['R'] = self.getR() if self.legalCoor(self.getLR(), n): res['LR'] = self.getLR() if self.legalCoor(self.getLL(), n): res['LL'] = self.getLL() if self.legalCoor(self.getL(), n): res['L'] = self.getL() final = [] for key in order: if key in res.keys() and not nodes[res[key]].visited: e = nodes[res[key]] e.direction = key e.depth = self.depth + 1 e.parent = self.value e.visited = True final.append(e) return final # ul, ur, r, lr, ll, l def bfs(n, r_start, c_start, r_end, c_end, nodes): queue = [] root = nodes[(r_start, c_start)] queue.append(root) root.visited = True reached = False while not (reached == True or queue == []): nextL = [] for e in queue: node = nodes[e.value] node.visited = True nextL += node.getLegalChild(nodes, n) queue = nextL for e in queue: if e.isReached(e.value, (r_end, c_end)): reached = True break return nodes def buildNodes(n): nodes = dict() for i in range(n): for j in range(n): nodes[(i, j)] = Node(value=(i, j)) return nodes def printShortestPath(n, r_start, c_start, r_end, c_end): nodes = buildNodes(n) nodes = bfs(n, r_start, c_start, r_end, c_end, nodes) if nodes[(r_end, c_end)].visited == False: print("Impossible") else: path = [] end = nodes[(r_end, c_end)] print(end.depth) while end.parent: path.append(end.direction) end = nodes[end.parent] path.reverse() print(*path) if __name__ == "__main__": n = int(input().strip()) i_start, j_start, i_end, j_end = input().strip().split(' ') i_start, j_start, i_end, j_end = [int(i_start), int(j_start), int(i_end), int(j_end)] printShortestPath(n, i_start, j_start, i_end, j_end)