solutions: ["from collections import deque\nsurround = [(-2, -1, 'UL'), (-2, 1, 'UR'), (0, 2, 'R'), (2, 1, 'LR'), (2, -1, 'LL'), (0, -2, 'L')]\n\ndef printShortestPath(n, i_start, j_start, i_end, j_end):\n\tdist = [[-1 for _ in range(n)] for _ in range(n)]\n\tpath = [[[] for _ in range(n)] for _ in range(n)]\n\tq = deque([(i_start, j_start)])\n\tdist[i_start][j_start] = 0\n\twhile len(q) > 0:\n\t\t(i, j) = q.popleft()\n\t\tif i == i_end and j == j_end:\n\t\t\tprint(dist[i][j])\n\t\t\tprint(*path[i][j])\n\t\t\treturn\n\t\tfor (dx, dy, name) in surround:\n\t\t\tif 0 <= i + dx < n and 0 <= j + dy < n and (dist[i + dx][j + dy] == -1):\n\t\t\t\tq.append((i + dx, j + dy))\n\t\t\t\tdist[i + dx][j + dy] = dist[i][j] + 1\n\t\t\t\tpath[i + dx][j + dy] = path[i][j] + [name]\n\tprint('Impossible')\nn = int(input().strip())\n(i_start, j_start, i_end, j_end) = input().strip().split(' ')\n(i_start, j_start, i_end, j_end) = [int(i_start), int(j_start), int(i_end), int(j_end)]\nprintShortestPath(n, i_start, j_start, i_end, j_end)\n", "import sys\n\ndef printShortestPath(n, i_start, j_start, i_end, j_end):\n\tfromdict = {}\n\ttovisit = [(i_start, j_start)]\n\twhile len(tovisit) > 0:\n\t\t(i, j) = tovisit.pop(0)\n\t\tif (i, j) == (i_end, j_end):\n\t\t\tbreak\n\t\tif i > 1 and j > 0 and ((i - 2, j - 1) not in fromdict):\n\t\t\ttovisit.append((i - 2, j - 1))\n\t\t\tfromdict[i - 2, j - 1] = ('UL', i, j)\n\t\tif i > 1 and j < n - 1 and ((i - 2, j + 1) not in fromdict):\n\t\t\ttovisit.append((i - 2, j + 1))\n\t\t\tfromdict[i - 2, j + 1] = ('UR', i, j)\n\t\tif j < n - 2 and (i, j + 2) not in fromdict:\n\t\t\ttovisit.append((i, j + 2))\n\t\t\tfromdict[i, j + 2] = ('R', i, j)\n\t\tif i < n - 2 and j < n - 1 and ((i + 2, j + 1) not in fromdict):\n\t\t\ttovisit.append((i + 2, j + 1))\n\t\t\tfromdict[i + 2, j + 1] = ('LR', i, j)\n\t\tif i < n - 2 and j > 0 and ((i + 2, j - 1) not in fromdict):\n\t\t\ttovisit.append((i + 2, j - 1))\n\t\t\tfromdict[i + 2, j - 1] = ('LL', i, j)\n\t\tif j > 1 and (i, j - 2) not in fromdict:\n\t\t\ttovisit.append((i, j - 2))\n\t\t\tfromdict[i, j - 2] = ('L', i, j)\n\tif (i_end, j_end) not in fromdict:\n\t\tprint('Impossible')\n\telse:\n\t\tans = []\n\t\t(i, j) = (i_end, j_end)\n\t\twhile (i, j) != (i_start, j_start):\n\t\t\t(dr, i_n, j_n) = fromdict[i, j]\n\t\t\tans.append(dr)\n\t\t\t(i, j) = (i_n, j_n)\n\t\tans = ans[::-1]\n\t\tprint(len(ans))\n\t\tprint(' '.join(ans))\nn = int(input().strip())\n(i_start, j_start, i_end, j_end) = input().strip().split(' ')\n(i_start, j_start, i_end, j_end) = [int(i_start), int(j_start), int(i_end), int(j_end)]\nprintShortestPath(n, i_start, j_start, i_end, j_end)\n", "import sys\n\ndef printShortestPath(n, i_start, j_start, i_end, j_end):\n\tlevel = [(i_start, j_start)]\n\tmove = {}\n\tparent = {(i_start, j_start): None}\n\toptions = [('UL', (-2, -1)), ('UR', (-2, 1)), ('R', (0, 2)), ('LR', (2, 1)), ('LL', (2, -1)), ('L', (0, -2))]\n\tn_level = 0\n\twhile level:\n\t\tnew_level = []\n\t\tfor (i, j) in level:\n\t\t\tif i == i_end and j == j_end:\n\t\t\t\tprint(n_level)\n\t\t\t\tmoves = []\n\t\t\t\tcurr = (i_end, j_end)\n\t\t\t\twhile curr in move:\n\t\t\t\t\tmoves.append(move[curr])\n\t\t\t\t\tcurr = parent[curr]\n\t\t\t\tprint(' '.join(moves[::-1]))\n\t\t\t\treturn None\n\t\t\telse:\n\t\t\t\tfor (key, value) in options:\n\t\t\t\t\t(di, dj) = value\n\t\t\t\t\t(new_i, new_j) = (i + di, j + dj)\n\t\t\t\t\tif 0 <= new_i < n and 0 <= new_j < n and ((new_i, new_j) not in parent):\n\t\t\t\t\t\tnew_level.append((new_i, new_j))\n\t\t\t\t\t\tparent[new_i, new_j] = (i, j)\n\t\t\t\t\t\tmove[new_i, new_j] = key\n\t\tlevel = new_level\n\t\tn_level += 1\n\tprint('Impossible')\nn = int(input().strip())\n(i_start, j_start, i_end, j_end) = input().strip().split(' ')\n(i_start, j_start, i_end, j_end) = [int(i_start), int(j_start), int(i_end), int(j_end)]\nprintShortestPath(n, i_start, j_start, i_end, j_end)\n", "import sys\n\ndef printShortestPath(n, i_start, j_start, i_end, j_end):\n\tpaths = [[''] * n for _ in range(n)]\n\tvisited = [[-1] * n for _ in range(n)]\n\tif i_start == i_end and j_start == j_end:\n\t\tprint('0')\n\t\tprint()\n\t\treturn\n\tvisited[i_start][j_start] = 0\n\tstack = [(i_start, j_start)]\n\twhile stack:\n\t\t(i, j) = stack.pop(0)\n\t\tcur_path = paths[i][j]\n\t\tdirections = [('UL', (-2, -1)), ('UR', (-2, 1)), ('R', (0, 2)), ('LR', (2, 1)), ('LL', (2, -1)), ('L', (0, -2))]\n\t\tfor (name, (dx, dy)) in directions:\n\t\t\tni = i + dx\n\t\t\tnj = j + dy\n\t\t\tif 0 <= ni < n and 0 <= nj < n and (visited[ni][nj] == -1):\n\t\t\t\tvisited[ni][nj] = visited[i][j] + 1\n\t\t\t\tpaths[ni][nj] = cur_path + ' ' + name\n\t\t\t\tif ni == i_end and nj == j_end:\n\t\t\t\t\tprint(visited[ni][nj])\n\t\t\t\t\tprint(paths[ni][nj].strip())\n\t\t\t\t\treturn\n\t\t\t\tstack.append((ni, nj))\n\tprint('Impossible')\n\treturn\nn = int(input().strip())\n(i_start, j_start, i_end, j_end) = input().strip().split(' ')\n(i_start, j_start, i_end, j_end) = [int(i_start), int(j_start), int(i_end), int(j_end)]\nprintShortestPath(n, i_start, j_start, i_end, j_end)\n", "from collections import deque\n\ndef parseInput(s):\n\treturn [int(x) for x in s.split()]\n\ndef printShortestPath(n, i_start, j_start, i_end, j_end):\n\tdirs = [(-2, -1, 'UL'), (-2, 1, 'UR'), (0, 2, 'R'), (2, 1, 'LR'), (2, -1, 'LL'), (0, -2, 'L')]\n\tgrid = [[0 for j in range(n)] for i in range(n)]\n\tgrid[i_start][j_start] = 1\n\tq = deque()\n\tq.append([(i_start, j_start)])\n\twhile q:\n\t\tcurrent = q.popleft()\n\t\t(posx, posy) = (current[-1][0], current[-1][1])\n\t\tfor (dx, dy, name) in dirs:\n\t\t\t(nx, ny) = (posx + dx, posy + dy)\n\t\t\tif 0 <= nx < n and 0 <= ny < n:\n\t\t\t\tif (nx, ny) == (i_end, j_end):\n\t\t\t\t\tprint(len(current))\n\t\t\t\t\tprint(' '.join((point[2] for point in current if len(point) == 3)) + ' ' + name)\n\t\t\t\t\treturn\n\t\t\t\telif grid[nx][ny]:\n\t\t\t\t\tpass\n\t\t\t\telse:\n\t\t\t\t\tgrid[nx][ny] = 1\n\t\t\t\t\tq.append(current + [(nx, ny, name)])\n\tprint('Impossible')\n\treturn\nn = int(input().strip())\n(i_start, j_start, i_end, j_end) = input().strip().split(' ')\n(i_start, j_start, i_end, j_end) = [int(i_start), int(j_start), int(i_end), int(j_end)]\nprintShortestPath(n, i_start, j_start, i_end, j_end)\n", "import sys\n\ndef printShortestPath(n, i_start, j_start, i_end, j_end):\n\tif abs(i_end - i_start) % 2 == 1 or abs(j_end - j_start) % 2 != abs(i_end - i_start) / 2 % 2:\n\t\tprint('Impossible')\n\t\treturn\n\tre = []\n\twhile i_start > i_end:\n\t\tif (i_start - i_end) / 2 > j_end - j_start:\n\t\t\tre.append('UL')\n\t\t\tj_start -= 1\n\t\telse:\n\t\t\tre.append('UR')\n\t\t\tj_start += 1\n\t\ti_start -= 2\n\twhile j_start < j_end and j_end - j_start > (i_end - i_start) / 2:\n\t\tre.append('R')\n\t\tj_start += 2\n\twhile i_end > i_start:\n\t\tif (i_end - i_start) / 2 > j_start - j_end:\n\t\t\tre.append('LR')\n\t\t\tj_start += 1\n\t\telse:\n\t\t\tre.append('LL')\n\t\t\tj_start -= 1\n\t\ti_start += 2\n\twhile j_start > j_end:\n\t\tre.append('L')\n\t\tj_start -= 2\n\tprint(len(re))\n\tprint(*re)\nn = int(input().strip())\n(i_start, j_start, i_end, j_end) = input().strip().split(' ')\n(i_start, j_start, i_end, j_end) = [int(i_start), int(j_start), int(i_end), int(j_end)]\nprintShortestPath(n, i_start, j_start, i_end, j_end)\n", "import sys\nmap = {0: 'UL', 1: 'UR', 2: 'R', 3: 'LR', 4: 'LL', 5: 'L'}\n\ndef printShortestPath(n, i_start, j_start, i_end, j_end):\n\tcurrent = {(i_start, j_start): tuple([])}\n\tvisited = set([(i_start, j_start)])\n\twhile current:\n\t\tnew = {}\n\t\tfor (i, j) in current:\n\t\t\tpath = current[i, j]\n\t\t\tif i > 1:\n\t\t\t\tif j > 0:\n\t\t\t\t\tpos = (i - 2, j - 1)\n\t\t\t\t\tif pos not in visited:\n\t\t\t\t\t\tif pos in new:\n\t\t\t\t\t\t\tif path + (0,) < new[pos]:\n\t\t\t\t\t\t\t\tnew[pos] = path + (0,)\n\t\t\t\t\t\telse:\n\t\t\t\t\t\t\tnew[pos] = path + (0,)\n\t\t\t\tif j < n - 1:\n\t\t\t\t\tpos = (i - 2, j + 1)\n\t\t\t\t\tif pos not in visited:\n\t\t\t\t\t\tif pos in new:\n\t\t\t\t\t\t\tif path + (1,) < new[pos]:\n\t\t\t\t\t\t\t\tnew[pos] = path + (1,)\n\t\t\t\t\t\telse:\n\t\t\t\t\t\t\tnew[pos] = path + (1,)\n\t\t\tif j > 1:\n\t\t\t\tpos = (i, j - 2)\n\t\t\t\tif pos not in visited:\n\t\t\t\t\tif pos in new:\n\t\t\t\t\t\tif path + (5,) < new[pos]:\n\t\t\t\t\t\t\tnew[pos] = path + (5,)\n\t\t\t\t\telse:\n\t\t\t\t\t\tnew[pos] = path + (5,)\n\t\t\tif j < n - 2:\n\t\t\t\tpos = (i, j + 2)\n\t\t\t\tif pos not in visited:\n\t\t\t\t\tif pos in new:\n\t\t\t\t\t\tif path + (2,) < new[pos]:\n\t\t\t\t\t\t\tnew[pos] = path + (2,)\n\t\t\t\t\telse:\n\t\t\t\t\t\tnew[pos] = path + (2,)\n\t\t\tif i < n - 2:\n\t\t\t\tif j > 0:\n\t\t\t\t\tpos = (i + 2, j - 1)\n\t\t\t\t\tif pos not in visited:\n\t\t\t\t\t\tif pos in new:\n\t\t\t\t\t\t\tif path + (4,) < new[pos]:\n\t\t\t\t\t\t\t\tnew[pos] = path + (4,)\n\t\t\t\t\t\telse:\n\t\t\t\t\t\t\tnew[pos] = path + (4,)\n\t\t\t\tif j < n - 1:\n\t\t\t\t\tpos = (i + 2, j + 1)\n\t\t\t\t\tif pos not in visited:\n\t\t\t\t\t\tif pos in new:\n\t\t\t\t\t\t\tif path + (3,) < new[pos]:\n\t\t\t\t\t\t\t\tnew[pos] = path + (3,)\n\t\t\t\t\t\telse:\n\t\t\t\t\t\t\tnew[pos] = path + (3,)\n\t\tif (i_end, j_end) in new:\n\t\t\tpath = new[i_end, j_end]\n\t\t\tprint(len(path))\n\t\t\tprint(' '.join([map[i] for i in path]))\n\t\t\treturn\n\t\tcurrent = new\n\t\tfor pos in new:\n\t\t\tvisited.add(pos)\n\tprint('Impossible')\nn = int(input().strip())\n(i_start, j_start, i_end, j_end) = input().strip().split(' ')\n(i_start, j_start, i_end, j_end) = [int(i_start), int(j_start), int(i_end), int(j_end)]\nprintShortestPath(n, i_start, j_start, i_end, j_end)\n", "import sys\nfrom collections import *\nMOVES_STR = ('UL', 'UR', 'R', 'LR', 'LL', 'L')\nMOVES = ((-2, -1), (-2, 1), (0, 2), (2, 1), (2, -1), (0, -2))\n\ndef solve(r0, c0, r1, c1, F, P, N):\n\tq = deque([(r0, c0)])\n\tF[r0][c0] = 0\n\twhile q:\n\t\t(r, c) = q.popleft()\n\t\tf = F[r][c]\n\t\tp = P[r][c]\n\t\tif r == r1 and c == c1:\n\t\t\treturn (f, p)\n\t\tfor (i, dd) in enumerate(MOVES):\n\t\t\t(nr, nc) = (r + dd[0], c + dd[1])\n\t\t\tif nr < 0 or nc < 0 or nr >= N or (nc >= N):\n\t\t\t\tcontinue\n\t\t\tif F[nr][nc] == None:\n\t\t\t\tF[nr][nc] = f + 1\n\t\t\t\tP[nr][nc] = p + ' ' + MOVES_STR[i]\n\t\t\t\tq.append((nr, nc))\n\treturn (0, [])\nN = int(input().strip())\nF = [[None] * N for _ in range(N)]\nP = [[''] * N for _ in range(N)]\n(r0, c0, r1, c1) = map(int, input().strip().split(' '))\nres = solve(r0, c0, r1, c1, F, P, N)\nif res[0] == 0:\n\tprint('Impossible')\nelse:\n\tprint(res[0])\n\tprint(res[1][1:])\n", "import sys\nfrom collections import deque\n\ndef printShortestPath(n, i_start, j_start, i_end, j_end):\n\tdp = [[(None, float('inf')) for i in range(n)] for _ in range(n)]\n\tcount = 0\n\tmovei = [-2, -2, 0, 2, 2, 0]\n\tmovej = [-1, 1, 2, 1, -1, -2]\n\tword = ['UL', 'UR', 'R', 'LR', 'LL', 'L']\n\tbfs = deque()\n\tbfs.append((i_start, j_start))\n\tdp[i_start][j_start] = ('', 0)\n\twhile len(bfs) > 0:\n\t\t(i, j) = bfs.popleft()\n\t\tchars = dp[i][j][0]\n\t\tfor index in range(len(word)):\n\t\t\t(newindexi, newindexj, count) = (i + movei[index], j + movej[index], dp[i][j][1] + 1)\n\t\t\tif newindexi >= 0 and newindexi < n and (newindexj >= 0) and (newindexj < n):\n\t\t\t\tif dp[newindexi][newindexj][1] > count:\n\t\t\t\t\tdp[newindexi][newindexj] = (chars + str(index), count)\n\t\t\t\t\tbfs.append((newindexi, newindexj))\n\t\t\t\telif dp[newindexi][newindexj][1] == count:\n\t\t\t\t\tif chars + str(index) < dp[newindexi][newindexj][0]:\n\t\t\t\t\t\tdp[newindexi][newindexj] = (chars + str(index), count)\n\t\t\t\t\t\tbfs.append((newindexi, newindexj))\n\tif dp[i_end][j_end][0] == None:\n\t\tprint('Impossible')\n\telse:\n\t\tprint(dp[i_end][j_end][1])\n\t\tfor i in dp[i_end][j_end][0]:\n\t\t\tprint(word[int(i)], end=' ')\nn = int(input().strip())\n(i_start, j_start, i_end, j_end) = input().strip().split(' ')\n(i_start, j_start, i_end, j_end) = [int(i_start), int(j_start), int(i_end), int(j_end)]\nprintShortestPath(n, i_start, j_start, i_end, j_end)\n", "moves_labels = ['UL', 'UR', 'R', 'LR', 'LL', 'L']\nmoves = [(-2, -1), (-2, 1), (0, 2), (2, 1), (2, -1), (0, -2)]\n\ndef move_to_next(pos, move):\n\tnext_pos = (pos[0] + move[0], pos[1] + move[1])\n\treturn next_pos\n\ndef is_valid_pos(pos, n):\n\tinside_x = 0 <= pos[1] <= n\n\tinside_y = 0 <= pos[0] <= n\n\treturn inside_x and inside_y\n\ndef is_destination(pos_a, pos_b):\n\treturn pos_a == pos_b\n\ndef printShortestPath(n, i_start, j_start, i_end, j_end):\n\tstart = (i_start, j_start)\n\tend = (i_end, j_end)\n\tto_visit_from = [(start, [])]\n\tvisited = set()\n\tfor node_path in to_visit_from:\n\t\tnode = node_path[0]\n\t\tpath = node_path[1]\n\t\tif node in visited:\n\t\t\tcontinue\n\t\tif is_destination(node, end):\n\t\t\tfinal_path = ' '.join(path)\n\t\t\tprint(len(path))\n\t\t\tprint(final_path)\n\t\t\treturn\n\t\tvisited.add(node)\n\t\tfor (i, m) in enumerate(moves):\n\t\t\tnext_position = move_to_next(node, m)\n\t\t\tif is_valid_pos(next_position, n):\n\t\t\t\tnext_path = path.copy()\n\t\t\t\tnext_path.append(moves_labels[i])\n\t\t\t\tnext_node_path = (next_position, next_path)\n\t\t\t\tto_visit_from.append(next_node_path)\n\tprint('Impossible')\nn = int(input().strip())\n(i_start, j_start, i_end, j_end) = input().strip().split(' ')\n(i_start, j_start, i_end, j_end) = [int(i_start), int(j_start), int(i_end), int(j_end)]\nprintShortestPath(n, i_start, j_start, i_end, j_end)\n", "import sys\nfrom collections import deque\n\ndef next_possible_positions(n, row, col):\n\tpossible_positions = []\n\tfor (move, r, c) in [('UL', row - 2, col - 1), ('UR', row - 2, col + 1), ('R', row, col + 2), ('LR', row + 2, col + 1), ('LL', row + 2, col - 1), ('L', row, col - 2)]:\n\t\tif r >= 0 and r < n and (c >= 0) and (c < n):\n\t\t\tpossible_positions.append((move, r, c))\n\treturn possible_positions\n\ndef backtrack_cell(r, c, move):\n\tif move == 'UL':\n\t\treturn (r + 2, c + 1)\n\tif move == 'UR':\n\t\treturn (r + 2, c - 1)\n\tif move == 'R':\n\t\treturn (r, c - 2)\n\tif move == 'LR':\n\t\treturn (r - 2, c - 1)\n\tif move == 'LL':\n\t\treturn (r - 2, c + 1)\n\tif move == 'L':\n\t\treturn (r, c + 2)\n\treturn None\n\ndef backtracked_path(matrix, r_start, c_start, r_end, c_end):\n\tmoves = deque()\n\t(r, c) = (r_end, c_end)\n\twhile not (r == r_start and c == c_start):\n\t\tmove = matrix[r][c]\n\t\tmoves.appendleft(move)\n\t\t(r, c) = backtrack_cell(r, c, move)\n\treturn moves\n\ndef printShortestPath(n, r_start, c_start, r_end, c_end):\n\tnext_to_visit = deque()\n\tnext_to_visit.append((r_start, c_start))\n\tmatrix = [[None for _ in range(n)] for _ in range(n)]\n\twhile len(next_to_visit) > 0:\n\t\t(c_r, c_c) = next_to_visit.popleft()\n\t\tfor (move, n_r, n_c) in next_possible_positions(n, c_r, c_c):\n\t\t\tif matrix[n_r][n_c] is not None:\n\t\t\t\tcontinue\n\t\t\tmatrix[n_r][n_c] = move\n\t\t\tif (n_r, n_c) == (r_end, c_end):\n\t\t\t\tmoves = backtracked_path(matrix, r_start, c_start, r_end, c_end)\n\t\t\t\tprint(len(moves))\n\t\t\t\tprint(' '.join(moves))\n\t\t\t\treturn\n\t\t\tnext_to_visit.append((n_r, n_c))\n\tprint('Impossible')\nn = int(input().strip())\n(i_start, j_start, i_end, j_end) = input().strip().split(' ')\n(i_start, j_start, i_end, j_end) = [int(i_start), int(j_start), int(i_end), int(j_end)]\nprintShortestPath(n, i_start, j_start, i_end, j_end)\n", "from collections import defaultdict as dd\nn = int(input())\na = n\n(s1, s2, e1, e2) = [int(i) for i in input().split()]\n(r1, r2) = (e1, e2)\ng = dd(list)\nfor i in range(n):\n\tfor j in range(n):\n\t\tif i - 2 >= 0 and j - 1 >= 0:\n\t\t\tg[i, j].append(((i - 2, j - 1), 'UL'))\n\t\tif i - 2 >= 0 and j + 1 < a:\n\t\t\tg[i, j].append(((i - 2, j + 1), 'UR'))\n\t\tif i < a and j + 2 < a:\n\t\t\tg[i, j].append(((i, j + 2), 'R'))\n\t\tif i + 2 < a and j + 1 < a:\n\t\t\tg[i, j].append(((i + 2, j + 1), 'LR'))\n\t\tif i + 2 < a and j - 1 >= 0:\n\t\t\tg[i, j].append(((i + 2, j - 1), 'LL'))\n\t\tif i < a and j - 2 >= 0:\n\t\t\tg[i, j].append(((i, j - 2), 'L'))\nd = []\nch = [[0 for i in range(a + 1)] for j in range(a + 1)]\ndis = [[[] for i in range(a + 1)] for j in range(a + 1)]\n\ndef bfs(i, j):\n\tch[s1][s2] = 1\n\td.append([s1, s2])\n\twhile d:\n\t\tk = d.pop(0)\n\t\tfor i in g[k[0], k[1]]:\n\t\t\tif ch[i[0][0]][i[0][1]] == 0:\n\t\t\t\tch[i[0][0]][i[0][1]] = 1\n\t\t\t\td.append([i[0][0], i[0][1]])\n\t\t\t\tdis[i[0][0]][i[0][1]] = [k[0], k[1]]\n\t\tif ch[e1][e2] == 1:\n\t\t\tbreak\n\ndef ret(i, j, k, l):\n\tif k + 2 == i and l + 1 == j:\n\t\treturn 'UL'\n\telif k + 2 == i and l - 1 == j:\n\t\treturn 'UR'\n\telif k == i and l - 2 == j:\n\t\treturn 'R'\n\telif k - 2 == i and l - 1 == j:\n\t\treturn 'LR'\n\telif k - 2 == i and l + 1 == j:\n\t\treturn 'LL'\n\telif k == i and l + 2 == j:\n\t\treturn 'L'\nbfs(s1, s2)\npath = []\nwhile len(dis[e1][e2]) != 0:\n\tpath.append(dis[e1][e2])\n\t(e1, e2) = dis[e1][e2]\nif len(path) == 0:\n\tprint('Impossible')\nelse:\n\tprint(len(path))\n\tk = []\n\tpath1 = path[::-1] + [[r1, r2]]\n\tfor i in range(len(path1) - 1):\n\t\tk.append(ret(path1[i][0], path1[i][1], path1[i + 1][0], path1[i + 1][1]))\n\tprint(*k)\n", "import sys\nfrom collections import deque\nn = int(input())\n(sy, sx, ey, ex) = map(int, input().split())\nQ = deque()\nQ.append(('', sx, sy, 0))\nmoves = [(-1, -2), (1, -2), (2, 0), (1, 2), (-1, 2), (-2, 0)]\nname = {(-1, -2): 'UL ', (1, -2): 'UR ', (2, 0): 'R ', (1, 2): 'LR ', (-1, 2): 'LL ', (-2, 0): 'L '}\nM = {}\nwhile Q:\n\t(way, x, y, d) = Q.popleft()\n\tif x == ex and y == ey:\n\t\tprint(d)\n\t\tprint(way.strip())\n\t\tsys.exit(0)\n\tif (x, y) in M:\n\t\tcontinue\n\tM[x, y] = d\n\tfor (dx, dy) in moves:\n\t\tif 0 <= x + dx < n and 0 <= y + dy < n:\n\t\t\tQ.append((way + name[dx, dy], x + dx, y + dy, d + 1))\nprint('Impossible')\n", "from collections import deque\nfrom collections import namedtuple\n\nclass Position(namedtuple('Position', 'i j move')):\n\n\tdef __eq__(self, other):\n\t\treturn self.i == other.i and self.j == other.j\n\n\tdef next(self, n):\n\t\treturn filter(lambda p: p.i >= 0 and p.i < n and (p.j >= 0) and (p.j < n), [Position(self.i - 2, self.j - 1, 'UL'), Position(self.i - 2, self.j + 1, 'UR'), Position(self.i, self.j + 2, 'R'), Position(self.i + 2, self.j + 1, 'LR'), Position(self.i + 2, self.j - 1, 'LL'), Position(self.i, self.j - 2, 'L')])\n\ndef printShortestPath(n, i_start, j_start, i_end, j_end):\n\tstart = Position(i_start, j_start, None)\n\tend = Position(i_end, j_end, None)\n\tprev = []\n\tvisited = []\n\tfor i in range(n):\n\t\tprev.append([])\n\t\tvisited.append([])\n\t\tfor j in range(n):\n\t\t\tprev[i].append(None)\n\t\t\tvisited[i].append(False)\n\tq = deque()\n\tq.append(Position(i_start, j_start, None))\n\twhile len(q) > 0:\n\t\tu = q.popleft()\n\t\tvisited[u.i][u.j] = True\n\t\tif u == end:\n\t\t\tpath = [u.move]\n\t\t\twhile prev[u.i][u.j] != None:\n\t\t\t\tif prev[u.i][u.j].move != None:\n\t\t\t\t\tpath.append(prev[u.i][u.j].move)\n\t\t\t\tu = prev[u.i][u.j]\n\t\t\tprint(len(path))\n\t\t\tprint(*path[::-1], sep=' ')\n\t\t\treturn\n\t\tfor v in u.next(n):\n\t\t\tif not visited[v.i][v.j]:\n\t\t\t\tvisited[v.i][v.j] = True\n\t\t\t\tprev[v.i][v.j] = u\n\t\t\t\tq.append(v)\n\tprint('Impossible')\nn = int(input().strip())\n(i_start, j_start, i_end, j_end) = map(int, input().strip().split(' '))\nprintShortestPath(n, i_start, j_start, i_end, j_end)\n", "import sys\n\ndef printShortestPath(n, i_start, j_start, i_end, j_end):\n\tj = j_start\n\tiDiff = i_end - i_start\n\tjDiff = j_end - j_start\n\tnumSteps = 0\n\tstring = ''\n\tif iDiff % 2 == 1 or (iDiff // 2 + jDiff) % 2 == 1:\n\t\tprint('Impossible')\n\telse:\n\t\twhile iDiff != 0 or jDiff != 0:\n\t\t\tif iDiff > 0:\n\t\t\t\tif j == n - 1 or jDiff <= -iDiff // 2:\n\t\t\t\t\tstring += 'LL '\n\t\t\t\t\tnumSteps += 1\n\t\t\t\t\tj -= 1\n\t\t\t\t\tiDiff -= 2\n\t\t\t\t\tjDiff += 1\n\t\t\t\telif jDiff <= iDiff // 2:\n\t\t\t\t\tstring += 'LR '\n\t\t\t\t\tnumSteps += 1\n\t\t\t\t\tj += 1\n\t\t\t\t\tiDiff -= 2\n\t\t\t\t\tjDiff -= 1\n\t\t\t\telse:\n\t\t\t\t\tstring += 'R '\n\t\t\t\t\tnumSteps += 1\n\t\t\t\t\tj += 2\n\t\t\t\t\tjDiff -= 2\n\t\t\telif iDiff < 0:\n\t\t\t\tif j == 0 or jDiff >= -iDiff // 2:\n\t\t\t\t\tstring += 'UR '\n\t\t\t\t\tnumSteps += 1\n\t\t\t\t\tj += 1\n\t\t\t\t\tiDiff += 2\n\t\t\t\t\tjDiff -= 1\n\t\t\t\telse:\n\t\t\t\t\tstring += 'UL '\n\t\t\t\t\tnumSteps += 1\n\t\t\t\t\tj -= 1\n\t\t\t\t\tiDiff += 2\n\t\t\t\t\tjDiff += 1\n\t\t\telif jDiff > 0:\n\t\t\t\tstring += 'R '\n\t\t\t\tnumSteps += 1\n\t\t\t\tj += 2\n\t\t\t\tjDiff -= 2\n\t\t\telse:\n\t\t\t\tstring += 'L '\n\t\t\t\tnumSteps += 1\n\t\t\t\tj -= 2\n\t\t\t\tjDiff += 2\n\t\tprint(numSteps)\n\t\tprint(string.rstrip())\nn = int(input().strip())\n(i_start, j_start, i_end, j_end) = input().strip().split(' ')\n(i_start, j_start, i_end, j_end) = [int(i_start), int(j_start), int(i_end), int(j_end)]\nprintShortestPath(n, i_start, j_start, i_end, j_end)\n", "from collections import deque\nimport sys\nm = ['UL', 'UR', 'R', 'LR', 'LL', 'L']\ndi = [-2, -2, +0, +2, +2, +0]\ndj = [-1, +1, +2, +1, -1, -2]\ndp = list(zip(di, dj, m))\n\ndef printShortestPath(n, ibeg, jbeg, iend, jend):\n\tD = [n * [None] for _ in range(n)]\n\tP = [n * [None] for _ in range(n)]\n\tD[ibeg][jbeg] = 0\n\tQ = deque([(ibeg, jbeg)])\n\twhile Q:\n\t\t(i0, j0) = Q.popleft()\n\t\td = D[i0][j0] + 1\n\t\tfor (di, dj, m) in dp:\n\t\t\t(i, j) = (i0 + di, j0 + dj)\n\t\t\tif 0 <= i < n and 0 <= j < n:\n\t\t\t\tif P[i][j] is None:\n\t\t\t\t\tQ.append((i, j))\n\t\t\t\tif D[i][j] is None or d < D[i][j]:\n\t\t\t\t\t(D[i][j], P[i][j]) = (d, (i0, j0, m))\n\t(i, j, M) = (iend, jend, [])\n\td = D[i][j]\n\tif d is None:\n\t\tprint('Impossible')\n\telse:\n\t\tprint(d)\n\t\twhile P[i][j]:\n\t\t\t(i, j, m) = P[i][j]\n\t\t\tM.append(m)\n\t\tprint(*M[::-1])\n\treturn\nn = int(input().strip())\n(i_start, j_start, i_end, j_end) = input().strip().split(' ')\n(i_start, j_start, i_end, j_end) = [int(i_start), int(j_start), int(i_end), int(j_end)]\nprintShortestPath(n, i_start, j_start, i_end, j_end)\n", "import sys\n\ndef printShortestPath(n, i_start, j_start, i_end, j_end):\n\tINF = 1e+18\n\tMOVES = [[-2, -1, 'UL'], [-2, +1, 'UR'], [0, +2, 'R'], [+2, +1, 'LR'], [+2, -1, 'LL'], [0, -2, 'L']]\n\td = [[INF] * n for x in range(n)]\n\td[i_end][j_end] = 0\n\ts = [[i_end, j_end]]\n\tk = 0\n\twhile k < len(s):\n\t\t(i, j) = s[k]\n\t\tk += 1\n\t\tfor (di, dj, c) in MOVES:\n\t\t\tif 0 <= i + di < n and 0 <= j + dj < n and (d[i + di][j + dj] == INF):\n\t\t\t\td[i + di][j + dj] = d[i][j] + 1\n\t\t\t\ts += [[i + di, j + dj]]\n\tif d[i_start][j_start] == INF:\n\t\tprint('Impossible')\n\t\treturn\n\tprint(d[i_start][j_start])\n\twhile i_start != i_end or j_start != j_end:\n\t\tfor (di, dj, c) in MOVES:\n\t\t\tif 0 <= i_start + di < n and 0 <= j_start + dj < n and (d[i_start + di][j_start + dj] == d[i_start][j_start] - 1):\n\t\t\t\tprint(c, end=' ')\n\t\t\t\ti_start += di\n\t\t\t\tj_start += dj\n\t\t\t\tbreak\nn = int(input().strip())\n(i_start, j_start, i_end, j_end) = input().strip().split(' ')\n(i_start, j_start, i_end, j_end) = [int(i_start), int(j_start), int(i_end), int(j_end)]\nprintShortestPath(n, i_start, j_start, i_end, j_end)\n", "from queue import Queue\n\ndef shortedPath(size, rootx, rooty, endx, endy):\n\tdis = [[[] for i in range(size)] for j in range(size)]\n\tdis[rootx][rooty].append('')\n\tq = Queue()\n\tq.put([rootx, rooty])\n\twhile not q.empty():\n\t\t(curx, cury) = q.get()\n\t\tfor i in range(len(move)):\n\t\t\tx = curx + move[i][1]\n\t\t\ty = cury + move[i][0]\n\t\t\tif x < 0 or x >= size:\n\t\t\t\tcontinue\n\t\t\tif y < 0 or y >= size:\n\t\t\t\tcontinue\n\t\t\tif len(dis[x][y]) != 0:\n\t\t\t\tcontinue\n\t\t\tdis[x][y] = dis[curx][cury] + [move[i][2]]\n\t\t\tif x == endx and y == endy:\n\t\t\t\treturn dis[x][y]\n\t\t\tq.put([x, y])\n\treturn dis[endx][endy]\n\ndef main():\n\tsize = int(input())\n\t(rootx, rooty, endx, endy) = [int(i) for i in input().split(' ')]\n\tres = shortedPath(size, rootx, rooty, endx, endy)\n\tif len(res) == 0:\n\t\tprint('Impossible')\n\t\treturn\n\tres.remove('')\n\tprint(len(res))\n\tprint(' '.join(res))\nmove = [[-1, -2, 'UL'], [1, -2, 'UR'], [2, 0, 'R'], [1, 2, 'LR'], [-1, 2, 'LL'], [-2, 0, 'L']]\nmain()\n", "import sys\nfrom collections import namedtuple\nPosition = namedtuple('Position', ('i', 'j'))\n\ndef printShortestPath(n, i_start, j_start, i_end, j_end):\n\tif i_start % 2 != i_end % 2:\n\t\tprint('Impossible')\n\t\treturn\n\tMove = namedtuple('Move', ('name', 'delta_i', 'delta_j'))\n\ts = Position(i_start, j_start)\n\tt = Position(i_end, j_end)\n\tmoves = [Move('UL', -2, -1), Move('UR', -2, 1), Move('R', 0, 2), Move('LR', 2, 1), Move('LL', 2, -1), Move('L', 0, -2)]\n\tfinal_moves = BFS(n, moves, s, t)\n\tif final_moves is False:\n\t\tprint('Impossible')\n\telse:\n\t\tprint(len(final_moves))\n\t\tprint(*final_moves)\n\ndef BFS(n, moves, s, t):\n\tif s == t:\n\t\treturn []\n\tparent = {s: None}\n\tmove_dict = {}\n\tend = False\n\tfrontier = [s]\n\twhile frontier and (not end):\n\t\tnext_frontier = []\n\t\tfor pos in frontier:\n\t\t\tfor m in moves:\n\t\t\t\tnew_pos = Position(pos.i + m.delta_i, pos.j + m.delta_j)\n\t\t\t\tif new_pos.i < 0 or new_pos.i >= n or new_pos.j < 0 or (new_pos.j >= n):\n\t\t\t\t\tcontinue\n\t\t\t\tif new_pos.i + 1 == t.i or new_pos.i - 1 == t.i:\n\t\t\t\t\treturn False\n\t\t\t\tif new_pos not in parent:\n\t\t\t\t\tparent[new_pos] = pos\n\t\t\t\t\tmove_dict[new_pos] = m.name\n\t\t\t\t\tnext_frontier.append(new_pos)\n\t\t\t\t\tif new_pos == t:\n\t\t\t\t\t\tend = True\n\t\t\t\t\t\tbreak\n\t\t\tif end:\n\t\t\t\tbreak\n\t\tfrontier = next_frontier\n\tif t not in parent:\n\t\treturn False\n\tfinal_moves = []\n\tcurrent = t\n\twhile current in move_dict:\n\t\tfinal_moves.append(move_dict[current])\n\t\tcurrent = parent[current]\n\tfinal_moves.reverse()\n\treturn final_moves\nn = int(input().strip())\n(i_start, j_start, i_end, j_end) = input().strip().split(' ')\n(i_start, j_start, i_end, j_end) = [int(i_start), int(j_start), int(i_end), int(j_end)]\nprintShortestPath(n, i_start, j_start, i_end, j_end)\n", "from collections import deque\n\ndef printShortestPath(n, i_start, j_start, i_end, j_end):\n\ttodo = deque([(i_start, j_start, [])])\n\tvisited = [list([False] * n) for _ in range(n)]\n\twhile todo:\n\t\t(i, j, path) = todo.popleft()\n\t\tif i == i_end and j == j_end:\n\t\t\tprint(len(path))\n\t\t\tprint(*path)\n\t\t\treturn\n\t\tfor (di, dj, dir) in [(-2, -1, 'UL'), (-2, 1, 'UR'), (0, 2, 'R'), (2, 1, 'LR'), (2, -1, 'LL'), (0, -2, 'L')]:\n\t\t\t(i2, j2) = (i + di, j + dj)\n\t\t\tif 0 <= i2 < n and 0 <= j2 < n and (not visited[i2][j2]):\n\t\t\t\ttodo.append((i2, j2, path + [dir]))\n\t\t\t\tvisited[i2][j2] = True\n\tprint('Impossible')\nn = int(input().strip())\n(i_start, j_start, i_end, j_end) = input().strip().split(' ')\n(i_start, j_start, i_end, j_end) = [int(i_start), int(j_start), int(i_end), int(j_end)]\nprintShortestPath(n, i_start, j_start, i_end, j_end)\n", "INF = float('inf')\nmoves = [('UL', -2, -1), ('UR', -2, 1), ('R', 0, 2), ('LR', 2, 1), ('LL', 2, -1), ('L', 0, -2)]\nn = int(input())\n(i0, j0, i1, j1) = map(int, input().split())\n\ndef adj(i, j):\n\treturn ((desc, i + di, j + dj) for (desc, di, dj) in moves if 0 <= i + di < n and 0 <= j + dj < n)\n\ndef bfs(i0, j0):\n\td = [[INF for _ in range(n)] for _ in range(n)]\n\td[i0][j0] = 0\n\t(q, qi) = ([(i0, j0)], 0)\n\twhile qi < len(q):\n\t\t(i, j) = q[qi]\n\t\tfor (_, ii, jj) in adj(i, j):\n\t\t\tif d[ii][jj] == INF:\n\t\t\t\td[ii][jj] = d[i][j] + 1\n\t\t\t\tq.append((ii, jj))\n\t\tqi += 1\n\treturn d\n\ndef path(i, j, i1, j1):\n\tfor _ in range(best):\n\t\t(desc, i, j) = next(((desc, ii, jj) for (desc, ii, jj) in adj(i, j) if d0[ii][jj] == d0[i][j] + 1 and d1[ii][jj] == d1[i][j] - 1))\n\t\tyield desc\n(d0, d1) = (bfs(i0, j0), bfs(i1, j1))\nbest = d0[i1][j1]\nif best == INF:\n\tprint('Impossible')\nelse:\n\tprint(best)\n\tprint(' '.join(path(i0, j0, i1, j1)))\n", "def printShortestPath(n, i_start, j_start, i_end, j_end):\n\tx_moves = [-1, 1, 2, 1, -1, -2]\n\ty_moves = [-2, -2, 0, 2, 2, 0]\n\tactions = ['UL', 'UR', 'R', 'LR', 'LL', 'L']\n\ttarget = (j_end, i_end)\n\tdone = False\n\tvisited = {(j_start, i_start): (j_start, i_start, -1)}\n\tfrontier = [(j_start, i_start)]\n\tsteps = 0\n\twhile len(frontier) != 0:\n\t\tsteps += 1\n\t\tnew_frontier = []\n\t\tfor i in frontier:\n\t\t\tfor j in range(6):\n\t\t\t\tx = i[0] + x_moves[j]\n\t\t\t\ty = i[1] + y_moves[j]\n\t\t\t\tif x < 0 or x > n - 1 or y < 0 or (y > n - 1):\n\t\t\t\t\tcontinue\n\t\t\t\tif (x, y) in visited:\n\t\t\t\t\tcontinue\n\t\t\t\tvisited[x, y] = (i[0], i[1], j)\n\t\t\t\tif (x, y) == target:\n\t\t\t\t\tdone = True\n\t\t\t\t\tbreak\n\t\t\t\tnew_frontier.append((x, y))\n\t\t\tif done:\n\t\t\t\tnew_frontier = []\n\t\t\t\tbreak\n\t\tfrontier = new_frontier\n\tif done:\n\t\tprint(steps)\n\t\tpos = (j_end, i_end, -1)\n\t\tr = []\n\t\twhile not (pos[0] == j_start and pos[1] == i_start):\n\t\t\tpos = visited[pos[0], pos[1]]\n\t\t\tr += [actions[pos[2]]]\n\t\tprint(' '.join(r[::-1]))\n\telse:\n\t\tprint('Impossible')\nn = int(input().strip())\n(i_start, j_start, i_end, j_end) = input().strip().split(' ')\n(i_start, j_start, i_end, j_end) = [int(i_start), int(j_start), int(i_end), int(j_end)]\nprintShortestPath(n, i_start, j_start, i_end, j_end)\n", "import sys\n\ndef mapper(s):\n\tm = {'UL': (0, 'UL'), 'UR': (1, 'UR'), 'R': (2, 'R'), 'LR': (3, 'LR'), 'LL': (4, 'LL'), 'L': (5, 'L')}\n\treturn m[s]\n\ndef printShortestPath(n, i_start, j_start, i_end, j_end):\n\ty = j_end - j_start\n\tx = i_end - i_start\n\tif abs(y) % 2 != 0:\n\t\tprint('Impossible')\n\t\treturn\n\tst = []\n\tcount = 0\n\twhile y != 0:\n\t\tif y <= 0:\n\t\t\tj_start -= 2\n\t\t\tif x <= 0:\n\t\t\t\ti_start -= 1\n\t\t\t\tst.append('UL')\n\t\t\telse:\n\t\t\t\ti_start += 1\n\t\t\t\tst.append('UR')\n\t\telse:\n\t\t\tj_start += 2\n\t\t\tif x < 0:\n\t\t\t\ti_start -= 1\n\t\t\t\tst.append('LL')\n\t\t\telse:\n\t\t\t\ti_start += 1\n\t\t\t\tst.append('LR')\n\t\tif i_start < 0 or i_start == n:\n\t\t\tprint('Impossible')\n\t\t\treturn\n\t\ty = j_end - j_start\n\t\tx = i_end - i_start\n\t\tcount += 1\n\tif abs(x) % 2 != 0:\n\t\tprint('Impossible')\n\t\treturn\n\tfor i in range(abs(x) // 2):\n\t\tif x < 0:\n\t\t\tst.append('L')\n\t\telse:\n\t\t\tst.append('R')\n\t\tcount += 1\n\tprint(count)\n\tst = list(map(mapper, st))\n\tst.sort()\n\tst = list(map(lambda x: x[1], st))\n\tprint(*st)\nn = int(input().strip())\n(i_start, j_start, i_end, j_end) = input().strip().split(' ')\n(i_start, j_start, i_end, j_end) = [int(i_start), int(j_start), int(i_end), int(j_end)]\nprintShortestPath(n, j_start, i_start, j_end, i_end)\n", "import sys\nimport math\nfrom collections import namedtuple\nsys.setrecursionlimit(10000)\nP = namedtuple('Pos', 'r c')\nmoves = [P(-2, -1), P(-2, 1), P(0, 2), P(2, 1), P(2, -1), P(0, -2)]\nnames = {P(-2, -1): 'UL', P(-2, 1): 'UR', P(0, 2): 'R', P(2, 1): 'LR', P(2, -1): 'LL', P(0, -2): 'L'}\n\ndef shortest(start, end, N, mem):\n\tif start == end:\n\t\treturn 0\n\tif mem[start.r][start.c] is not None:\n\t\treturn mem[start.r][start.c][0]\n\tmn = math.inf\n\tmem[start.r][start.c] = (math.inf, None)\n\tbst = None\n\tfor move in moves:\n\t\tn = P(start.r + move.r, start.c + move.c)\n\t\td1 = abs(n.c - end.c) - abs(start.c - end.c)\n\t\td2 = abs(n.r - end.r) - abs(start.r - end.r)\n\t\tif n.r >= 0 and n.r < N and (n.c >= 0) and (n.c < N) and (d1 <= 1) and (d2 <= 1):\n\t\t\tans = 1 + shortest(n, end, N, mem)\n\t\t\tif ans < mn:\n\t\t\t\tmn = ans\n\t\t\t\tbst = move\n\tmem[start.r][start.c] = (mn, bst)\n\treturn mn\n\ndef printShortestPath(n, i_start, j_start, i_end, j_end):\n\tstart = P(i_start, j_start)\n\tend = P(i_end, j_end)\n\tmem = [[None for i in range(n)] for u in range(n)]\n\ts = shortest(start, end, n, mem=mem)\n\tif s == math.inf:\n\t\tprint('Impossible')\n\t\treturn\n\tprint(s)\n\tm = []\n\tp = start\n\twhile p != end:\n\t\t(_, b) = mem[p.r][p.c]\n\t\tassert b in names\n\t\tm.append(names[b])\n\t\tp = P(p.r + b.r, p.c + b.c)\n\tprint(' '.join(m))\nn = int(input().strip())\n(i_start, j_start, i_end, j_end) = input().strip().split(' ')\n(i_start, j_start, i_end, j_end) = [int(i_start), int(j_start), int(i_end), int(j_end)]\nprintShortestPath(n, i_start, j_start, i_end, j_end)\n", "import sys\n\ndef printShortestPath(n, i_start, j_start, i_end, j_end):\n\tmoves = 0\n\t(UL, UR, R, LR, LL, L) = (0, 0, 0, 0, 0, 0)\n\tv = i_start - i_end\n\th = j_start - j_end\n\n\tdef move():\n\t\tnonlocal h, v, moves, UL, UR, R, LR, LL, L\n\t\twhile h >= 0 and v > 0:\n\t\t\tUL += 1\n\t\t\tv -= 2\n\t\t\th -= 1\n\t\t\tmoves += 1\n\t\twhile h < 0 and v > 0:\n\t\t\tUR += 1\n\t\t\tv -= 2\n\t\t\th += 1\n\t\t\tmoves += 1\n\t\twhile h < 0 and v == 0:\n\t\t\tR += 1\n\t\t\th += 2\n\t\t\tmoves += 1\n\t\twhile h <= 0 and v < 0:\n\t\t\tLR += 1\n\t\t\tv += 2\n\t\t\th += 1\n\t\t\tmoves += 1\n\t\twhile h > 0 and v < 0:\n\t\t\tLL += 1\n\t\t\tv += 2\n\t\t\th -= 1\n\t\t\tmoves += 1\n\t\twhile h > 0 and v == 0:\n\t\t\tL += 1\n\t\t\th -= 2\n\t\t\tmoves += 1\n\tif abs(v) % 2 == 1:\n\t\tprint('Impossible')\n\telif h % 2 != v / 2 % 2:\n\t\tprint('Impossible')\n\telse:\n\t\twhile (h, v) != (0, 0):\n\t\t\tmove()\n\t\tprint(moves)\n\t\tprint('UL ' * UL + 'UR ' * UR + 'R ' * R + 'LR ' * LR + 'LL ' * LL + 'L ' * L)\nn = int(input().strip())\n(i_start, j_start, i_end, j_end) = input().strip().split(' ')\n(i_start, j_start, i_end, j_end) = [int(i_start), int(j_start), int(i_end), int(j_end)]\nprintShortestPath(n, i_start, j_start, i_end, j_end)\n", "import sys\n\ndef printShortestPath(n, starty, startx, i_end, j_end):\n\tvisited = [[False for x in range(n)] for y in range(n)]\n\tparent = [[[-1, -1] for x in range(n)] for y in range(n)]\n\tqueue = []\n\tqueue.append([starty, startx])\n\tvisited[starty][startx] = True\n\twhile queue:\n\t\tif queue[0] == [i_end, j_end]:\n\t\t\tbreak\n\t\ts = queue.pop(0)\n\t\tif s[1] >= 1 and s[0] >= 2 and (not visited[s[0] - 2][s[1] - 1]):\n\t\t\tqueue.append([s[0] - 2, s[1] - 1])\n\t\t\tvisited[s[0] - 2][s[1] - 1] = True\n\t\t\tparent[s[0] - 2][s[1] - 1] = s\n\t\tif s[1] <= n - 2 and s[0] >= 2 and (not visited[s[0] - 2][s[1] + 1]):\n\t\t\tqueue.append([s[0] - 2, s[1] + 1])\n\t\t\tvisited[s[0] - 2][s[1] + 1] = True\n\t\t\tparent[s[0] - 2][s[1] + 1] = s\n\t\tif s[1] <= n - 3 and (not visited[s[0]][s[1] + 2]):\n\t\t\tqueue.append([s[0], s[1] + 2])\n\t\t\tvisited[s[0]][s[1] + 2] = True\n\t\t\tparent[s[0]][s[1] + 2] = s\n\t\tif s[1] <= n - 2 and s[0] <= n - 3 and (not visited[s[0] + 2][s[1] + 1]):\n\t\t\tqueue.append([s[0] + 2, s[1] + 1])\n\t\t\tvisited[s[0] + 2][s[1] + 1] = True\n\t\t\tparent[s[0] + 2][s[1] + 1] = s\n\t\tif s[1] >= 1 and s[0] <= n - 3 and (not visited[s[0] + 2][s[1] - 1]):\n\t\t\tqueue.append([s[0] + 2, s[1] - 1])\n\t\t\tvisited[s[0] + 2][s[1] - 1] = True\n\t\t\tparent[s[0] + 2][s[1] - 1] = s\n\t\tif s[1] >= 2 and (not visited[s[0]][s[1] - 2]):\n\t\t\tqueue.append([s[0], s[1] - 2])\n\t\t\tvisited[s[0]][s[1] - 2] = True\n\t\t\tparent[s[0]][s[1] - 2] = s\n\tif not visited[i_end][j_end]:\n\t\tprint('Impossible')\n\t\treturn\n\tpath = [[i_end, j_end]]\n\ttmp = path[0]\n\twhile tmp != [starty, startx]:\n\t\ttmp = parent[tmp[0]][tmp[1]]\n\t\tpath.append(tmp)\n\tpath = path[::-1]\n\tprint(len(path) - 1)\n\tfor i in range(len(path) - 1):\n\t\tif path[i][1] > path[i + 1][1]:\n\t\t\tif path[i][0] < path[i + 1][0]:\n\t\t\t\tprint('LL', end=' ')\n\t\t\telif path[i][0] > path[i + 1][0]:\n\t\t\t\tprint('UL', end=' ')\n\t\t\telse:\n\t\t\t\tprint('L', end=' ')\n\t\telif path[i][0] < path[i + 1][0]:\n\t\t\tprint('LR', end=' ')\n\t\telif path[i][0] > path[i + 1][0]:\n\t\t\tprint('UR', end=' ')\n\t\telse:\n\t\t\tprint('R', end=' ')\n\tprint()\nn = int(input().strip())\n(i_start, j_start, i_end, j_end) = input().strip().split(' ')\n(i_start, j_start, i_end, j_end) = [int(i_start), int(j_start), int(i_end), int(j_end)]\nprintShortestPath(n, i_start, j_start, i_end, j_end)\n", "import sys\nfrom queue import Queue\n\ndef print_path(i_start, j_start, i_end, j_end, parent):\n\tpath = []\n\t(i, j) = (i_end, j_end)\n\twhile (i, j) != (i_start, j_start):\n\t\t(i, j, m) = parent[i, j]\n\t\tpath.append(m)\n\tprint(' '.join((m for m in path[::-1])))\n\ndef printShortestPath(n, i_start, j_start, i_end, j_end):\n\trow = [-2, -2, 0, 2, 2, 0]\n\tcol = [-1, 1, 2, 1, -1, -2]\n\tmove_names = ['UL', 'UR', 'R', 'LR', 'LL', 'L']\n\tparent = {}\n\tq = Queue()\n\tmarked = {(i_start, j_start)}\n\tq.put((i_start, j_start, 0))\n\twhile not q.empty():\n\t\t(i_root, j_root, d) = q.get()\n\t\tif (i_root, j_root) == (i_end, j_end):\n\t\t\tprint(d)\n\t\t\tprint_path(i_start, j_start, i_end, j_end, parent)\n\t\t\treturn\n\t\tfor k in range(6):\n\t\t\t(i, j) = (i_root + row[k], j_root + col[k])\n\t\t\tif 0 <= i < n and 0 <= j < n and ((i, j) not in marked):\n\t\t\t\tmarked.add((i, j))\n\t\t\t\tparent[i, j] = (i_root, j_root, move_names[k])\n\t\t\t\tq.put((i, j, d + 1))\n\tprint('Impossible')\nn = int(input().strip())\n(i_start, j_start, i_end, j_end) = input().strip().split(' ')\n(i_start, j_start, i_end, j_end) = [int(i_start), int(j_start), int(i_end), int(j_end)]\nprintShortestPath(n, i_start, j_start, i_end, j_end)\n", "import sys\nmoves = ['UL', 'UR', 'R', 'LR', 'LL', 'L']\ncoords = [(-2, -1), (-2, 1), (0, 2), (2, 1), (2, -1), (0, -2)]\n\ndef printShortestPath(n, i_start, j_start, i_end, j_end):\n\tif i_end - i_start & 1:\n\t\tprint('Impossible')\n\telse:\n\t\tpath = []\n\t\tdist = abs(i_start - i_end) // 2\n\t\ti = i_start\n\t\tj = j_start\n\t\tfor d in range(dist):\n\t\t\tif i < i_end:\n\t\t\t\tif j <= j_end:\n\t\t\t\t\tpath.append('LR')\n\t\t\t\t\ti += 2\n\t\t\t\t\tj += 1\n\t\t\t\telse:\n\t\t\t\t\tpath.append('LL')\n\t\t\t\t\ti += 2\n\t\t\t\t\tj -= 1\n\t\t\telif i > i_end:\n\t\t\t\tif j >= j_end:\n\t\t\t\t\tpath.append('UL')\n\t\t\t\t\ti -= 2\n\t\t\t\t\tj -= 1\n\t\t\t\telse:\n\t\t\t\t\tpath.append('UR')\n\t\t\t\t\ti -= 2\n\t\t\t\t\tj += 1\n\t\tif j != j_end:\n\t\t\tdist = abs(j - j_end)\n\t\t\tif dist & 1:\n\t\t\t\tprint('Impossible')\n\t\t\t\treturn\n\t\t\tfor d in range(dist):\n\t\t\t\tif j < j_end:\n\t\t\t\t\tpath.append('R')\n\t\t\t\t\tj += 2\n\t\t\t\telif j > j_end:\n\t\t\t\t\tpath.append('L')\n\t\t\t\t\tj -= 2\n\t\tprint(len(path))\n\t\tprint(' '.join(sorted(path, key=moves.index)))\nn = int(input().strip())\n(i_start, j_start, i_end, j_end) = input().strip().split(' ')\n(i_start, j_start, i_end, j_end) = [int(i_start), int(j_start), int(i_end), int(j_end)]\nprintShortestPath(n, i_start, j_start, i_end, j_end)\n", "import sys, math\n\ndef coord_to_inx(n, c):\n\treturn c[0] * n + c[1]\n\ndef inx_to_coord(n, i):\n\treturn (int(math.floor(i / n)), i % n)\n\ndef move_desc(from_, to_):\n\trow = from_[0] - to_[0]\n\tcol = from_[1] - to_[1]\n\tif row == 2:\n\t\tif col == 1:\n\t\t\treturn 'UL'\n\t\tif col == -1:\n\t\t\treturn 'UR'\n\tif row == 0:\n\t\tif col == 2:\n\t\t\treturn 'L'\n\t\tif col == -2:\n\t\t\treturn 'R'\n\tif row == -2:\n\t\tif col == 1:\n\t\t\treturn 'LL'\n\t\tif col == -1:\n\t\t\treturn 'LR'\n\traise 'invalid coords: ' + str(from_) + ' ' + str(to_)\n\ndef adj(n, v, quarter):\n\t(row, col) = v\n\tif row - 2 >= 0:\n\t\tif col - 1 >= 0:\n\t\t\tyield (row - 2, col - 1)\n\t\tif col + 1 < n:\n\t\t\tyield (row - 2, col + 1)\n\tif col + 2 < n:\n\t\tyield (row, col + 2)\n\tif row + 2 < n:\n\t\tif col + 1 < n:\n\t\t\tyield (row + 2, col + 1)\n\t\tif col - 1 >= 0:\n\t\t\tyield (row + 2, col - 1)\n\tif col - 2 >= 0:\n\t\tyield (row, col - 2)\n\ndef get_quarter(s, t):\n\t(s_row, s_col) = s\n\t(t_row, t_col) = t\n\tif t_row <= s_row:\n\t\tif t_col >= s_col:\n\t\t\treturn 1\n\t\telse:\n\t\t\treturn 2\n\telif t_col >= s_col:\n\t\treturn 3\n\telse:\n\t\treturn 4\n\ndef printShortestPath(n, i_start, j_start, i_end, j_end):\n\tif i_start % 2 != i_end % 2:\n\t\tprint('Impossible')\n\t\texit()\n\tis_t_same_row_kind = abs(i_start - i_end) // 2 % 2 == 0\n\tif is_t_same_row_kind and j_start % 2 != j_end % 2:\n\t\tprint('Impossible')\n\t\texit()\n\tif not is_t_same_row_kind and j_start % 2 == j_end % 2:\n\t\tprint('Impossible')\n\t\texit()\n\ts = (i_start, j_start)\n\tt = (i_end, j_end)\n\tmarked = set()\n\tq = []\n\tpathto = [-1] * (n * n)\n\tq.append(s)\n\tfound = False\n\tquarter = get_quarter(s, t)\n\twhile len(q) > 0:\n\t\tv = q.pop()\n\t\tv_inx = coord_to_inx(n, v)\n\t\tfor w in adj(n, v, quarter):\n\t\t\tif w not in marked:\n\t\t\t\tmarked.add(w)\n\t\t\t\tq.insert(0, w)\n\t\t\t\tpathto[coord_to_inx(n, w)] = v_inx\n\t\t\t\tif w == t:\n\t\t\t\t\tfound = True\n\t\t\t\t\tbreak\n\t\tif found:\n\t\t\tbreak\n\tif not found:\n\t\traise 'error'\n\tpath = []\n\tv = t\n\twhile True:\n\t\tw = inx_to_coord(n, pathto[coord_to_inx(n, v)])\n\t\tpath += [move_desc(w, v)]\n\t\tv = w\n\t\tif v == s:\n\t\t\tbreak\n\tprint(len(path))\n\tprint(' '.join(reversed(path)))\nn = int(input().strip())\n(i_start, j_start, i_end, j_end) = input().strip().split(' ')\n(i_start, j_start, i_end, j_end) = [int(i_start), int(j_start), int(i_end), int(j_end)]\nprintShortestPath(n, i_start, j_start, i_end, j_end)\n", "from collections import deque, defaultdict\n\ndef calc_pos(move, x_pos, y_pos):\n\tif move == 'UL':\n\t\treturn (x_pos - 2, y_pos - 1)\n\tif move == 'UR':\n\t\treturn (x_pos - 2, y_pos + 1)\n\tif move == 'R':\n\t\treturn (x_pos, y_pos + 2)\n\tif move == 'LR':\n\t\treturn (x_pos + 2, y_pos + 1)\n\tif move == 'LL':\n\t\treturn (x_pos + 2, y_pos - 1)\n\tif move == 'L':\n\t\treturn (x_pos, y_pos - 2)\n\ndef bfs(a, x_s, y_s, x_e, y_e, visit):\n\tprev = defaultdict()\n\tmoves = ['UL', 'UR', 'R', 'LR', 'LL', 'L']\n\tqueue = deque()\n\tqueue.append((x_s, y_s))\n\tvisit[x_s][y_s] = True\n\tdata[x_s][y_s] = 0\n\twhile queue:\n\t\t(x_s, y_s) = queue.popleft()\n\t\tif x_s == y_s and x_e == y_e:\n\t\t\treturn prev\n\t\tfor k in moves:\n\t\t\tif is_safe(k, x_s, y_s, visit):\n\t\t\t\t(a, b) = calc_pos(k, x_s, y_s)\n\t\t\t\tdata[a][b] = data[x_s][y_s] + 1\n\t\t\t\tprev[a, b] = [[x_s, y_s], k]\n\t\t\t\tqueue.append((a, b))\n\t\t\t\tvisit[a][b] = True\n\treturn prev\n\ndef is_safe(mov, i, j, visit):\n\t(i, j) = calc_pos(mov, i, j)\n\tif n > i >= 0 and n > j >= 0 and (visit[i][j] == False):\n\t\treturn True\n\treturn False\nn = int(input())\n(x_start, y_start, x_end, y_end) = map(int, input().split())\ndata = [[0 for i in range(n)] for j in range(n)]\nvisit = [[False for i in range(n)] for j in range(n)]\nprevv = bfs(data, x_start, y_start, x_end, y_end, visit)\nif data[x_end][y_end] != 0:\n\tprint(data[x_end][y_end])\n\tans = []\n\twhile not (x_start == x_end and y_start == y_end):\n\t\tans.append(prevv[x_end, y_end][1])\n\t\t(x_end, y_end) = prevv[x_end, y_end][0]\n\tfor i in range(1, len(ans) + 1):\n\t\tprint(ans[-i], end=' ')\nelse:\n\tprint('Impossible')\n", "from collections import defaultdict\nimport sys\nN = 0\n\ndef minuser():\n\treturn -1\nDP = defaultdict(minuser)\n\ndef findPath(x, y, cost, moves):\n\tif y % 2 != 0 or (x % 2 == 1 and y == 0):\n\t\tprint('Impossible')\n\telif x == 0 and y == 0:\n\t\tprint(cost)\n\t\tnstr = ''\n\t\tpriors = []\n\t\tmoves = sorted(moves)[::-1]\n\t\tfor elem in moves:\n\t\t\tnstr += elem + ' '\n\t\tprint(nstr)\n\telif x < 0 and y < -1:\n\t\tmoves.append('UL')\n\t\tfindPath(x + 1, y + 2, cost + 1, moves)\n\telif x > 0 and y < -1:\n\t\tmoves.append('UR')\n\t\tfindPath(x - 1, y + 2, cost + 1, moves)\n\telif x > 0 and y == 0:\n\t\tmoves.append('R')\n\t\tfindPath(x - 2, y, cost + 1, moves)\n\telif x > 0 and y > 1:\n\t\tmoves.append('LR')\n\t\tfindPath(x - 1, y - 2, cost + 1, moves)\n\telif x < 0 and y > 1:\n\t\tmoves.append('LL')\n\t\tfindPath(x + 1, y - 2, cost + 1, moves)\n\telif x < 0 and y == 0:\n\t\tmoves.append('L')\n\t\tfindPath(x + 2, y, cost + 1, moves)\n\telif y > 1:\n\t\tmoves.append('LR')\n\t\tfindPath(x - 1, y - 2, cost + 1, moves)\n\telif y < -1:\n\t\tmoves.append('UL')\n\t\tfindPath(x - 1, y + 2, cost + 1, moves)\n\ndef printShortestPath(n, i_start, j_start, i_end, j_end):\n\tx = i_end - i_start\n\ty = j_end - j_start\n\tfindPath(y, x, 0, [])\nn = int(input().strip())\n(i_start, j_start, i_end, j_end) = input().strip().split(' ')\n(i_start, j_start, i_end, j_end) = [int(i_start), int(j_start), int(i_end), int(j_end)]\nprintShortestPath(n, i_start, j_start, i_end, j_end)\n", "import collections\nn = int(input())\n(istart, jstart, iend, jend) = map(int, input().split())\ngrid = [[None] * n for i in range(n)]\nmoves = [(-2, -1, 'UL'), (-2, +1, 'UR'), (0, +2, 'R'), (+2, +1, 'LR'), (+2, -1, 'LL'), (0, -2, 'L')]\ngrid[istart][jstart] = (-1, -1, '')\nactive = collections.deque()\nactive.append((istart, jstart))\nwhile active:\n\t(i, j) = active.popleft()\n\tfor (di, dj, dir) in moves:\n\t\ti2 = i + di\n\t\tj2 = j + dj\n\t\tif i2 < 0 or i2 >= n or j2 < 0 or (j2 >= n) or grid[i2][j2]:\n\t\t\tcontinue\n\t\tgrid[i2][j2] = (i, j, dir)\n\t\tif i == iend and j == jend:\n\t\t\tactive.clear()\n\t\t\tbreak\n\t\tactive.append((i2, j2))\nif grid[iend][jend]:\n\ti = iend\n\tj = jend\n\tpath = []\n\twhile True:\n\t\t(i, j, dir) = grid[i][j]\n\t\tif dir == '':\n\t\t\tbreak\n\t\tpath.append(dir)\n\tpath.reverse()\n\tprint(len(path))\n\tprint(*path)\nelse:\n\tprint('Impossible')\n", "import sys\n\ndef distance(i_start, j_start, i_end, j_end):\n\tif min(i_start, j_start, i_end, j_end) < 0 or max(i_start, j_start, i_end, j_end) >= n:\n\t\treturn -1\n\tfieldsDown = abs(i_end - i_start)\n\tfieldsRight = abs(j_end - j_start)\n\tif fieldsDown + fieldsRight == 0:\n\t\treturn 0\n\tif fieldsDown % 2 == 1:\n\t\treturn -1\n\tstepsDown = fieldsDown // 2\n\tif (stepsDown + fieldsRight) % 2 == 1:\n\t\treturn -1\n\tsecondSummand = max([0, (fieldsRight - stepsDown) // 2])\n\treturn stepsDown + secondSummand\n\ndef solve(i_start, j_start, i_end, j_end):\n\tsteps = []\n\td = distance(i_start, j_start, i_end, j_end)\n\tif d == -1:\n\t\tprint('Impossible')\n\t\treturn\n\telse:\n\t\tprint(d)\n\tmoves = [['UL', -2, -1], ['UR', -2, 1], ['R', 0, 2], ['LR', 2, 1], ['LL', 2, -1], ['L', 0, -2]]\n\twhile d != 0:\n\t\tfor m in moves:\n\t\t\tnewD = distance(i_start + m[1], j_start + m[2], i_end, j_end)\n\t\t\tif newD != -1 and newD < d:\n\t\t\t\ti_start += m[1]\n\t\t\t\tj_start += m[2]\n\t\t\t\td = newD\n\t\t\t\tsteps.append(m[0])\n\t\t\t\tbreak\n\tprint(' '.join(steps))\n\ndef printShortestPath(n, i_start, j_start, i_end, j_end):\n\tsolve(i_start, j_start, i_end, j_end)\nn = int(input().strip())\n(i_start, j_start, i_end, j_end) = input().strip().split(' ')\n(i_start, j_start, i_end, j_end) = [int(i_start), int(j_start), int(i_end), int(j_end)]\nprintShortestPath(n, i_start, j_start, i_end, j_end)\n", "import sys\n\ndef printShortestPath(n, i_start, j_start, i_end, j_end):\n\tv_dist = abs(i_start - i_end)\n\th_dist = abs(j_start - j_end)\n\tif v_dist % 2 == 1:\n\t\tprint('Impossible')\n\t\treturn\n\tif h_dist % 2 != v_dist // 2 % 2:\n\t\tprint('Impossible')\n\t\treturn\n\tresult = []\n\t(i, j) = (i_start, j_start)\n\twhile i != i_end or j != j_end:\n\t\tif i > i_end and j < j_end:\n\t\t\tresult.append('UR')\n\t\t\ti -= 2\n\t\t\tj += 1\n\t\telif i < i_end and j < j_end:\n\t\t\tresult.append('LR')\n\t\t\ti += 2\n\t\t\tj += 1\n\t\telif i > i_end and j > j_end:\n\t\t\tresult.append('UL')\n\t\t\ti -= 2\n\t\t\tj -= 1\n\t\telif i < i_end and j > j_end:\n\t\t\tresult.append('LL')\n\t\t\ti += 2\n\t\t\tj -= 1\n\t\telif i == i_end and j < j_end:\n\t\t\tresult.append('R')\n\t\t\tj += 2\n\t\telif i == i_end and j > j_end:\n\t\t\tresult.append('L')\n\t\t\tj -= 2\n\t\telif i > i_end and j == j_end:\n\t\t\tif j > 0:\n\t\t\t\tresult.append('UL')\n\t\t\t\ti -= 2\n\t\t\t\tj -= 1\n\t\t\telse:\n\t\t\t\tresult.append('UR')\n\t\t\t\ti -= 2\n\t\t\t\tj += 1\n\t\telif i < i_end and j == j_end:\n\t\t\tif j < n - 1:\n\t\t\t\tresult.append('LR')\n\t\t\t\ti += 2\n\t\t\t\tj += 1\n\t\t\telse:\n\t\t\t\tresult.append('LL')\n\t\t\t\ti += 2\n\t\t\t\tj -= 1\n\tpriority = {'UL': 0, 'UR': 1, 'R': 2, 'LR': 3, 'LL': 4, 'L': 5}\n\tresult.sort(key=lambda x: priority[x])\n\tprint(len(result))\n\tprint(' '.join(result))\nn = int(input().strip())\n(i_start, j_start, i_end, j_end) = input().strip().split(' ')\n(i_start, j_start, i_end, j_end) = [int(i_start), int(j_start), int(i_end), int(j_end)]\nprintShortestPath(n, i_start, j_start, i_end, j_end)\n", "from collections import deque\n\ndef printShortestPath(n, i_s, j_s, i_e, j_e):\n\tdist = [[None] * n for _ in range(n)]\n\tpth = [[None] * n for _ in range(n)]\n\td = [(-2, -1, 'UL'), (-2, 1, 'UR'), (0, 2, 'R'), (2, 1, 'LR'), (2, -1, 'LL'), (0, -2, 'L'), (0, 2, 'R')]\n\tq = deque()\n\tq.append((i_s, j_s))\n\tdist[i_s][j_s] = 0\n\twhile q:\n\t\t(i, j) = q.popleft()\n\t\tfor (u, v, s) in ((i + di, j + dj, s) for (di, dj, s) in d):\n\t\t\tif all((0 <= x < n for x in (u, v))) and dist[u][v] is None:\n\t\t\t\tdist[u][v] = dist[i][j] + 1\n\t\t\t\tpth[u][v] = (i, j, s)\n\t\t\t\tif (u, v) == (i_e, j_e):\n\t\t\t\t\tprint(dist[u][v])\n\t\t\t\t\tp = (i, j, s)\n\t\t\t\t\tl = []\n\t\t\t\t\twhile p:\n\t\t\t\t\t\tl.append(p[2])\n\t\t\t\t\t\tp = pth[p[0]][p[1]]\n\t\t\t\t\tprint(*reversed(l))\n\t\t\t\t\treturn\n\t\t\t\tq.append((u, v))\n\tprint('Impossible')\nn = int(input().strip())\n(i_start, j_start, i_end, j_end) = input().strip().split(' ')\n(i_start, j_start, i_end, j_end) = [int(i_start), int(j_start), int(i_end), int(j_end)]\nprintShortestPath(n, i_start, j_start, i_end, j_end)\n", "import sys\n\nclass Node:\n\n\tdef __init__(self, present, parent):\n\t\tself.present = present\n\t\tself.parent = parent[:]\n\n\tdef UL(self):\n\t\tself.present = [self.present[0] - 1, self.present[1] - 2]\n\t\tself.parent.append('UL')\n\n\tdef UR(self):\n\t\tself.present = [self.present[0] + 1, self.present[1] - 2]\n\t\tself.parent.append('UR')\n\n\tdef R(self):\n\t\tself.present = [self.present[0] + 2, self.present[1]]\n\t\tself.parent.append('R')\n\n\tdef LR(self):\n\t\tself.present = [self.present[0] + 1, self.present[1] + 2]\n\t\tself.parent.append('LR')\n\n\tdef LL(self):\n\t\tself.present = [self.present[0] - 1, self.present[1] + 2]\n\t\tself.parent.append('LL')\n\n\tdef L(self):\n\t\tself.present = [self.present[0] - 2, self.present[1]]\n\t\tself.parent.append('L')\n\n\tdef check(self, end):\n\t\treturn self.present == end\n\n\tdef boundary(self, visited, n):\n\t\tif self.present[0] < 0 or self.present[1] < 0 or self.present[0] > n - 1 or (self.present[1] > n - 1):\n\t\t\treturn True\n\t\telif visited[self.present[1]][self.present[0]] == True:\n\t\t\treturn True\n\t\telse:\n\t\t\tvisited[self.present[1]][self.present[0]] = True\n\t\t\treturn False\n\ndef printShortestPath(n, i_start, j_start, i_end, j_end):\n\tend = [j_end, i_end]\n\tvisited = dict()\n\tpriority = {0: lambda x: x.UL(), 1: lambda x: x.UR(), 2: lambda x: x.R(), 3: lambda x: x.LR(), 4: lambda x: x.LL(), 5: lambda x: x.L()}\n\tfor i in range(n):\n\t\tvisited[i] = [False] * n\n\tqueue = list()\n\ts = Node([j_start, i_start], [])\n\tqueue.append(s)\n\tvisited[i_start][j_start] = True\n\twhile queue:\n\t\ts = queue.pop(0)\n\t\tfor i in range(6):\n\t\t\tx = Node(s.present, s.parent)\n\t\t\tpriority[i](x)\n\t\t\tif x.check(end):\n\t\t\t\treturn x.parent\n\t\t\telif x.boundary(visited, n):\n\t\t\t\tcontinue\n\t\t\tqueue.append(x)\n\treturn []\n\ndef printd(li):\n\tif len(li) == 0:\n\t\tprint('Impossible')\n\telse:\n\t\tprint(len(li))\n\t\tfor i in li:\n\t\t\tprint(i, end=' ')\n\t\tprint(' ')\nn = int(input().strip())\n(i_start, j_start, i_end, j_end) = input().strip().split(' ')\n(i_start, j_start, i_end, j_end) = [int(i_start), int(j_start), int(i_end), int(j_end)]\nprintd(printShortestPath(n, i_start, j_start, i_end, j_end))\n", "import sys\n\ndef printShortestPath(n, i_start, j_start, i_end, j_end):\n\tif i_start % 2 == 0:\n\t\tif i_end % 2 != 0:\n\t\t\tprint('Impossible')\n\t\t\treturn\n\telif i_end % 2 == 0:\n\t\tprint('Impossible')\n\t\treturn\n\tif j_start % 2 == 0:\n\t\tif abs(i_start - i_end) / 2 % 2 == 0:\n\t\t\tif j_end % 2 != 0:\n\t\t\t\tprint('Impossible')\n\t\t\t\treturn\n\t\telif j_end % 2 == 0:\n\t\t\tprint('Impossible')\n\t\t\treturn\n\telif abs(i_start - i_end) / 2 % 2 == 0:\n\t\tif j_end % 2 == 0:\n\t\t\tprint('Impossible')\n\t\t\treturn\n\telif j_end % 2 != 0:\n\t\tprint('Impossible')\n\t\treturn\n\ts = ''\n\tcount = 0\n\twhile 1:\n\t\tif i_start == i_end and j_start == j_end:\n\t\t\tbreak\n\t\telif i_start == i_end:\n\t\t\tif j_start < j_end:\n\t\t\t\ts += 'R '\n\t\t\t\tj_start += 2\n\t\t\t\tcount += 1\n\t\t\telse:\n\t\t\t\ts += 'L '\n\t\t\t\tj_start -= 2\n\t\t\t\tcount += 1\n\t\telif j_start == j_end:\n\t\t\tif i_start < i_end:\n\t\t\t\tx = (i_end - i_start) // 4\n\t\t\t\twhile x:\n\t\t\t\t\ts += 'LR '\n\t\t\t\t\ti_start += 2\n\t\t\t\t\tj_start += 1\n\t\t\t\t\tx -= 1\n\t\t\t\t\tcount += 1\n\t\t\telse:\n\t\t\t\tx = (i_start - i_end) // 4\n\t\t\t\twhile x:\n\t\t\t\t\ts += 'UL '\n\t\t\t\t\ti_start -= 2\n\t\t\t\t\tj_start -= 1\n\t\t\t\t\tx -= 1\n\t\t\t\t\tcount += 1\n\t\telif i_start < i_end and j_start < j_end:\n\t\t\tx = (i_end - i_start) // 2\n\t\t\ty = j_end - j_start\n\t\t\tif y > x:\n\t\t\t\ts += 'R '\n\t\t\t\tj_start += 2\n\t\t\t\tcount += 1\n\t\t\telse:\n\t\t\t\ts += 'LR '\n\t\t\t\ti_start += 2\n\t\t\t\tj_start += 1\n\t\t\t\tcount += 1\n\t\telif i_start > i_end and j_start > j_end:\n\t\t\ts += 'UL '\n\t\t\ti_start -= 2\n\t\t\tj_start -= 1\n\t\t\tcount += 1\n\t\telif i_start < i_end and j_start > j_end:\n\t\t\tjumps = (i_end - i_start) // 2\n\t\t\ttr = j_start - j_end\n\t\t\tjumps = (jumps - tr) // 2\n\t\t\tif jumps >= 1:\n\t\t\t\twhile jumps:\n\t\t\t\t\ts += 'LR '\n\t\t\t\t\ti_start += 2\n\t\t\t\t\tj_start += 1\n\t\t\t\t\tcount += 1\n\t\t\t\t\tjumps -= 1\n\t\t\telse:\n\t\t\t\ts += 'LL '\n\t\t\t\ti_start += 2\n\t\t\t\tj_start -= 1\n\t\t\t\tcount += 1\n\t\telse:\n\t\t\ts += 'UR '\n\t\t\ti_start -= 2\n\t\t\tj_start += 1\n\t\t\tcount += 1\n\tprint(count)\n\tprint(s)\nn = int(input().strip())\n(i_start, j_start, i_end, j_end) = input().strip().split(' ')\n(i_start, j_start, i_end, j_end) = [int(i_start), int(j_start), int(i_end), int(j_end)]\nprintShortestPath(n, i_start, j_start, i_end, j_end)\n", "import re\nimport sys\nFAILURE = 'Impossible'\nUPLEFT = 'UL '\nUPRIGHT = 'UR '\nDOWNLEFT = 'LL '\nDOWNRIGHT = 'LR '\nLEFT = 'L '\nRIGHT = 'R '\n\ndef sign(x):\n\treturn 1 if x >= 0 else -1\nlines = [line.strip() for line in sys.stdin.readlines()]\nn = int(lines[0])\npositions = [int(r) for r in re.split('[^\\\\d]', lines[1])]\nstart = positions[:2]\nend = positions[2:]\ndx = end[1] - start[1]\ndy = end[0] - start[0]\nabsdx = abs(dx)\nabsdy = abs(dy)\nif absdy % 2 == 1:\n\tprint(FAILURE)\n\tsys.exit(0)\nNy = absdy // 2\nif absdx % 2 == 0 and Ny % 2 == 1 or (absdx % 2 == 1 and Ny % 2 == 0):\n\tprint(FAILURE)\n\tsys.exit(0)\nif absdx >= Ny:\n\toppmoves = 0\nelse:\n\toppmoves = (Ny - absdx) // 2\nif not oppmoves:\n\tdxprime = dx - sign(dx) * Ny\n\tabsdxprime = abs(dxprime)\nelse:\n\tdxprime = 0\n\tabsdxprime = 0\nNx = absdxprime // 2\nresultstring = ''\nif dy < 0:\n\tif dx < 0:\n\t\tresultstring += UPLEFT * (Ny - oppmoves)\n\t\tresultstring += UPRIGHT * oppmoves\n\telse:\n\t\tresultstring += UPLEFT * oppmoves\n\t\tresultstring += UPRIGHT * (Ny - oppmoves)\nif dxprime > 0:\n\tresultstring += RIGHT * Nx\nif dy > 0:\n\tif dx < 0:\n\t\tresultstring += DOWNRIGHT * oppmoves\n\t\tresultstring += DOWNLEFT * (Ny - oppmoves)\n\telse:\n\t\tresultstring += DOWNRIGHT * (Ny - oppmoves)\n\t\tresultstring += DOWNLEFT * oppmoves\nif dxprime < 0:\n\tresultstring += LEFT * Nx\nprint(Ny + Nx)\nprint(resultstring.strip())\n", "import sys\n\ndef printShortestPath(n, i_start, j_start, i_end, j_end):\n\tvisited = [[0 for i in range(n)] for k in range(n)]\n\tprev = [[0 for i in range(n)] for k in range(n)]\n\tq = []\n\tq.append((i_start, j_start))\n\tmove_list = [(-2, -1), (-2, 1), (0, 2), (2, 1), (2, -1), (0, -2)]\n\tname_list = ['UL', 'UR', 'R', 'LR', 'LL', 'L']\n\tflag = True\n\tvisited[i_start][j_start] = 1\n\twhile q:\n\t\t(x, y) = q.pop(0)\n\t\tif (x, y) == (i_end, j_end):\n\t\t\tpath = []\n\t\t\tnode = (x, y)\n\t\t\twhile prev[x][y] != 0:\n\t\t\t\t(x, y, t) = prev[x][y]\n\t\t\t\tpath.append(t)\n\t\t\tpath.reverse()\n\t\t\tprint(len(path))\n\t\t\tprint(' '.join(path))\n\t\t\tflag = False\n\t\t\tbreak\n\t\tvisited[x][y] = 1\n\t\tfor (idx, (dx, dy)) in enumerate(move_list):\n\t\t\t(new_x, new_y) = (x + dx, y + dy)\n\t\t\tif 0 <= new_x < n and 0 <= new_y < n:\n\t\t\t\tif visited[new_x][new_y] == 1:\n\t\t\t\t\tcontinue\n\t\t\t\telse:\n\t\t\t\t\tq.append((new_x, new_y))\n\t\t\t\t\tprev[new_x][new_y] = (x, y, name_list[idx])\n\t\t\t\t\tvisited[new_x][new_y] = 1\n\tif flag:\n\t\tprint('Impossible')\nn = int(input().strip())\n(i_start, j_start, i_end, j_end) = input().strip().split(' ')\n(i_start, j_start, i_end, j_end) = [int(i_start), int(j_start), int(i_end), int(j_end)]\nprintShortestPath(n, i_start, j_start, i_end, j_end)\n", "import sys\n\ndef printStuff(c, s):\n\tprint(c)\n\tb = ''\n\ttemp = s.split(' ')\n\tfinal = []\n\tfor x in range(0, len(temp) - 1):\n\t\tif temp[x] == 'UL':\n\t\t\tfinal.append('UL')\n\tfor x in range(0, len(temp) - 1):\n\t\tif temp[x] == 'UR':\n\t\t\tfinal.append('UR')\n\tfor x in range(0, len(temp) - 1):\n\t\tif temp[x] == 'R':\n\t\t\tfinal.append('R')\n\tfor x in range(0, len(temp) - 1):\n\t\tif temp[x] == 'LR':\n\t\t\tfinal.append('LR')\n\tfor x in range(0, len(temp) - 1):\n\t\tif temp[x] == 'LL':\n\t\t\tfinal.append('LL')\n\tfor x in range(0, len(temp) - 1):\n\t\tif temp[x] == 'L':\n\t\t\tfinal.append('L')\n\tfor x in range(0, len(final)):\n\t\tb = b + final[x] + ' '\n\tprint(b)\n\ndef printShortestPath(n, i_start, j_start, i_end, j_end):\n\tt = ''\n\tcount = 0\n\ty = i_start\n\tsy = i_start\n\tx = j_start\n\tsx = j_start\n\ta = i_end\n\tb = j_end\n\tif sy > a:\n\t\twhile True:\n\t\t\tif sx >= b:\n\t\t\t\tsx -= 1\n\t\t\t\tsy -= 2\n\t\t\t\tcount += 1\n\t\t\t\tt = t + 'UL '\n\t\t\t\tif sx < b and sy < a:\n\t\t\t\t\tprint('Impossible')\n\t\t\t\t\treturn\n\t\t\telif sx < b:\n\t\t\t\tsx += 1\n\t\t\t\tsy -= 2\n\t\t\t\tcount += 1\n\t\t\t\tt = t + 'UR '\n\t\t\t\tif sx > b and sy > a:\n\t\t\t\t\tprint('Impossible')\n\t\t\t\t\treturn\n\t\t\tif sy == a and sx == b:\n\t\t\t\tprintStuff(count, t)\n\t\t\t\treturn\n\t\t\telif sy == a and sx != b:\n\t\t\t\tbreak\n\tif sy < a:\n\t\twhile True:\n\t\t\tif sx > b:\n\t\t\t\tsx -= 1\n\t\t\t\tsy += 2\n\t\t\t\tcount += 1\n\t\t\t\tt = t + 'LL '\n\t\t\t\tif sx < b and sy > a:\n\t\t\t\t\tprint('Impossible')\n\t\t\t\t\treturn\n\t\t\telif sx <= b:\n\t\t\t\tsx += 1\n\t\t\t\tsy += 2\n\t\t\t\tcount += 1\n\t\t\t\tt = t + 'LR '\n\t\t\t\tif sx > b and sy > a:\n\t\t\t\t\tprint('Impossible')\n\t\t\t\t\treturn\n\t\t\tif sy == a and sx == b:\n\t\t\t\tprintStuff(count, t)\n\t\t\t\treturn\n\t\t\telif sy == a and sx != b:\n\t\t\t\tbreak\n\tif sy == a:\n\t\tif sx < b:\n\t\t\twhile True:\n\t\t\t\tsx += 2\n\t\t\t\tcount += 1\n\t\t\t\tt = t + 'R '\n\t\t\t\tif sx == b:\n\t\t\t\t\tprintStuff(count, t)\n\t\t\t\t\treturn\n\t\t\t\telif sx > b:\n\t\t\t\t\tprint('Impossible')\n\t\t\t\t\treturn\n\t\telif sx > b:\n\t\t\twhile True:\n\t\t\t\tsx -= 2\n\t\t\t\tcount += 1\n\t\t\t\tt = t + 'L '\n\t\t\t\tif sx == b:\n\t\t\t\t\tprintStuff(count, t)\n\t\t\t\t\treturn\n\t\t\t\telif sx < b:\n\t\t\t\t\tprint('Impossible')\n\t\t\t\t\treturn\nn = int(input().strip())\n(i_start, j_start, i_end, j_end) = input().strip().split(' ')\n(i_start, j_start, i_end, j_end) = [int(i_start), int(j_start), int(i_end), int(j_end)]\nprintShortestPath(n, i_start, j_start, i_end, j_end)\n", "import sys\n\ndef printShortestPath(n, i_start, j_start, i_end, j_end):\n\tv = [[False for i in range(n)] for j in range(n)]\n\tv[i_start][j_start] = True\n\tp = [[(-1, -1) for i in range(n)] for j in range(n)]\n\tm = [['' for i in range(n)] for j in range(n)]\n\tq = [(i_start, j_start)]\n\twhile q:\n\t\tcurr = q.pop(0)\n\t\tif curr[0] == i_end and curr[1] == j_end:\n\t\t\tbreak\n\t\tif curr[0] - 2 >= 0 and curr[1] - 1 >= 0 and (v[curr[0] - 2][curr[1] - 1] == False):\n\t\t\tv[curr[0] - 2][curr[1] - 1] = True\n\t\t\tp[curr[0] - 2][curr[1] - 1] = curr\n\t\t\tm[curr[0] - 2][curr[1] - 1] = 'UL'\n\t\t\tq.append((curr[0] - 2, curr[1] - 1))\n\t\tif curr[0] - 2 >= 0 and curr[1] + 1 < n and (v[curr[0] - 2][curr[1] + 1] == False):\n\t\t\tv[curr[0] - 2][curr[1] + 1] = True\n\t\t\tp[curr[0] - 2][curr[1] + 1] = curr\n\t\t\tm[curr[0] - 2][curr[1] + 1] = 'UR'\n\t\t\tq.append((curr[0] - 2, curr[1] + 1))\n\t\tif curr[1] + 2 < n and v[curr[0]][curr[1] + 2] == False:\n\t\t\tv[curr[0]][curr[1] + 2] = True\n\t\t\tp[curr[0]][curr[1] + 2] = curr\n\t\t\tm[curr[0]][curr[1] + 2] = 'R'\n\t\t\tq.append((curr[0], curr[1] + 2))\n\t\tif curr[0] + 2 < n and curr[1] + 1 < n and (v[curr[0] + 2][curr[1] + 1] == False):\n\t\t\tv[curr[0] + 2][curr[1] + 1] = True\n\t\t\tp[curr[0] + 2][curr[1] + 1] = curr\n\t\t\tm[curr[0] + 2][curr[1] + 1] = 'LR'\n\t\t\tq.append((curr[0] + 2, curr[1] + 1))\n\t\tif curr[0] + 2 < n and curr[1] - 1 >= 0 and (v[curr[0] + 2][curr[1] - 1] == False):\n\t\t\tv[curr[0] + 2][curr[1] - 1] = True\n\t\t\tp[curr[0] + 2][curr[1] - 1] = curr\n\t\t\tm[curr[0] + 2][curr[1] - 1] = 'LL'\n\t\t\tq.append((curr[0] + 2, curr[1] - 1))\n\t\tif curr[1] - 2 >= 0 and v[curr[0]][curr[1] - 2] == False:\n\t\t\tv[curr[0]][curr[1] - 2] = True\n\t\t\tp[curr[0]][curr[1] - 2] = curr\n\t\t\tm[curr[0]][curr[1] - 2] = 'L'\n\t\t\tq.append((curr[0], curr[1] - 2))\n\tif v[i_end][j_end] == False or (i_start, j_start) == (i_end, j_end):\n\t\tprint('Impossible')\n\telse:\n\t\tlen_path = 0\n\t\tmoves = ''\n\t\tend = p[i_end][j_end]\n\t\ti = i_end\n\t\tj = j_end\n\t\twhile p[i][j] != (-1, -1):\n\t\t\tif len_path == 0:\n\t\t\t\tmid = ''\n\t\t\telse:\n\t\t\t\tmid = ' '\n\t\t\tmoves = m[i][j] + mid + moves\n\t\t\ttmp_i = p[i][j][0]\n\t\t\ttmp_j = p[i][j][1]\n\t\t\ti = tmp_i\n\t\t\tj = tmp_j\n\t\t\tlen_path += 1\n\t\tprint(len_path)\n\t\tprint(moves)\nn = int(input().strip())\n(i_start, j_start, i_end, j_end) = input().strip().split(' ')\n(i_start, j_start, i_end, j_end) = [int(i_start), int(j_start), int(i_end), int(j_end)]\nprintShortestPath(n, i_start, j_start, i_end, j_end)\n", "import sys\n\ndef validMove(n, i, j):\n\tif i < 0 or i >= n:\n\t\treturn False\n\tif j < 0 or j >= n:\n\t\treturn False\n\treturn True\nname = ['UL', 'UR', 'R', 'LR', 'LL', 'L']\nmoveY = [-1, 1, 2, 1, -1, -2]\nmoveX = [-2, -2, 0, 2, 2, 0]\n\ndef findNextLevel(inputArray, parent, level, cur_level, n, i_end, j_end):\n\toutputArray = []\n\tfound = False\n\tfor k in range(len(inputArray)):\n\t\tfor i in range(6):\n\t\t\tif validMove(n, inputArray[k][0] + moveX[i], inputArray[k][1] + moveY[i]):\n\t\t\t\tif inputArray[k][0] + moveX[i] == i_end and inputArray[k][1] + moveY[i] == j_end:\n\t\t\t\t\tparent[inputArray[k][0] + moveX[i]][inputArray[k][1] + moveY[i]] = inputArray[k]\n\t\t\t\t\tfound = True\n\t\t\t\t\tbreak\n\t\t\t\telif level[inputArray[k][0] + moveX[i]][inputArray[k][1] + moveY[i]] == -1:\n\t\t\t\t\tlevel[inputArray[k][0] + moveX[i]][inputArray[k][1] + moveY[i]] = cur_level + 1\n\t\t\t\t\tparent[inputArray[k][0] + moveX[i]][inputArray[k][1] + moveY[i]] = inputArray[k]\n\t\t\t\t\toutputArray.append([inputArray[k][0] + moveX[i], inputArray[k][1] + moveY[i]])\n\t\tif found:\n\t\t\tbreak\n\tif found:\n\t\treturn True\n\telif len(outputArray) > 0:\n\t\tfound = found or findNextLevel(outputArray, parent, level, cur_level + 1, n, i_end, j_end)\n\treturn found\n\ndef printShortestPath(n, i_start, j_start, i_end, j_end):\n\tparent = [[[-1, -1] for i in range(n)] for j in range(n)]\n\tlevel = [[-1 for i in range(n)] for j in range(n)]\n\tcur_level = 0\n\tlevel[i_start][j_start] = 0\n\tfound = findNextLevel([[i_start, j_start]], parent, level, cur_level, n, i_end, j_end)\n\tif found:\n\t\tstart = [i_end, j_end]\n\t\tresult = []\n\t\twhile start != [-1, -1]:\n\t\t\ttemp = parent[start[0]][start[1]]\n\t\t\tdelX = -temp[0] + start[0]\n\t\t\tdelY = -temp[1] + start[1]\n\t\t\tfor i in range(6):\n\t\t\t\tif [delX, delY] == [moveX[i], moveY[i]]:\n\t\t\t\t\tresult.append(name[i])\n\t\t\t\t\tbreak\n\t\t\tstart = temp\n\t\tprint(len(result))\n\t\tstrToWrite = ''\n\t\tfor i in range(len(result)):\n\t\t\tstrToWrite += result[len(result) - 1 - i] + ' '\n\t\tprint(strToWrite[:-1])\n\telse:\n\t\tprint('Impossible')\nn = int(input().strip())\n(i_start, j_start, i_end, j_end) = input().strip().split(' ')\n(i_start, j_start, i_end, j_end) = [int(i_start), int(j_start), int(i_end), int(j_end)]\nprintShortestPath(n, i_start, j_start, i_end, j_end)\n", "import sys\n\ndef printShortestPath(n, i_start, j_start, i_end, j_end):\n\tif i_start % 2 != i_end % 2:\n\t\tprint('Impossible')\n\telif i_start % 4 == i_end % 4 and j_start % 2 != j_end % 2:\n\t\tprint('Impossible')\n\telif i_start % 4 != i_end % 4 and j_start % 2 == j_end % 2:\n\t\tprint('Impossible')\n\telse:\n\t\tnumMoves = 0\n\t\tmoveStr = ''\n\t\twhile i_start != i_end or j_start != j_end:\n\t\t\tif i_start - i_end > max((j_end - j_start) * 2, 0) and j_start > 0:\n\t\t\t\tmoveStr += 'UL '\n\t\t\t\ti_start -= 2\n\t\t\t\tj_start -= 1\n\t\t\telif i_start > i_end and j_start >= j_end and (j_start > 0):\n\t\t\t\tmoveStr += 'UL '\n\t\t\t\ti_start -= 2\n\t\t\t\tj_start -= 1\n\t\t\telif (i_start > i_end and j_start <= j_end) and j_start < n - 1:\n\t\t\t\tmoveStr += 'UR '\n\t\t\t\ti_start -= 2\n\t\t\t\tj_start += 1\n\t\t\telif j_end > j_start and (j_end - j_start) * 2 > i_end - i_start and (j_start < n - 2):\n\t\t\t\tmoveStr += 'R '\n\t\t\t\tj_start += 2\n\t\t\telif i_end - i_start > max((j_start - j_end) * 2, 0) and j_start < n - 1:\n\t\t\t\tmoveStr += 'LR '\n\t\t\t\ti_start += 2\n\t\t\t\tj_start += 1\n\t\t\telif i_start < i_end and j_start <= j_end and (j_start < n - 1):\n\t\t\t\tmoveStr += 'LR '\n\t\t\t\ti_start += 2\n\t\t\t\tj_start += 1\n\t\t\telif (i_start < i_end and j_start >= j_end) and j_start > 0:\n\t\t\t\tmoveStr += 'LL '\n\t\t\t\ti_start += 2\n\t\t\t\tj_start -= 1\n\t\t\telif (i_start == i_end and j_start > j_end) and j_start > 1:\n\t\t\t\tmoveStr += 'L '\n\t\t\t\tj_start -= 2\n\t\t\tnumMoves += 1\n\t\tprint(numMoves)\n\t\tprint(moveStr.strip())\nn = int(input().strip())\n(i_start, j_start, i_end, j_end) = input().strip().split(' ')\n(i_start, j_start, i_end, j_end) = [int(i_start), int(j_start), int(i_end), int(j_end)]\nprintShortestPath(n, i_start, j_start, i_end, j_end)\n", "import sys\n\ndef update_table(board, path, cells, i_old, j_old, i_new, j_new, current_l, move):\n\tboard[i_new][j_new] = current_l\n\tcells.append((i_new, j_new))\n\tpath[i_new, j_new] = path[i_old, j_old].copy()\n\tpath[i_new, j_new].append(move)\n\ndef printShortestPath(n, i_start, j_start, i_end, j_end):\n\tmoves_order = ['UpperLeft', 'UpperRight', 'Right', 'LowerRight', 'LowerLeft', 'Left']\n\tboard = []\n\tfor _ in range(n):\n\t\tboard.append([-1] * n)\n\tboard[i_start][j_start] = 0\n\tpath = {(i_start, j_start): []}\n\tcurrent_l = 0\n\tcurrent_cells = [(i_start, j_start)]\n\tcan_move = 1\n\twhile can_move:\n\t\tcurrent_l += 1\n\t\tcan_move = 0\n\t\tnew_cells = []\n\t\tfor cell in current_cells:\n\t\t\tif cell[0] > 1:\n\t\t\t\tif cell[1] > 0 and board[cell[0] - 2][cell[1] - 1] < 0:\n\t\t\t\t\tupdate_table(board, path, new_cells, cell[0], cell[1], cell[0] - 2, cell[1] - 1, current_l, 'UL')\n\t\t\t\t\tcan_move = 1\n\t\t\t\tif cell[1] < n - 1 and board[cell[0] - 2][cell[1] + 1] < 0:\n\t\t\t\t\tupdate_table(board, path, new_cells, cell[0], cell[1], cell[0] - 2, cell[1] + 1, current_l, 'UR')\n\t\t\t\t\tcan_move = 1\n\t\t\tif cell[1] < n - 2 and board[cell[0]][cell[1] + 2] < 0:\n\t\t\t\tupdate_table(board, path, new_cells, cell[0], cell[1], cell[0], cell[1] + 2, current_l, 'R')\n\t\t\t\tcan_move = 1\n\t\t\tif cell[0] < n - 2:\n\t\t\t\tif cell[1] < n - 1 and board[cell[0] + 2][cell[1] + 1] < 0:\n\t\t\t\t\tupdate_table(board, path, new_cells, cell[0], cell[1], cell[0] + 2, cell[1] + 1, current_l, 'LR')\n\t\t\t\t\tcan_move = 1\n\t\t\t\tif cell[1] > 0 and board[cell[0] + 2][cell[1] - 1] < 0:\n\t\t\t\t\tupdate_table(board, path, new_cells, cell[0], cell[1], cell[0] + 2, cell[1] - 1, current_l, 'LL')\n\t\t\t\t\tcan_move = 1\n\t\t\tif cell[1] > 1 and board[cell[0]][cell[1] - 2] < 0:\n\t\t\t\tupdate_table(board, path, new_cells, cell[0], cell[1], cell[0], cell[1] - 2, current_l, 'L')\n\t\t\t\tcan_move = 1\n\t\tcurrent_cells = new_cells\n\tif board[i_end][j_end] == -1:\n\t\tprint('Impossible')\n\telse:\n\t\tprint(board[i_end][j_end])\n\t\tprint(' '.join(path[i_end, j_end]))\nn = int(input().strip())\n(i_start, j_start, i_end, j_end) = input().strip().split(' ')\n(i_start, j_start, i_end, j_end) = [int(i_start), int(j_start), int(i_end), int(j_end)]\nprintShortestPath(n, i_start, j_start, i_end, j_end)\n", "import sys\nfrom collections import OrderedDict\nfrom operator import add\nds = ['UL', 'UR', 'R', 'LR', 'LL', 'L']\ndirs = [('UL', (-1, -2)), ('UR', (1, -2)), ('R', (2, 0)), ('LR', (1, 2)), ('LL', (-1, 2)), ('L', (-2, 0))]\n\ndef dist(p1, p2):\n\treturn abs(p1[0] - p2[0]) + abs(p1[1] - p2[1])\n\ndef nextStep(pos, dest):\n\tbest = None\n\tcurrdist = dist(pos, dest)\n\tif currdist == 0:\n\t\treturn 'Done'\n\tmindist = None\n\tminpos = None\n\tfor i in dirs:\n\t\tnewpos = list(map(add, pos, i[1]))\n\t\tnewdist = dist(newpos, dest)\n\t\tprint('{}, {}, {:}, {}, {}, {}'.format(pos, dest, currdist, i, newpos, newdist), file=sys.stderr)\n\t\tif mindist is None or mindist > newdist:\n\t\t\tmindist = newdist\n\t\t\tminpos = newpos\n\t\t\tbest = i\n\tprint('best: {}, [{}] -> [{}], dist:{} -> {}'.format(best, pos, minpos, currdist, mindist), file=sys.stderr)\n\tif mindist > currdist:\n\t\tprint('Got further: Abort', file=sys.stderr)\n\t\tbest = None\n\tif mindist == currdist:\n\t\tprint('No closer: Abort', file=sys.stderr)\n\t\tbest = None\n\treturn best\n\ndef printShortestPath(n, i_start, j_start, i_end, j_end):\n\tpos = (j_start, i_start)\n\tdest = (j_end, i_end)\n\tsteps = []\n\twhile True:\n\t\tbestMove = nextStep(pos, dest)\n\t\tif bestMove is None:\n\t\t\tprint('Impossible')\n\t\t\treturn\n\t\telif bestMove == 'Done':\n\t\t\tbreak\n\t\telse:\n\t\t\tsteps.append(bestMove)\n\t\t\tpos = list(map(add, pos, bestMove[1]))\n\tprint(len(steps))\n\tsteps = sorted(steps, key=lambda x: ds.index(x[0]))\n\tprint(' '.join((s[0] for s in steps)))\nn = int(input().strip())\n(i_start, j_start, i_end, j_end) = input().strip().split(' ')\n(i_start, j_start, i_end, j_end) = [int(i_start), int(j_start), int(i_end), int(j_end)]\nprintShortestPath(n, i_start, j_start, i_end, j_end)\n", "import sys\n\ndef printShortestPath(n, i_start, j_start, i_end, j_end):\n\tshortestPaths = {(i_start, j_start): []}\n\tmoves = {'UL': (-2, -1), 'UR': (-2, 1), 'LL': (2, -1), 'LR': (2, 1), 'L': (0, -2), 'R': (0, 2)}\n\tmoveorder = ['UL', 'UR', 'R', 'LR', 'LL', 'L']\n\tnew = [(i_start, j_start)]\n\twhile len(new) > 0:\n\t\tcurr = new.pop(0)\n\t\tfor m in moveorder:\n\t\t\tnext_pos = (curr[0] + moves[m][0], curr[1] + moves[m][1])\n\t\t\tif next_pos not in shortestPaths and min(next_pos) >= 0 and (max(next_pos) < n):\n\t\t\t\tshortestPaths[next_pos] = shortestPaths[curr] + [m]\n\t\t\t\tnew.append(next_pos)\n\tif (i_end, j_end) in shortestPaths:\n\t\tprint(len(shortestPaths[i_end, j_end]))\n\t\tprint(' '.join(shortestPaths[i_end, j_end]))\n\telse:\n\t\tprint('Impossible')\nn = int(input().strip())\n(i_start, j_start, i_end, j_end) = input().strip().split(' ')\n(i_start, j_start, i_end, j_end) = [int(i_start), int(j_start), int(i_end), int(j_end)]\nprintShortestPath(n, i_start, j_start, i_end, j_end)\n", "class node:\n\n\tdef __init__(self):\n\t\tself.i = None\n\t\tself.j = None\n\t\tself.h = None\n\t\tself.parent = None\n\t\tself.move = None\n\nclass pathnode:\n\n\tdef __init__(self):\n\t\tself.a = []\n\t\tself.length = len(self.a)\n\nclass redknight_chess:\n\n\tdef __init__(self, n, s, e):\n\t\tself.start = s\n\t\tself.end = e\n\t\tself.start.h = self.heuristic(self.start)\n\t\tself.end.h = self.heuristic(self.end)\n\t\tself.n = n\n\t\tself.openx = []\n\t\tself.openx.append(s)\n\t\tself.paths = [None for i in range(100)]\n\t\tself.closex = []\n\n\tdef search(self):\n\t\tk = 0\n\t\twhile len(self.openx) > 0:\n\t\t\tif k == 5:\n\t\t\t\treturn\n\t\t\tx = self.openx[0]\n\t\t\tdel self.openx[0]\n\t\t\tself.closex.append(x)\n\t\t\tif x.i == self.end.i and x.j == self.end.j:\n\t\t\t\tself.printpath(x)\n\t\t\t\tk = k + 1\n\t\t\tadj = self.movegen(x)\n\t\t\tadjr = self.removeseen(adj)\n\t\t\tself.openx = self.openx + adjr\n\n\tdef movegen(self, e):\n\t\tm = e.i\n\t\tn = e.j\n\t\tmove = []\n\t\tp = m - 1\n\t\tq = n - 2\n\t\tnod = node()\n\t\tnod.i = p\n\t\tnod.j = q\n\t\tif p >= 0 and q >= 0 and (p < self.n) and (q < self.n):\n\t\t\tnod.h = self.heuristic(nod)\n\t\t\tnod.parent = e\n\t\t\tnod.move = 'UL'\n\t\t\tif nod.h < e.h:\n\t\t\t\tmove.append(nod)\n\t\tp = m + 1\n\t\tq = n - 2\n\t\tnod = node()\n\t\tnod.i = p\n\t\tnod.j = q\n\t\tif p >= 0 and q >= 0 and (p < self.n) and (q < self.n):\n\t\t\tnod.h = self.heuristic(nod)\n\t\t\tnod.parent = e\n\t\t\tnod.move = 'UR'\n\t\t\tif nod.h < e.h:\n\t\t\t\tmove.append(nod)\n\t\tp = m + 2\n\t\tq = n\n\t\tnod = node()\n\t\tnod.i = p\n\t\tnod.j = q\n\t\tif p >= 0 and q >= 0 and (p < self.n) and (q < self.n):\n\t\t\tnod.h = self.heuristic(nod)\n\t\t\tnod.parent = e\n\t\t\tnod.move = 'R'\n\t\t\tif nod.h < e.h:\n\t\t\t\tmove.append(nod)\n\t\tp = m + 1\n\t\tq = n + 2\n\t\tnod = node()\n\t\tnod.i = p\n\t\tnod.j = q\n\t\tif p >= 0 and q >= 0 and (p < self.n) and (q < self.n):\n\t\t\tnod.h = self.heuristic(nod)\n\t\t\tnod.parent = e\n\t\t\tnod.move = 'LR'\n\t\t\tif nod.h < e.h:\n\t\t\t\tmove.append(nod)\n\t\tp = m - 1\n\t\tq = n + 2\n\t\tnod = node()\n\t\tnod.i = p\n\t\tnod.j = q\n\t\tif p >= 0 and q >= 0 and (p < self.n) and (q < self.n):\n\t\t\tnod.h = self.heuristic(nod)\n\t\t\tnod.parent = e\n\t\t\tnod.move = 'LL'\n\t\t\tif nod.h < e.h:\n\t\t\t\tmove.append(nod)\n\t\tp = m - 2\n\t\tq = n\n\t\tnod = node()\n\t\tnod.i = p\n\t\tnod.j = q\n\t\tif p >= 0 and q >= 0 and (p < self.n) and (q < self.n):\n\t\t\tnod.h = self.heuristic(nod)\n\t\t\tnod.parent = e\n\t\t\tnod.move = 'L'\n\t\t\tif nod.h < e.h:\n\t\t\t\tmove.append(nod)\n\t\treturn move\n\n\tdef heuristic(self, n):\n\t\tn.i\n\t\tmax_i = max(n.i, self.end.i)\n\t\tmin_i = min(n.i, self.end.i)\n\t\tmax_j = max(n.j, self.end.j)\n\t\tmin_j = min(n.j, self.end.j)\n\t\ta = max_i - min_i\n\t\tb = max_j - min_j\n\t\ta = a * a\n\t\tb = b * b\n\t\ts = a + b\n\t\treturn s\n\n\tdef compare(self, a, b):\n\t\tif a.i == b.i and a.j == b.j:\n\t\t\treturn True\n\t\treturn False\n\n\tdef removeseen(self, n):\n\t\tfor i in range(len(n)):\n\t\t\tt = 0\n\t\t\tfor j in range(len(self.openx)):\n\t\t\t\tif self.compare(n[i], self.openx[j]) == True:\n\t\t\t\t\tdel n[i]\n\t\t\t\t\tt = 1\n\t\t\t\t\tbreak\n\t\t\tif t == 1:\n\t\t\t\tbreak\n\t\tfor i in range(len(n)):\n\t\t\tt = 0\n\t\t\tfor j in range(len(self.openx)):\n\t\t\t\tif self.compare(n[i], self.openx[j]) == True:\n\t\t\t\t\tdel n[i]\n\t\t\t\t\tt = 1\n\t\t\t\t\tbreak\n\t\t\tif t == 1:\n\t\t\t\tbreak\n\t\tfor i in range(len(n)):\n\t\t\tt = 0\n\t\t\tfor j in range(len(self.openx)):\n\t\t\t\tif self.compare(n[i], self.openx[j]) == True:\n\t\t\t\t\tdel n[i]\n\t\t\t\t\tt = 1\n\t\t\t\t\tbreak\n\t\t\tif t == 1:\n\t\t\t\tbreak\n\t\tfor i in range(len(n)):\n\t\t\tt = 0\n\t\t\tfor j in range(len(self.openx)):\n\t\t\t\tif self.compare(n[i], self.openx[j]) == True:\n\t\t\t\t\tdel n[i]\n\t\t\t\t\tt = 1\n\t\t\t\t\tbreak\n\t\t\tif t == 1:\n\t\t\t\tbreak\n\t\tfor i in range(len(n)):\n\t\t\tt = 0\n\t\t\tfor j in range(len(self.openx)):\n\t\t\t\tif self.compare(n[i], self.openx[j]) == True:\n\t\t\t\t\tdel n[i]\n\t\t\t\t\tt = 1\n\t\t\t\t\tbreak\n\t\t\tif t == 1:\n\t\t\t\tbreak\n\t\tfor i in range(len(n)):\n\t\t\tt = 0\n\t\t\tfor j in range(len(self.openx)):\n\t\t\t\tif self.compare(n[i], self.openx[j]) == True:\n\t\t\t\t\tdel n[i]\n\t\t\t\t\tt = 1\n\t\t\t\t\tbreak\n\t\t\tif t == 1:\n\t\t\t\tbreak\n\t\tfor i in range(len(n)):\n\t\t\tt = 0\n\t\t\tfor j in range(len(self.closex)):\n\t\t\t\tif self.compare(n[i], self.closex[j]) == True:\n\t\t\t\t\tdel n[i]\n\t\t\t\t\tt = 1\n\t\t\t\t\tbreak\n\t\t\tif t == 1:\n\t\t\t\tbreak\n\t\tfor i in range(len(n)):\n\t\t\tt = 0\n\t\t\tfor j in range(len(self.closex)):\n\t\t\t\tif self.compare(n[i], self.closex[j]) == True:\n\t\t\t\t\tdel n[i]\n\t\t\t\t\tt = 1\n\t\t\t\t\tbreak\n\t\t\tif t == 1:\n\t\t\t\tbreak\n\t\tfor i in range(len(n)):\n\t\t\tt = 0\n\t\t\tfor j in range(len(self.closex)):\n\t\t\t\tif self.compare(n[i], self.closex[j]) == True:\n\t\t\t\t\tdel n[i]\n\t\t\t\t\tt = 1\n\t\t\t\t\tbreak\n\t\t\tif t == 1:\n\t\t\t\tbreak\n\t\tfor i in range(len(n)):\n\t\t\tt = 0\n\t\t\tfor j in range(len(self.closex)):\n\t\t\t\tif self.compare(n[i], self.closex[j]) == True:\n\t\t\t\t\tdel n[i]\n\t\t\t\t\tt = 1\n\t\t\t\t\tbreak\n\t\t\tif t == 1:\n\t\t\t\tbreak\n\t\tfor i in range(len(n)):\n\t\t\tt = 0\n\t\t\tfor j in range(len(self.closex)):\n\t\t\t\tif self.compare(n[i], self.closex[j]) == True:\n\t\t\t\t\tdel n[i]\n\t\t\t\t\tt = 1\n\t\t\t\t\tbreak\n\t\t\tif t == 1:\n\t\t\t\tbreak\n\t\tfor i in range(len(n)):\n\t\t\tt = 0\n\t\t\tfor j in range(len(self.closex)):\n\t\t\t\tif self.compare(n[i], self.closex[j]) == True:\n\t\t\t\t\tdel n[i]\n\t\t\t\t\tt = 1\n\t\t\t\t\tbreak\n\t\t\tif t == 1:\n\t\t\t\tbreak\n\t\treturn n\n\n\tdef printpath(self, x):\n\t\ta = []\n\t\ta.append(x)\n\t\tpar = x.parent\n\t\twhile par != None:\n\t\t\ta.append(par)\n\t\t\tpar = par.parent\n\t\tif self.paths[len(a)] == None:\n\t\t\tself.paths[len(a)] = a\n\n\tdef solution(self):\n\t\tfor i in range(100):\n\t\t\tif self.paths[i] != None:\n\t\t\t\tprint(i - 1)\n\t\t\t\tfor j in range(len(self.paths[i])):\n\t\t\t\t\tif self.paths[i][-1 - j].move != None:\n\t\t\t\t\t\tprint(self.paths[i][-1 - j].move, end=' ')\n\t\t\t\treturn\n\t\tsol = 'Impossible'\n\t\tprint(sol)\n\t\treturn\n\ndef main():\n\tn = int(input())\n\tx = input()\n\tx = x.split()\n\tfor i in range(len(x)):\n\t\tx[i] = int(x[i])\n\ts = node()\n\te = node()\n\ts.i = x[1]\n\ts.j = x[0]\n\te.i = x[3]\n\te.j = x[2]\n\tfind = redknight_chess(n, s, e)\n\tfind.search()\n\tfind.solution()\nmain()\n", "import sys\n\ndef printShortestPath(n, i_start, j_start, i_end, j_end):\n\tseen = {(i_start, j_start)}\n\tpathes = [[(i_start, j_start)]]\n\treached = False\n\twhile pathes and (not reached):\n\t\ttemp = []\n\t\tfor path in pathes:\n\t\t\t(x, y) = path[-1]\n\t\t\tul = (x - 2, y - 1)\n\t\t\tur = (x - 2, y + 1)\n\t\t\tr = (x, y + 2)\n\t\t\tl = (x, y - 2)\n\t\t\tlr = (x + 2, y + 1)\n\t\t\tll = (x + 2, y - 1)\n\t\t\torder = [ul, ur, r, lr, ll, l]\n\t\t\tif (i_end, j_end) in order:\n\t\t\t\treached = path[:] + [(i_end, j_end)]\n\t\t\t\tbreak\n\t\t\telse:\n\t\t\t\tfor (i, j) in order:\n\t\t\t\t\tif i in range(n) and j in range(n):\n\t\t\t\t\t\tif (i, j) not in seen:\n\t\t\t\t\t\t\tseen.add((i, j))\n\t\t\t\t\t\t\ttemp.append(path[:] + [(i, j)])\n\t\tpathes = temp\n\tif not reached:\n\t\tprint('Impossible')\n\telse:\n\t\tprint(len(reached) - 1)\n\t\torder = ''\n\t\tpos = (i_start, j_start)\n\t\tfor (i, j) in reached[1:]:\n\t\t\tif i == pos[0]:\n\t\t\t\tif j > pos[1]:\n\t\t\t\t\torder = order + 'R '\n\t\t\t\telse:\n\t\t\t\t\torder = order + 'L '\n\t\t\telif i > pos[0]:\n\t\t\t\tif j > pos[1]:\n\t\t\t\t\torder = order + 'LR '\n\t\t\t\telse:\n\t\t\t\t\torder = order + 'LL '\n\t\t\telif j > pos[1]:\n\t\t\t\torder = order + 'UR '\n\t\t\telse:\n\t\t\t\torder = order + 'UL '\n\t\t\tpos = (i, j)\n\t\tprint(order[:-1])\nn = int(input().strip())\n(i_start, j_start, i_end, j_end) = input().strip().split(' ')\n(i_start, j_start, i_end, j_end) = [int(i_start), int(j_start), int(i_end), int(j_end)]\nprintShortestPath(n, i_start, j_start, i_end, j_end)\n", "import sys\n\nclass Node:\n\n\tdef __init__(self, i, j, d, p):\n\t\tself.i = i\n\t\tself.j = j\n\t\tself.d = d\n\t\tself.p = p\n\ndef printShortestPath(n, ist, jst, ind, jnd):\n\tif n <= 3:\n\t\tprint('Impossible')\n\t\treturn\n\tmps = [[-2, -1], [-2, 1], [0, 2], [2, 1], [2, -1], [0, -2]]\n\tnts = ['UL', 'UR', 'R', 'LR', 'LL', 'L']\n\tpts = [Node(ist, jst, None, None)]\n\tvisited = [ist * n + jst + 1]\n\tno = 0\n\tnn = None\n\tis_continue = True\n\twhile is_continue:\n\t\ttpts = []\n\t\tno += 1\n\t\tfor p in pts:\n\t\t\tfor (mp, nt) in zip(mps, nts):\n\t\t\t\tni = p.i + mp[0]\n\t\t\t\tnj = p.j + mp[1]\n\t\t\t\tidx = ni * n + nj + 1\n\t\t\t\tif ni < 0 or ni >= n or nj < 0 or (nj >= n) or (idx in visited):\n\t\t\t\t\tcontinue\n\t\t\t\telse:\n\t\t\t\t\tnn = Node(ni, nj, nt, p)\n\t\t\t\t\tif ni == ind and nj == jnd:\n\t\t\t\t\t\tprint(no)\n\t\t\t\t\t\ttnn = nn\n\t\t\t\t\t\tpns = []\n\t\t\t\t\t\twhile tnn.p:\n\t\t\t\t\t\t\tpns.append(tnn.d)\n\t\t\t\t\t\t\ttnn = tnn.p\n\t\t\t\t\t\tprint(' '.join(reversed(pns)))\n\t\t\t\t\t\treturn\n\t\t\t\t\telse:\n\t\t\t\t\t\ttpts.append(nn)\n\t\t\t\t\t\tvisited.append(idx)\n\t\tif not tpts:\n\t\t\tprint('Impossible')\n\t\t\treturn\n\t\telse:\n\t\t\tpts = tpts\nn = int(input().strip())\n(i_start, j_start, i_end, j_end) = input().strip().split(' ')\n(i_start, j_start, i_end, j_end) = [int(i_start), int(j_start), int(i_end), int(j_end)]\nprintShortestPath(n, i_start, j_start, i_end, j_end)\n", "__author__ = 'Tola'\nfrom collections import deque\nimport sys\n\ndef printShortestPath(n, i_start, j_start, i_end, j_end, queue, state):\n\twhile True:\n\t\tif len(queue) == 0:\n\t\t\tbreak\n\t\tcurrent = queue.popleft()\n\t\t(i_s, j_s, moves) = current\n\t\tif 0 <= i_s - 2 < n and 0 <= j_s - 1 < n and state[i_s - 2][j_s - 1]:\n\t\t\tstate[i_s - 2][j_s - 1] = False\n\t\t\tif i_s - 2 == i_end and j_s - 1 == j_end:\n\t\t\t\treturn moves + ['UL']\n\t\t\tqueue.append([i_s - 2, j_s - 1, moves + ['UL']])\n\t\tif 0 <= i_s - 2 < n and 0 <= j_s + 1 < n and state[i_s - 2][j_s + 1]:\n\t\t\tstate[i_s - 2][j_s + 1] = False\n\t\t\tif i_s - 2 == i_end and j_s + 1 == j_end:\n\t\t\t\treturn moves + ['UR']\n\t\t\tqueue.append([i_s - 2, j_s + 1, moves + ['UR']])\n\t\tif 0 <= j_s + 2 < n and state[i_s][j_s + 2]:\n\t\t\tstate[i_s][j_s + 2] = False\n\t\t\tif i_s == i_end and j_s + 2 == j_end:\n\t\t\t\treturn moves + ['R']\n\t\t\tqueue.append([i_s, j_s + 2, moves + ['R']])\n\t\tif 0 <= i_s + 2 < n and 0 <= j_s + 1 < n and state[i_s + 2][j_s + 1]:\n\t\t\tstate[i_s + 2][j_s + 1] = False\n\t\t\tif i_s + 2 == i_end and j_s + 1 == j_end:\n\t\t\t\treturn moves + ['LR']\n\t\t\tqueue.append([i_s + 2, j_s + 1, moves + ['LR']])\n\t\tif 0 <= i_s + 2 < n and 0 <= j_s - 1 < n and state[i_s + 2][j_s - 1]:\n\t\t\tstate[i_s + 2][j_s - 1] = False\n\t\t\tif i_s + 2 == i_end and j_s - 1 == j_end:\n\t\t\t\treturn moves + ['LL']\n\t\t\tqueue.append([i_s + 2, j_s - 1, moves + ['LL']])\n\t\tif 0 <= j_s - 2 < n and state[i_s][j_s - 2]:\n\t\t\tstate[i_s][j_s - 2] = False\n\t\t\tif i_s == i_end and j_s - 2 == j_end:\n\t\t\t\treturn moves + ['L']\n\t\t\tqueue.append([i_s, j_s - 2, moves + ['L']])\nn = int(input().strip())\n(i_start, j_start, i_end, j_end) = input().strip().split(' ')\n(i_start, j_start, i_end, j_end) = [int(i_start), int(j_start), int(i_end), int(j_end)]\nstate = [[True] * n for i in range(n)]\nqueue = deque([[i_start, j_start, []]])\nstate[i_start][j_start] = False\nretVal = printShortestPath(n, i_start, j_start, i_end, j_end, queue, state)\nif retVal:\n\tprint(len(retVal))\n\tprint(' '.join(retVal))\nelse:\n\tprint('Impossible')\n", "from collections import defaultdict\nfrom itertools import product\nn = int(input())\n(x1, y1, x2, y2) = map(int, input().strip().split())\n(start, end) = ((x1, y1), (x2, y2))\ndist = defaultdict(lambda : float('inf'))\ndist[end] = 0\nfor _ in range(n * n + 1):\n\tunchanged = True\n\tfor (x, y) in product(range(n), range(n)):\n\t\tval = 1 + min(dist[x, y - 2], dist[x + 2, y + 1], dist[x - 2, y - 1], dist[x, y + 2], dist[x - 2, y + 1], dist[x + 2, y - 1])\n\t\tif val < dist[x, y]:\n\t\t\tdist[x, y] = val\n\t\t\tunchanged = False\n\tif unchanged:\n\t\tbreak\nif dist[start] == float('inf'):\n\tprint('Impossible')\nelse:\n\t(x, y) = start\n\tpath = []\n\twhile (x, y) != end:\n\t\td = dist[x, y]\n\t\tif dist[x - 2, y - 1] == d - 1:\n\t\t\tpath.append('UL')\n\t\t\t(x, y) = (x - 2, y - 1)\n\t\telif dist[x - 2, y + 1] == d - 1:\n\t\t\tpath.append('UR')\n\t\t\t(x, y) = (x - 2, y + 1)\n\t\telif dist[x, y + 2] == d - 1:\n\t\t\tpath.append('R')\n\t\t\t(x, y) = (x, y + 2)\n\t\telif dist[x + 2, y + 1] == d - 1:\n\t\t\tpath.append('LR')\n\t\t\t(x, y) = (x + 2, y + 1)\n\t\telif dist[x + 2, y - 1] == d - 1:\n\t\t\tpath.append('LL')\n\t\t\t(x, y) = (x + 2, y - 1)\n\t\telif dist[x, y - 2] == d - 1:\n\t\t\tpath.append('L')\n\t\t\t(x, y) = (x, y - 2)\n\tprint(dist[start])\n\tprint(*path, sep=' ')\n", "import sys\n\ndef printShortestPath(n, i_start, j_start, i_end, j_end):\n\tmoveNames = ['UL ', 'UR ', 'R ', 'LR ', 'LL ', 'L ']\n\tmoves = [(-2, -1), (-2, 1), (0, 2), (2, 1), (2, -1), (0, -2)]\n\tmoveCounts = [[-1 for i in range(n)] for j in range(n)]\n\tcurrCount = 0\n\tmoveCounts[i_end][j_end] = 0\n\tcurrLocs = [(i_end, j_end)]\n\twhile len(currLocs) > 0:\n\t\tcurrCount += 1\n\t\tnextLocs = set()\n\t\tfor (i, j) in currLocs:\n\t\t\tfor (iDiff, jDiff) in moves:\n\t\t\t\tnewI = i + iDiff\n\t\t\t\tnewJ = j + jDiff\n\t\t\t\tif newI >= 0 and newI < n and (newJ >= 0) and (newJ < n) and (moveCounts[newI][newJ] == -1):\n\t\t\t\t\tnextLocs.add((newI, newJ))\n\t\t\t\t\tmoveCounts[newI][newJ] = currCount\n\t\tcurrLocs = nextLocs\n\tif moveCounts[i_start][j_start] == -1:\n\t\tprint('Impossible')\n\telse:\n\t\tmoveCount = moveCounts[i_start][j_start]\n\t\tmoveList = ''\n\t\ti = i_start\n\t\tj = j_start\n\t\twhile i != i_end or j != j_end:\n\t\t\tfor index in range(len(moves)):\n\t\t\t\tnewI = i + moves[index][0]\n\t\t\t\tnewJ = j + moves[index][1]\n\t\t\t\tif newI >= 0 and newI < n and (newJ >= 0) and (newJ < n) and (moveCounts[newI][newJ] == moveCount - 1):\n\t\t\t\t\ti = newI\n\t\t\t\t\tj = newJ\n\t\t\t\t\tmoveList += moveNames[index]\n\t\t\t\t\tmoveCount -= 1\n\t\t\t\t\tbreak\n\t\tprint(moveCounts[i_start][j_start])\n\t\tprint(moveList)\nn = int(input().strip())\n(i_start, j_start, i_end, j_end) = input().strip().split(' ')\n(i_start, j_start, i_end, j_end) = [int(i_start), int(j_start), int(i_end), int(j_end)]\nprintShortestPath(n, i_start, j_start, i_end, j_end)\n", "import sys\nsys.setrecursionlimit(150000)\nd = {1: 'UL', 2: 'UR', 3: 'R', 4: 'LR', 5: 'LL', 6: 'L'}\n\ndef trace_route(i1, j1, i2, j2):\n\tcount = 0\n\ts = []\n\twhile i1 != i2 or j1 != j2:\n\t\tif i1 - i2 >= 2 and j1 - j2 >= 1:\n\t\t\ts.append(1)\n\t\t\ti1 -= 2\n\t\t\tj1 -= 1\n\t\telif i1 - i2 >= 2 and j2 - j1 >= 1:\n\t\t\ts.append(2)\n\t\t\ti1 -= 2\n\t\t\tj1 += 1\n\t\telif i1 == i2 and j2 - j1 >= 2:\n\t\t\ts.append(3)\n\t\t\tj1 += 2\n\t\telif i2 - i1 >= 2 and j2 - j1 >= 1:\n\t\t\ts.append(4)\n\t\t\tj1 += 1\n\t\t\ti1 += 2\n\t\telif i2 - i1 >= 2 and j1 - j2 >= 1:\n\t\t\ts.append(5)\n\t\t\tj1 -= 1\n\t\t\ti1 += 2\n\t\telif i1 == i2 and j1 - j2 >= 2:\n\t\t\ts.append(6)\n\t\t\tj1 -= 2\n\t\telif j2 == j1:\n\t\t\tif i1 < i2:\n\t\t\t\ts.append(4)\n\t\t\t\tj1 += 1\n\t\t\t\ti1 += 2\n\t\t\telse:\n\t\t\t\ts.append(1)\n\t\t\t\ti1 -= 2\n\t\t\t\tj1 -= 1\n\t\tcount += 1\n\treturn (count, list(sorted(s)))\n\ndef is_ok(grid, i, j, n):\n\treturn i >= 0 and j >= 0 and (i < n) and (j < n) and (not grid[i][j])\n\ndef propagate(i, j, grid, n):\n\tgrid[i][j] = True\n\tif is_ok(grid, i - 2, j - 1, n):\n\t\tpropagate(i - 2, j - 1, grid, n)\n\tif is_ok(grid, i - 2, j + 1, n):\n\t\tpropagate(i - 2, j + 1, grid, n)\n\tif is_ok(grid, i, j + 2, n):\n\t\tpropagate(i, j + 2, grid, n)\n\tif is_ok(grid, i + 2, j + 1, n):\n\t\tpropagate(i + 2, j + 1, grid, n)\n\tif is_ok(grid, i + 2, j - 1, n):\n\t\tpropagate(i + 2, j - 1, grid, n)\n\tif is_ok(grid, i, j - 2, n):\n\t\tpropagate(i, j - 2, grid, n)\nn = int(input())\ngrid = []\nfor i in range(n):\n\tl = []\n\tfor j in range(n):\n\t\tl.append(False)\n\tgrid.append(l)\n(istart, jstart, iend, jend) = list(map(int, input().split()))\npropagate(istart, jstart, grid, n)\nif grid[iend][jend]:\n\t(c, s) = trace_route(istart, jstart, iend, jend)\n\tprint(c)\n\ts = list(map(lambda x: d[x], s))\n\tprint(' '.join(s))\nelse:\n\tprint('Impossible')\n", "def printShortestPath(n, i_start, j_start, i_end, j_end):\n\tvertdist = i_end - i_start\n\thordist = j_end - j_start\n\tif vertdist % 2 == 1:\n\t\tprint('Impossible')\n\telif vertdist % 4 == 2 and hordist % 2 == 0:\n\t\tprint('Impossible')\n\telif vertdist % 4 == 0 and hordist % 2 == 1:\n\t\tprint('Impossible')\n\telse:\n\t\tvertmoves = int(abs(vertdist / 2))\n\t\tif abs(hordist) <= vertmoves:\n\t\t\tmoves = vertmoves\n\t\t\thormoves = 0\n\t\telse:\n\t\t\thormoves = int((abs(hordist) - vertmoves) / 2)\n\t\t\tmoves = vertmoves + hormoves\n\t\tprint(int(moves))\n\t\ts = ''\n\t\tif vertdist == 0:\n\t\t\tif hordist > 0:\n\t\t\t\tfor i in range(hormoves):\n\t\t\t\t\ts += 'R '\n\t\t\telif hordist < 0:\n\t\t\t\tfor i in range(hormoves):\n\t\t\t\t\ts += 'L '\n\t\telif vertdist < 0:\n\t\t\tif abs(hordist) >= vertmoves:\n\t\t\t\tif hordist < 0:\n\t\t\t\t\tfor i in range(vertmoves):\n\t\t\t\t\t\ts += 'UL '\n\t\t\t\t\tfor i in range(hormoves):\n\t\t\t\t\t\ts += 'L '\n\t\t\t\telse:\n\t\t\t\t\tfor i in range(vertmoves):\n\t\t\t\t\t\ts += 'UR '\n\t\t\t\t\tfor i in range(hormoves):\n\t\t\t\t\t\ts += 'R '\n\t\t\telse:\n\t\t\t\tulmoves = int((vertmoves - hordist) / 2)\n\t\t\t\turmoves = vertmoves - ulmoves\n\t\t\t\tif ulmoves <= j_start:\n\t\t\t\t\tfor i in range(ulmoves):\n\t\t\t\t\t\ts += 'UL '\n\t\t\t\t\tfor i in range(urmoves):\n\t\t\t\t\t\ts += 'UR '\n\t\t\t\telse:\n\t\t\t\t\tfor i in range(j_start):\n\t\t\t\t\t\ts += 'UL '\n\t\t\t\t\tfor i in range(int((vertmoves - j_start) / 2)):\n\t\t\t\t\t\ts += 'UR UL '\n\t\t\t\t\tif (vertmoves - j_start) % 2 == 1:\n\t\t\t\t\t\ts += 'UR '\n\t\telif vertdist > 0:\n\t\t\tif abs(hordist) >= vertmoves:\n\t\t\t\tif hordist < 0:\n\t\t\t\t\tfor i in range(vertmoves):\n\t\t\t\t\t\ts += 'LL '\n\t\t\t\t\tfor i in range(hormoves):\n\t\t\t\t\t\ts += 'L '\n\t\t\t\telse:\n\t\t\t\t\tfor i in range(hormoves):\n\t\t\t\t\t\ts += 'R '\n\t\t\t\t\tfor i in range(vertmoves):\n\t\t\t\t\t\ts += 'LR '\n\t\t\telse:\n\t\t\t\tllmoves = int((vertmoves - hordist) / 2)\n\t\t\t\tlrmoves = vertmoves - llmoves\n\t\t\t\tif lrmoves < n - j_start:\n\t\t\t\t\tfor i in range(lrmoves):\n\t\t\t\t\t\ts += 'LR '\n\t\t\t\t\tfor i in range(llmoves):\n\t\t\t\t\t\ts += 'LL '\n\t\t\t\telse:\n\t\t\t\t\tfor i in range(n - j_start - 1):\n\t\t\t\t\t\ts += 'LR '\n\t\t\t\t\tfor i in range(int((vertmoves - n + j_start + 1) / 2)):\n\t\t\t\t\t\ts += 'LL LR '\n\t\t\t\t\tif (vertmoves - n + j_start + 1) % 2 == 1:\n\t\t\t\t\t\ts += 'LL '\n\t\tprint(s)\nn = int(input().strip())\n(i_start, j_start, i_end, j_end) = input().strip().split(' ')\n(i_start, j_start, i_end, j_end) = [int(i_start), int(j_start), int(i_end), int(j_end)]\nprintShortestPath(n, i_start, j_start, i_end, j_end)\n", "import sys\nsys.setrecursionlimit(1000000)\nfrom copy import copy\nALREADY_DONE = set()\nMOVES = {(0, 2): 'R', (0, -2): 'L', (-2, 1): 'UR', (-2, -1): 'UL', (2, 1): 'LR', (2, -1): 'LL'}\nMOVES_ORDERED = [(-2, -1), (-2, 1), (0, 2), (2, 1), (2, -1), (0, -2)]\n\ndef compute_new_pos(pos, delta):\n\treturn (pos[0] + delta[0], pos[1] + delta[1])\n\ndef is_out(pos, n):\n\treturn pos[0] < 0 or pos[0] >= n or pos[1] >= n or (pos[1] < 0)\n\nclass RK:\n\n\tdef __init__(self, position, n, target, historic, already_done):\n\t\tself.position = position\n\t\tself.target = target\n\t\tself.historic = historic\n\t\tself.already_done = already_done\n\t\tself.n = n\n\nclass RK_BFS(RK):\n\n\tdef __init__(self, position, n, target, historic, already_done, count_rk, queue, all_pos):\n\t\tRK.__init__(self, position, n, target, historic, already_done)\n\t\tself.count_rk = count_rk\n\t\tself.queue = queue\n\t\tself.all_pos = all_pos + [position]\n\n\tdef expand(self):\n\t\tself.count_rk += 1\n\t\tfor move in MOVES_ORDERED:\n\t\t\ttmp_pos = compute_new_pos(self.position, move)\n\t\t\tif tmp_pos == self.target:\n\t\t\t\tnew_histo = self.historic.copy() + [MOVES[move]]\n\t\t\t\tprint(str(len(new_histo)))\n\t\t\t\tprint(' '.join(new_histo))\n\t\t\t\tsys.exit(0)\n\t\t\telif not is_out(tmp_pos, self.n) and (not tmp_pos in self.already_done):\n\t\t\t\tnew_histo = self.historic.copy() + [MOVES[move]]\n\t\t\t\tself.count_rk += 1\n\t\t\t\tself.already_done.update([tmp_pos])\n\t\t\t\trk_bfs = RK_BFS(tmp_pos, self.n, self.target, new_histo, self.already_done, self.count_rk, self.queue, self.all_pos)\n\t\t\t\tself.queue.append(rk_bfs)\n\t\tif len(self.queue) == 0:\n\t\t\tprint('Impossible')\n\t\t\tsys.exit(0)\n\t\trk = self.queue.pop(0)\n\t\trk.expand()\n\t\tself.count_rk -= 1\n\t\tif self.count_rk == 0:\n\t\t\tprint('Impossible')\n\t\t\tsys.exit(0)\n\ndef printShortestPath(n, i_start, j_start, i_end, j_end):\n\tif i_start % 2 != i_end % 2:\n\t\tprint('Impossible')\n\t\tsys.exit(0)\n\talready_done = set(tuple([i_start, j_start]))\n\thistoric = []\n\tqueue = list()\n\tall_pos = list()\n\tbk = RK_BFS((i_start, j_start), n, (i_end, j_end), historic, already_done, 0, queue, all_pos)\n\tbk.expand()\nn = int(input().strip())\n(i_start, j_start, i_end, j_end) = input().strip().split(' ')\n(i_start, j_start, i_end, j_end) = [int(i_start), int(j_start), int(i_end), int(j_end)]\nprintShortestPath(n, i_start, j_start, i_end, j_end)\n", "import sys\ndic = {'1': 'UL', '2': 'UR', '3': 'R', '4': 'LR', '5': 'LL', '6': 'L'}\n\ndef printShortestPath(n, i_start, j_start, i_end, j_end):\n\tmoves = 0\n\tstring = ''\n\ttab = []\n\tif abs(i_start - i_end) % 2 == 0 and (i_start % 4 != i_end % 4 and j_start % 2 != j_end % 2 or (i_start % 4 == i_end % 4 and j_start % 2 == j_end % 2)):\n\t\twhile i_start != i_end or j_start != j_end:\n\t\t\tif i_start > i_end:\n\t\t\t\tif j_start >= j_end:\n\t\t\t\t\tstring += '1 '\n\t\t\t\t\tmoves += 1\n\t\t\t\t\ti_start -= 2\n\t\t\t\t\tj_start -= 1\n\t\t\t\telif j_start < j_end:\n\t\t\t\t\tstring += '2 '\n\t\t\t\t\tmoves += 1\n\t\t\t\t\ti_start -= 2\n\t\t\t\t\tj_start += 1\n\t\t\telif i_start == i_end and j_start < j_end:\n\t\t\t\tstring += '3 '\n\t\t\t\tmoves += 1\n\t\t\t\tj_start += 2\n\t\t\telif i_start < i_end:\n\t\t\t\tif j_start <= j_end:\n\t\t\t\t\tstring += '4 '\n\t\t\t\t\tmoves += 1\n\t\t\t\t\ti_start += 2\n\t\t\t\t\tj_start += 1\n\t\t\t\telif j_start > j_end:\n\t\t\t\t\tstring += '5 '\n\t\t\t\t\tmoves += 1\n\t\t\t\t\ti_start += 2\n\t\t\t\t\tj_start -= 1\n\t\t\telif i_start == i_end and j_start > j_end:\n\t\t\t\tstring += '6 '\n\t\t\t\tmoves += 1\n\t\t\t\tj_start -= 2\n\t\tspl = string.split(' ')\n\t\tspl.pop()\n\t\tspl = sorted(spl)\n\t\tfor item in spl:\n\t\t\ttab.append(dic.get(item, item))\n\t\tprint(moves)\n\t\tprint(' '.join(tab))\n\telse:\n\t\tprint('Impossible')\nn = int(input().strip())\n(i_start, j_start, i_end, j_end) = input().strip().split(' ')\n(i_start, j_start, i_end, j_end) = [int(i_start), int(j_start), int(i_end), int(j_end)]\nprintShortestPath(n, i_start, j_start, i_end, j_end)\n", "import sys\n\ndef canReach(n, x0, y0, x1, y1):\n\tx = abs(x0 - x1)\n\ty = abs(y0 - y1)\n\treturn x % 2 == 0 and (y + x / 2) % 2 == 0\norder = {'UL': 0, 'UR': 1, 'R': 2, 'LR': 3, 'LL': 4, 'L': 5}\n\ndef printShortestPath(n, i_start, j_start, i_end, j_end):\n\tif not canReach(n, i_start, j_start, i_end, j_end):\n\t\tprint('Impossible')\n\t\treturn\n\t(x, y) = (i_start, j_start)\n\tans = []\n\twhile x != i_end or y != j_end:\n\t\tr = []\n\t\tif x > i_end:\n\t\t\tr.append('U')\n\t\t\tx -= 2\n\t\telif x < i_end:\n\t\t\tr.append('L')\n\t\t\tx += 2\n\t\tif y > j_end:\n\t\t\tr.append('L')\n\t\t\ty -= 2 if len(r) == 1 else 1\n\t\telse:\n\t\t\tr.append('R')\n\t\t\ty += 2 if len(r) == 1 else 1\n\t\tans.append(''.join(r))\n\tans = sorted(ans, key=lambda x: order[x])\n\tprint(len(ans))\n\tprint(' '.join(ans))\nn = int(input().strip())\n(i_start, j_start, i_end, j_end) = input().strip().split(' ')\n(i_start, j_start, i_end, j_end) = [int(i_start), int(j_start), int(i_end), int(j_end)]\nprintShortestPath(n, i_start, j_start, i_end, j_end)\n", "import sys\n\nclass Node:\n\tvalue = None\n\tdirection = None\n\tchildren = []\n\tparent = None\n\tvisited = False\n\tdepth = 0\n\n\tdef __init__(self, value=None, direction=None):\n\t\tself.value = value\n\t\tself.direction = direction\n\n\tdef isLeaf(self):\n\t\treturn len(self.children) == 0\n\n\tdef isRoot(self):\n\t\treturn not self.parent\n\n\tdef asChildOf(self, parentNode):\n\t\tself.parent = parentNode\n\t\tself.depth = parentNode.depth + 1\n\t\tparentNode.children.append(self)\n\n\tdef getUL(self):\n\t\treturn (self.value[0] - 2, self.value[1] - 1)\n\n\tdef getUR(self):\n\t\treturn (self.value[0] - 2, self.value[1] + 1)\n\n\tdef getL(self):\n\t\treturn (self.value[0], self.value[1] - 2)\n\n\tdef getR(self):\n\t\treturn (self.value[0], self.value[1] + 2)\n\n\tdef getLL(self):\n\t\treturn (self.value[0] + 2, self.value[1] - 1)\n\n\tdef getLR(self):\n\t\treturn (self.value[0] + 2, self.value[1] + 1)\n\n\tdef legalCoor(self, coor, n):\n\t\tr = coor[0]\n\t\tc = coor[1]\n\t\treturn (r >= 0 and r < n) and (c >= 0 and c < n)\n\n\tdef isReached(self, cur, des):\n\t\treturn cur == des\n\n\tdef getLegalChild(self, nodes, n):\n\t\torder = ['UL', 'UR', 'R', 'LR', 'LL', 'L']\n\t\tres = dict()\n\t\tif self.legalCoor(self.getUL(), n):\n\t\t\tres['UL'] = self.getUL()\n\t\tif self.legalCoor(self.getUR(), n):\n\t\t\tres['UR'] = self.getUR()\n\t\tif self.legalCoor(self.getR(), n):\n\t\t\tres['R'] = self.getR()\n\t\tif self.legalCoor(self.getLR(), n):\n\t\t\tres['LR'] = self.getLR()\n\t\tif self.legalCoor(self.getLL(), n):\n\t\t\tres['LL'] = self.getLL()\n\t\tif self.legalCoor(self.getL(), n):\n\t\t\tres['L'] = self.getL()\n\t\tfinal = []\n\t\tfor key in order:\n\t\t\tif key in res.keys() and (not nodes[res[key]].visited):\n\t\t\t\te = nodes[res[key]]\n\t\t\t\te.direction = key\n\t\t\t\te.depth = self.depth + 1\n\t\t\t\te.parent = self.value\n\t\t\t\te.visited = True\n\t\t\t\tfinal.append(e)\n\t\treturn final\n\ndef bfs(n, r_start, c_start, r_end, c_end, nodes):\n\tqueue = []\n\troot = nodes[r_start, c_start]\n\tqueue.append(root)\n\troot.visited = True\n\treached = False\n\twhile not (reached == True or queue == []):\n\t\tnextL = []\n\t\tfor e in queue:\n\t\t\tnode = nodes[e.value]\n\t\t\tnode.visited = True\n\t\t\tnextL += node.getLegalChild(nodes, n)\n\t\tqueue = nextL\n\t\tfor e in queue:\n\t\t\tif e.isReached(e.value, (r_end, c_end)):\n\t\t\t\treached = True\n\t\t\t\tbreak\n\treturn nodes\n\ndef buildNodes(n):\n\tnodes = dict()\n\tfor i in range(n):\n\t\tfor j in range(n):\n\t\t\tnodes[i, j] = Node(value=(i, j))\n\treturn nodes\n\ndef printShortestPath(n, r_start, c_start, r_end, c_end):\n\tnodes = buildNodes(n)\n\tnodes = bfs(n, r_start, c_start, r_end, c_end, nodes)\n\tif nodes[r_end, c_end].visited == False:\n\t\tprint('Impossible')\n\telse:\n\t\tpath = []\n\t\tend = nodes[r_end, c_end]\n\t\tprint(end.depth)\n\t\twhile end.parent:\n\t\t\tpath.append(end.direction)\n\t\t\tend = nodes[end.parent]\n\t\tpath.reverse()\n\t\tprint(*path)\nn = int(input().strip())\n(i_start, j_start, i_end, j_end) = input().strip().split(' ')\n(i_start, j_start, i_end, j_end) = [int(i_start), int(j_start), int(i_end), int(j_end)]\nprintShortestPath(n, i_start, j_start, i_end, j_end)\n", "import sys\nfrom collections import deque\n\ndef reachable(i_start, j_start, i_end, j_end):\n\ti_mod = abs(i_end - i_start) % 4\n\tj_mod = abs(j_end - j_start) % 2\n\treturn i_mod == j_mod == 0 or (i_mod == 2 and j_mod == 1)\n\ndef printShortestPath(n, i_start, j_start, i_end, j_end):\n\tif not reachable(i_start, j_start, i_end, j_end):\n\t\tprint('Impossible')\n\telse:\n\t\tmove_names = {(-2, -1): 'UL', (-2, 1): 'UR', (0, 2): 'R', (2, 1): 'LR', (2, -1): 'LL', (0, -2): 'L'}\n\t\tpath = shortestPath(n, i_start, j_start, i_end, j_end)\n\t\tprint(len(path))\n\t\tprint(' '.join((move_names[p] for p in path)))\n\ndef between(n, x, y):\n\treturn y >= x and x <= n <= y or (y < x and y <= n <= x)\n\ndef shortestPath(n, i_start, j_start, i_end, j_end):\n\tend = (i_end, j_end)\n\n\tdef good_moves(loc):\n\t\tfor (i, j) in [(-2, -1), (-2, 1), (0, 2), (2, 1), (2, -1), (0, -2)]:\n\t\t\tni = loc[0] + i\n\t\t\tnj = loc[1] + j\n\t\t\tif 0 <= ni < n and 0 <= nj < n and (between(ni, end[0], loc[0]) or between(nj, end[1], loc[1])):\n\t\t\t\tyield (ni, nj)\n\n\tdef history(shortest_paths, loc):\n\t\tnew_loc = shortest_paths[loc]\n\t\tpath = []\n\t\twhile new_loc is not None:\n\t\t\tpath.append((loc[0] - new_loc[0], loc[1] - new_loc[1]))\n\t\t\tloc = new_loc\n\t\t\tnew_loc = shortest_paths[loc]\n\t\treturn list(reversed(path))\n\tshortest_paths = {(i_start, j_start): None}\n\tq = deque([(i_start, j_start)])\n\twhile True:\n\t\tloc = q.popleft()\n\t\tfor nloc in good_moves(loc):\n\t\t\tif nloc not in shortest_paths:\n\t\t\t\tshortest_paths[nloc] = loc\n\t\t\t\tq.append(nloc)\n\t\t\tif nloc == end:\n\t\t\t\treturn history(shortest_paths, end)\nn = int(input().strip())\n(i_start, j_start, i_end, j_end) = input().strip().split(' ')\n(i_start, j_start, i_end, j_end) = [int(i_start), int(j_start), int(i_end), int(j_end)]\nprintShortestPath(n, i_start, j_start, i_end, j_end)\n", "import sys\n\ndef outside(x, n):\n\tif x['x'] < 0 or x['x'] >= n or x['y'] < 0 or (x['y'] >= n):\n\t\treturn True\n\telse:\n\t\treturn False\n\ndef printShortestPath(n, i_start, j_start, i_end, j_end):\n\tpos = {'x': i_start, 'y': j_start}\n\tdes = {'x': i_end, 'y': j_end}\n\tnmov = 0\n\tdirec = []\n\tfor i in range(n):\n\t\tnewpos = {'UL': {'x': pos['x'] - 2, 'y': pos['y'] - 1, 'k': 0}, 'UR': {'x': pos['x'] - 2, 'y': pos['y'] + 1, 'k': 1}, 'R': {'x': pos['x'], 'y': pos['y'] + 2, 'k': 2}, 'LR': {'x': pos['x'] + 2, 'y': pos['y'] + 1, 'k': 3}, 'LL': {'x': pos['x'] + 2, 'y': pos['y'] - 1, 'k': 4}, 'L': {'x': pos['x'], 'y': pos['y'] - 2, 'k': 5}}\n\t\tfor mov in newpos:\n\t\t\tnewpos[mov]['d'] = abs(newpos[mov]['x'] - des['x']) + abs(newpos[mov]['y'] - des['y'])\n\t\tmov = min([(x[1]['d'], x[1]['k'], x[0]) for x in newpos.items() if not outside(x[1], n)])[2]\n\t\tif outside(newpos[mov], n) or min(newpos.items(), key=lambda x: (x[1]['d'], x[1]['k']))[1]['d'] == 1:\n\t\t\tprint('Impossible')\n\t\t\tbreak\n\t\tpos['x'] = newpos[mov]['x']\n\t\tpos['y'] = newpos[mov]['y']\n\t\tdirec.append((mov, newpos[mov]['k']))\n\t\tnmov = nmov + 1\n\t\tif pos['x'] == des['x'] and pos['y'] == des['y']:\n\t\t\tprint(nmov)\n\t\t\tprint(' '.join([x[0] for x in sorted(direc, key=lambda x: x[1])]))\n\t\t\tbreak\nn = int(input().strip())\n(i_start, j_start, i_end, j_end) = input().strip().split(' ')\n(i_start, j_start, i_end, j_end) = [int(i_start), int(j_start), int(i_end), int(j_end)]\nprintShortestPath(n, i_start, j_start, i_end, j_end)\n", "import sys\n\nclass Queue:\n\n\tdef __init__(self):\n\t\tself.items = []\n\n\tdef isEmpty(self):\n\t\treturn self.items == []\n\n\tdef enqueue(self, item):\n\t\tself.items.insert(0, item)\n\n\tdef dequeue(self):\n\t\treturn self.items.pop()\n\n\tdef size(self):\n\t\treturn len(self.items)\n\ndef check(n, x, y, visited):\n\tif x >= 0 and x < n and (y >= 0) and (y < n) and ((x, y) not in visited):\n\t\treturn True\n\telse:\n\t\treturn False\n\ndef printShortestPath(n, i_start, j_start, i_end, j_end):\n\tq = Queue()\n\tvisited = set()\n\tall_moves = {}\n\tavailable_moves = {(-2, -1): 'UL', (-2, +1): 'UR', (0, +2): 'R', (+2, +1): 'LR', (+2, -1): 'LL', (0, -2): 'L'}\n\tshortest_moves = []\n\tdirs = [(-2, -1), (-2, +1), (0, +2), (+2, +1), (+2, -1), (0, -2)]\n\tq.enqueue((i_start, j_start, 0))\n\twhile not q.isEmpty():\n\t\t(x, y, pathLen) = q.dequeue()\n\t\tif x == i_end and y == j_end:\n\t\t\tprint(pathLen)\n\t\t\tprevious = (x, y)\n\t\t\twhile previous != (i_start, j_start):\n\t\t\t\tnew_previous = all_moves[previous]\n\t\t\t\tdx = previous[0] - new_previous[0]\n\t\t\t\tdy = previous[1] - new_previous[1]\n\t\t\t\tshortest_moves.append(available_moves[dx, dy])\n\t\t\t\tprevious = new_previous\n\t\t\tprint(' '.join(map(str, list(reversed(shortest_moves)))))\n\t\t\treturn 0\n\t\tfor (dx, dy) in dirs:\n\t\t\tnx = x + dx\n\t\t\tny = y + dy\n\t\t\tif check(n, nx, ny, visited):\n\t\t\t\tall_moves[nx, ny] = (x, y)\n\t\t\t\tq.enqueue((nx, ny, pathLen + 1))\n\t\t\t\tvisited.add((nx, ny))\n\treturn -1\nn = int(input().strip())\n(i_start, j_start, i_end, j_end) = input().strip().split(' ')\n(i_start, j_start, i_end, j_end) = [int(i_start), int(j_start), int(i_end), int(j_end)]\nresult = printShortestPath(n, i_start, j_start, i_end, j_end)\nif result == -1:\n\tprint('Impossible')\n", "t = int(input())\n(x1, y1, x2, y2) = map(int, input().split())\nboard = [['' for i in range(t)] for j in range(t)]\nboard[x1][y1] = 'X'\ndirec = {'UL': [-2, -1], 'UR': [-2, 1], 'R': [0, 2], 'LR': [2, 1], 'LL': [2, -1], 'L': [0, -2]}\nstep = [(x1, y1)]\nwhile len(step) > 0:\n\t(curx, cury) = (step[0][0], step[0][1])\n\tfor d in ['UL', 'UR', 'R', 'LR', 'LL', 'L']:\n\t\t(t1, t2) = (curx + direc[d][0], cury + direc[d][1])\n\t\tif t1 >= 0 and t1 < t and (t2 >= 0) and (t2 < t) and (board[t1][t2] == ''):\n\t\t\tboard[t1][t2] = d\n\t\t\tstep.append((t1, t2))\n\tif board[x2][y2] != '':\n\t\tbreak\n\tdel step[0]\nif board[x2][y2] == '':\n\tprint('Impossible')\nelse:\n\tcnt = 0\n\tstep = []\n\t(x, y) = (x2, y2)\n\twhile x != x1 or y != y1:\n\t\tstep.append(board[x][y])\n\t\t(x, y) = (x - direc[board[x][y]][0], y - direc[board[x][y]][1])\n\t\tcnt += 1\n\tprint(cnt)\n\tprint(' '.join(step[::-1]))\n", "def possible(si, sj, ei, ej):\n\treturn si & 1 == ei & 1 and (si >> 1 & 1 == ei >> 1 & 1) == (sj & 1 == ej & 1)\nn = int(input())\n(starti, startj, endi, endj) = [int(x) for x in input().strip().split()]\n(UL, UR, R, LR, LL, L) = [0] * 6\nif not possible(starti, startj, endi, endj):\n\tprint('Impossible')\n\texit()\nwhile starti != endi or startj != endj:\n\tif starti < endi:\n\t\tif startj <= endj and startj + 1 < n:\n\t\t\tLR += 1\n\t\t\tstarti += 2\n\t\t\tstartj += 1\n\t\telse:\n\t\t\tLL += 1\n\t\t\tstarti += 2\n\t\t\tstartj -= 1\n\telif starti > endi:\n\t\tif startj <= endj and startj + 1 < n:\n\t\t\tUR += 1\n\t\t\tstarti -= 2\n\t\t\tstartj += 1\n\t\telse:\n\t\t\tUL += 1\n\t\t\tstarti -= 2\n\t\t\tstartj -= 1\n\telif startj < endj:\n\t\tR += endj - startj >> 1\n\t\tstartj = endj\n\telse:\n\t\tL += startj - endj >> 1\n\t\tstartj = endj\nans = []\nans += ['UL'] * UL\nans += ['UR'] * UR\nans += ['R'] * R\nans += ['LR'] * LR\nans += ['LL'] * LL\nans += ['L'] * L\nprint(len(ans))\nprint(*ans)\n", "import sys\nfrom heapq import *\n\ndef printShortestPath(n, i_start, j_start, i_end, j_end):\n\tmove_pref = {'UL': 1, 'UR': 2, 'R': 3, 'LR': 4, 'LL': 5, 'L': 6}\n\tvisited_nodes = []\n\tcost_to_go = {}\n\tprev_node = {}\n\tqueue = []\n\tcost_to_go[i_end, j_end] = 0\n\theappush(queue, [0, (i_end, j_end)])\n\tstart_reached = False\n\twhile queue and (not start_reached):\n\t\tcurrent_node = heappop(queue)\n\t\tcurrent_cost = current_node[0]\n\t\tcurrent_node = current_node[1]\n\t\tvisited_nodes.append(current_node)\n\t\tif current_node == (i_start, j_start):\n\t\t\tstart_reached = True\n\t\telse:\n\t\t\tneighbours = []\n\t\t\tif current_node[1] - 2 >= 0:\n\t\t\t\tneighbours.append([(current_node[0], current_node[1] - 2), 'R'])\n\t\t\tif current_node[1] + 2 < n:\n\t\t\t\tneighbours.append([(current_node[0], current_node[1] + 2), 'L'])\n\t\t\tif current_node[0] - 2 >= 0 and current_node[1] - 1 >= 0:\n\t\t\t\tneighbours.append([(current_node[0] - 2, current_node[1] - 1), 'LR'])\n\t\t\tif current_node[0] - 2 >= 0 and current_node[1] + 1 < n:\n\t\t\t\tneighbours.append([(current_node[0] - 2, current_node[1] + 1), 'LL'])\n\t\t\tif current_node[0] + 2 < n and current_node[1] - 1 >= 0:\n\t\t\t\tneighbours.append([(current_node[0] + 2, current_node[1] - 1), 'UR'])\n\t\t\tif current_node[0] + 2 < n and current_node[1] + 1 < n:\n\t\t\t\tneighbours.append([(current_node[0] + 2, current_node[1] + 1), 'UL'])\n\t\t\tfor neighb in neighbours:\n\t\t\t\tif neighb[0] not in visited_nodes:\n\t\t\t\t\tif neighb[0] not in cost_to_go:\n\t\t\t\t\t\tcost_to_go[neighb[0]] = current_cost + 1\n\t\t\t\t\t\theappush(queue, [current_cost + 1, neighb[0]])\n\t\t\t\t\t\tprev_node[neighb[0]] = [current_node, neighb[1]]\n\t\t\t\t\telif current_cost + 1 < cost_to_go[neighb[0]]:\n\t\t\t\t\t\tcost_to_go[neighb[0]] = current_cost + 1\n\t\t\t\t\t\theappush(queue, [current_cost + 1, neighb[0]])\n\t\t\t\t\t\tprev_node[neighb[0]] = [current_node, neighb[1]]\n\t\t\t\t\telif current_cost + 1 == cost_to_go[neighb[0]]:\n\t\t\t\t\t\tif move_pref[neighb[1]] < move_pref[prev_node[neighb[0]][1]]:\n\t\t\t\t\t\t\tprev_node[neighb[0]] = [current_node, neighb[1]]\n\tif not start_reached:\n\t\tprint('Impossible')\n\telse:\n\t\ton_node = (i_start, j_start)\n\t\tmoves = []\n\t\twhile on_node != (i_end, j_end):\n\t\t\tmoves.append(prev_node[on_node][1])\n\t\t\ton_node = prev_node[on_node][0]\n\t\tprint(len(moves))\n\t\tprint(' '.join(moves))\nn = int(input().strip())\n(i_start, j_start, i_end, j_end) = input().strip().split(' ')\n(i_start, j_start, i_end, j_end) = [int(i_start), int(j_start), int(i_end), int(j_end)]\nprintShortestPath(n, i_start, j_start, i_end, j_end)\n", "import sys\n\ndef onBoard(n, x, y):\n\treturn (x >= 0) & (x < n) & (y >= 0) & (y < n)\n\ndef BFS(n, board, leaves):\n\tnextLeaves = []\n\tmoves = [[-2, -1, 'UL'], [-2, 1, 'UR'], [0, 2, 'R'], [2, 1, 'LR'], [2, -1, 'LL'], [0, -2, 'L']]\n\tfor L in leaves:\n\t\t(x, y, path) = L\n\t\tfor M in moves:\n\t\t\t(dx, dy, step) = M\n\t\t\tif onBoard(n, x + dx, y + dy):\n\t\t\t\tif board[x + dx][y + dy] == 2:\n\t\t\t\t\treturn path + [step]\n\t\t\t\telif board[x + dx][y + dy] == 0:\n\t\t\t\t\tboard[x + dx][y + dy] = 1\n\t\t\t\t\te = [x + dx, y + dy, path + [step]]\n\t\t\t\t\tnextLeaves.append(e)\n\tif nextLeaves == []:\n\t\treturn 'Impossible'\n\telse:\n\t\treturn BFS(n, board, nextLeaves)\n\ndef printShortestPath(n, i_start, j_start, i_end, j_end):\n\tboard = []\n\tfor i in range(n):\n\t\tboard.append([0] * n)\n\tboard[i_start][j_start] = 1\n\tboard[i_end][j_end] = 2\n\tleaves = [[i_start, j_start, []]]\n\tp = BFS(n, board, leaves)\n\tif p == 'Impossible':\n\t\tprint(p)\n\telse:\n\t\tprint(len(p))\n\t\tprint(' '.join(p))\nn = int(input().strip())\n(i_start, j_start, i_end, j_end) = input().strip().split(' ')\n(i_start, j_start, i_end, j_end) = [int(i_start), int(j_start), int(i_end), int(j_end)]\nprintShortestPath(n, i_start, j_start, i_end, j_end)\n", "import sys\n\ndef printShortestPath(n, i_start, j_start, i_end, j_end):\n\tseen = set()\n\tqueue = [(0, i_start, j_start, [])]\n\twhile queue:\n\t\ttemp = []\n\t\twhile queue:\n\t\t\t(count, i, j, steps) = queue.pop()\n\t\t\tif i < 0 or i >= n or j < 0 or (j >= n):\n\t\t\t\tcontinue\n\t\t\tif (i, j) in seen:\n\t\t\t\tcontinue\n\t\t\tseen.add((i, j))\n\t\t\tif i == i_end and j == j_end:\n\t\t\t\tprint(count)\n\t\t\t\tprint(' '.join(steps))\n\t\t\t\treturn\n\t\t\tcount += 1\n\t\t\tnewsteps = steps[:]\n\t\t\tnewsteps.append('UL')\n\t\t\ttemp.append((count, i - 2, j - 1, newsteps))\n\t\t\tnewsteps = steps[:]\n\t\t\tnewsteps.append('UR')\n\t\t\ttemp.append((count, i - 2, j + 1, newsteps))\n\t\t\tnewsteps = steps[:]\n\t\t\tnewsteps.append('R')\n\t\t\ttemp.append((count, i, j + 2, newsteps))\n\t\t\tnewsteps = steps[:]\n\t\t\tnewsteps.append('LR')\n\t\t\ttemp.append((count, i + 2, j + 1, newsteps))\n\t\t\tnewsteps = steps[:]\n\t\t\tnewsteps.append('LL')\n\t\t\ttemp.append((count, i + 2, j - 1, newsteps))\n\t\t\tnewsteps = steps[:]\n\t\t\tnewsteps.append('L')\n\t\t\ttemp.append((count, i, j - 2, newsteps))\n\t\tqueue = list(reversed(temp))\n\tprint('Impossible')\nn = int(input().strip())\n(i_start, j_start, i_end, j_end) = input().strip().split(' ')\n(i_start, j_start, i_end, j_end) = [int(i_start), int(j_start), int(i_end), int(j_end)]\nprintShortestPath(n, i_start, j_start, i_end, j_end)\n", "import sys\n\nclass Move:\n\n\tdef __init__(self, next_i, next_j, move_name):\n\t\tself.pos_i = next_i\n\t\tself.pos_j = next_j\n\t\tself.move_name = move_name\n\n\tdef __repr__(self):\n\t\treturn '{}:{},{}'.format(self.move_name, self.pos_i, self.pos_j)\n\ndef printShortestPath(n, i_start, j_start, i_end, j_end):\n\tif not is_valid(n, i_start, j_start, i_end, j_end):\n\t\tprint('Impossible')\n\t\treturn\n\tresult = get_shortest_path(n, i_start, j_start, i_end, j_end)\n\tpriorities = {'UL': 1, 'UR': 2, 'R': 3, 'LR': 4, 'LL': 5, 'L': 6}\n\tresult = [(priorities[n], n) for n in result]\n\tresult.sort()\n\tresult = [n[1] for n in result]\n\tprint(len(result))\n\tprint(' '.join(result))\n\ndef UL(curr_i, curr_j, last_move=None):\n\treturn Move(curr_i - 2, curr_j - 1, 'UL')\n\ndef UR(curr_i, curr_j, last_move=None):\n\treturn Move(curr_i - 2, curr_j + 1, 'UR')\n\ndef R(curr_i, curr_j, last_move=None):\n\treturn Move(curr_i, curr_j + 2, 'R')\n\ndef LR(curr_i, curr_j, last_move=None):\n\treturn Move(curr_i + 2, curr_j + 1, 'LR')\n\ndef LL(curr_i, curr_j, last_move=None):\n\treturn Move(curr_i + 2, curr_j - 1, 'LL')\n\ndef L(curr_i, curr_j, last_move=None):\n\treturn Move(curr_i, curr_j - 2, 'L')\n\ndef in_bounds(move, n):\n\treturn 0 <= move.pos_i < n and 0 <= move.pos_j < n\n\ndef generate_valid_moves(curr_i, curr_j, n):\n\tmoves = [f(curr_i, curr_j) for f in [UL, UR, R, LR, LL, L]]\n\treturn [m for m in moves if in_bounds(m, n)]\n\ndef get_shortest_path(n, i_start, j_start, i_end, j_end):\n\tcurr_i = i_start\n\tcurr_j = j_start\n\tcurrent_distance = abs(i_end - curr_i) + abs(j_end - curr_j)\n\tpath = []\n\twhile current_distance != 0:\n\t\tnext_moves = [(abs(i_end - m.pos_i) + abs(j_end - m.pos_j), m) for m in generate_valid_moves(curr_i, curr_j, n)]\n\t\tmin_dist = next_moves[0][0]\n\t\tmin_move = next_moves[0][1]\n\t\tfor (dist, m) in next_moves:\n\t\t\tif dist < min_dist:\n\t\t\t\tmin_dist = dist\n\t\t\t\tmin_move = m\n\t\tcurrent_distance = min_dist\n\t\tpath.append(min_move.move_name)\n\t\tcurr_i = min_move.pos_i\n\t\tcurr_j = min_move.pos_j\n\treturn path\n\ndef is_valid(n, i_start, j_start, i_end, j_end):\n\tif abs(i_end - i_start) % 2 == 1:\n\t\treturn False\n\tif abs(i_end - i_start) % 4 == 0 and abs(j_end - j_start) % 2 == 0:\n\t\treturn True\n\tif abs(i_end - i_start) % 4 == 2 and abs(j_end - j_start) % 2 == 1:\n\t\treturn True\n\treturn False\nn = int(input().strip())\n(i_start, j_start, i_end, j_end) = input().strip().split(' ')\n(i_start, j_start, i_end, j_end) = [int(i_start), int(j_start), int(i_end), int(j_end)]\nprintShortestPath(n, i_start, j_start, i_end, j_end)\n", "import sys\n\ndef printShortestPath(n, ist, jst, ien, jen):\n\ts = []\n\ti = 1\n\tcount = 0\n\tflag = False\n\td = abs(ist - ien) + abs(jst - jen)\n\twhile d != 0 and i < 100000:\n\t\tk = [100000] * 6\n\t\td1 = d\n\t\tif jst - 1 >= 0 and ist - 2 >= 0:\n\t\t\tk[0] = abs(jst - 1 - jen) + abs(ist - 2 - ien)\n\t\tif jst + 1 < n and ist - 2 >= 0:\n\t\t\tk[1] = abs(jst + 1 - jen) + abs(ist - 2 - ien)\n\t\tif jst + 2 < n:\n\t\t\tk[2] = abs(jst + 2 - jen) + abs(ist - ien)\n\t\tif jst + 1 < n and ist + 2 < n:\n\t\t\tk[3] = abs(jst + 1 - jen) + abs(ist + 2 - ien)\n\t\tif jst - 1 >= 0 and ist + 2 < n:\n\t\t\tk[4] = abs(jst - 1 - jen) + abs(ist + 2 - ien)\n\t\tif jst - 2 >= 0:\n\t\t\tk[5] = abs(jst - 2 - jen) + abs(ist - ien)\n\t\tl = min(k)\n\t\tif l == k[0]:\n\t\t\tcount += 1\n\t\t\tjst = jst - 1\n\t\t\tist = ist - 2\n\t\t\ts.append(0)\n\t\telif l == k[1]:\n\t\t\tcount += 1\n\t\t\tjst = jst + 1\n\t\t\tist = ist - 2\n\t\t\ts.append(1)\n\t\telif l == k[2]:\n\t\t\tcount += 1\n\t\t\tjst = jst + 2\n\t\t\ts.append(2)\n\t\telif l == k[3]:\n\t\t\tcount += 1\n\t\t\tjst = jst + 1\n\t\t\tist = ist + 2\n\t\t\ts.append(3)\n\t\telif l == k[4]:\n\t\t\tcount += 1\n\t\t\tjst = jst - 1\n\t\t\tist = ist + 2\n\t\t\ts.append(4)\n\t\telif l == k[5]:\n\t\t\tcount += 1\n\t\t\tjst = jst - 2\n\t\t\ts.append(5)\n\t\td = abs(ist - ien) + abs(jst - jen)\n\t\ti += 1\n\t\tif d1 < d:\n\t\t\tflag = True\n\t\t\tbreak\n\ts.sort()\n\tfor i in range(len(s)):\n\t\tif s[i] == 0:\n\t\t\ts[i] = 'UL'\n\t\telif s[i] == 1:\n\t\t\ts[i] = 'UR'\n\t\telif s[i] == 2:\n\t\t\ts[i] = 'R'\n\t\telif s[i] == 3:\n\t\t\ts[i] = 'LR'\n\t\telif s[i] == 4:\n\t\t\ts[i] = 'LL'\n\t\telse:\n\t\t\ts[i] = 'L'\n\tif flag == True or d != 0:\n\t\tprint('Impossible')\n\telif d == 0:\n\t\tprint(count)\n\t\tprint(*s)\nn = int(input().strip())\n(i_start, j_start, i_end, j_end) = input().strip().split(' ')\n(i_start, j_start, i_end, j_end) = [int(i_start), int(j_start), int(i_end), int(j_end)]\nprintShortestPath(n, i_start, j_start, i_end, j_end)\n", "import math\ndim = int(input())\n(sJ, sI, eJ, eI) = map(int, input().split())\nbot = (sI, sJ)\npoint = (eI, eJ)\narr = [(-1, 2), (1, 2), (-2, 0), (2, 0), (-1, -2), (1, -2)]\nvalues = ['LL', 'LR', 'L', 'R', 'UL', 'UR']\nmoves = list(zip(values, arr))\nprior = dict(zip(['UL', 'UR', 'R', 'LR', 'LL', 'L'], list(range(1, 7))))\nordering = []\n\ndef manhattan(bot, point):\n\treturn math.sqrt((bot[0] - point[0]) ** 2 + (bot[1] - point[1]) ** 2)\n\ndef optim(arr):\n\ttemp = {}\n\tfor i in arr:\n\t\ttry:\n\t\t\tx = (bot[0] + i[1][0], bot[1] + i[1][1])\n\t\t\ttemp[i[0]] = x\n\t\texcept:\n\t\t\tpass\n\toptimumValue = min((manhattan(temp[k], point) for k in temp))\n\tpriority = {i: j for (i, j) in temp.items() if manhattan(j, point) == optimumValue}\n\tval = min(priority, key=lambda k: prior[k])\n\treturn (val, temp[val])\nrepeats = set()\nflag = False\nwhile bot != point:\n\t(val, bot) = optim(moves)\n\tordering.append(val)\n\tif bot not in repeats:\n\t\trepeats.add(bot)\n\telse:\n\t\tflag = True\n\t\tbreak\nif flag:\n\tprint('Impossible')\nelse:\n\tprint(len(ordering))\n\toutput = sorted(ordering, key=lambda k: prior[k])\n\tprint(*output)\n", "import sys\n\ndef printShortestPath(n, i_start, j_start, i_end, j_end):\n\tmoves = 0\n\tres = []\n\tif (i_end - i_start) % 2 != 0:\n\t\tprint('Impossible')\n\t\treturn res\n\telse:\n\t\titurns = int((i_end - i_start) / 2)\n\t\tif (abs(j_end - j_start) - abs(iturns)) % 2 != 0:\n\t\t\tprint('Impossible')\n\t\t\treturn res\n\t\telse:\n\t\t\ti_curr = i_start\n\t\t\tj_curr = j_start\n\t\t\twhile i_curr != i_end or j_curr != j_end:\n\t\t\t\tmoves += 1\n\t\t\t\tif i_curr > i_end:\n\t\t\t\t\ti_curr -= 2\n\t\t\t\t\tif j_curr >= j_end - int((i_curr - i_end) / 2 - 1) and j_curr > 0:\n\t\t\t\t\t\tres.append('UL')\n\t\t\t\t\t\tj_curr -= 1\n\t\t\t\t\telse:\n\t\t\t\t\t\tres.append('UR')\n\t\t\t\t\t\tj_curr += 1\n\t\t\t\telif i_curr <= i_end and j_curr < j_end - 1 - int((i_end - i_curr) / 2):\n\t\t\t\t\tj_curr += 2\n\t\t\t\t\tres.append('R')\n\t\t\t\telif i_curr < i_end:\n\t\t\t\t\ti_curr += 2\n\t\t\t\t\tif j_curr <= j_end + int((i_end - i_curr) / 2) and j_curr < n - 1:\n\t\t\t\t\t\tres.append('LR')\n\t\t\t\t\t\tj_curr += 1\n\t\t\t\t\telse:\n\t\t\t\t\t\tres.append('LL')\n\t\t\t\t\t\tj_curr -= 1\n\t\t\t\telse:\n\t\t\t\t\tj_curr -= 2\n\t\t\t\t\tres.append('L')\n\t\t\tprint(moves)\n\t\t\tprint(' '.join(res))\n\t\t\treturn res\nn = int(input().strip())\n(i_start, j_start, i_end, j_end) = input().strip().split(' ')\n(i_start, j_start, i_end, j_end) = [int(i_start), int(j_start), int(i_end), int(j_end)]\nprintShortestPath(n, i_start, j_start, i_end, j_end)\n", "from collections import deque, namedtuple\nPoint = namedtuple('Point', ['x', 'y'])\nPath = namedtuple('Path', ['point', 'moves'])\nMOVES = (('UL', Point(-1, -2)), ('UR', Point(1, -2)), ('R', Point(2, 0)), ('LR', Point(1, 2)), ('LL', Point(-1, 2)), ('L', Point(-2, 0)))\n\ndef valid_moves(size, start):\n\tvalid = []\n\tfor (name, move) in MOVES:\n\t\tcurrent = Point(start.x + move.x, start.y + move.y)\n\t\tif min(current.x, current.y) >= 0 and max(current.x, current.y) < size:\n\t\t\tvalid.append((name, current))\n\treturn valid\n\ndef find_shortest(size, start_y, start_x, end_y, end_x):\n\troutes = deque()\n\tvisited = {}\n\ttarget = Point(end_x, end_y)\n\tcurrent = Path(Point(start_x, start_y), [])\n\twhile current.point != target:\n\t\tfor (move, point) in valid_moves(size, current.point):\n\t\t\tprevious = visited.get(point)\n\t\t\tif not previous or len(current.moves) < previous:\n\t\t\t\troutes.append(Path(point, current.moves + [move]))\n\t\t\t\tvisited[point] = len(current.moves)\n\t\tif not routes:\n\t\t\treturn\n\t\tcurrent = routes.popleft()\n\treturn current.moves\n\ndef printShortestPath(size, start_y, start_x, end_y, end_x):\n\tpath = find_shortest(size, start_y, start_x, end_y, end_x)\n\tif not path:\n\t\tprint('Impossible')\n\telse:\n\t\tprint(len(path))\n\t\tprint(' '.join(path))\nn = int(input().strip())\n(i_start, j_start, i_end, j_end) = input().strip().split(' ')\n(i_start, j_start, i_end, j_end) = [int(i_start), int(j_start), int(i_end), int(j_end)]\nprintShortestPath(n, i_start, j_start, i_end, j_end)\n", "import sys\nn = int(input().strip())\ntable = [[-1 for _ in range(n + 1)] for _ in range(n + 1)]\n(i_start, j_start, i_end, j_end) = input().strip().split(' ')\n(i_start, j_start, i_end, j_end) = [int(i_start) + 1, int(j_start) + 1, int(i_end) + 1, int(j_end) + 1]\nn = 21\nmid = n // 2 + 1\ndiffx = mid - i_start\ndiffy = mid - j_start\ni = mid\nj = mid\nendi = i_end + diffx\nendj = j_end + diffy\nans = 0\nrb_diagonal = []\nif endi % 2 == 0 or (endi % 2 != 0 and (endi - 1) % 4 == 0 and (endj % 2 != 0)) or (endi % 2 != 0 and (endi - 1) % 4 != 0 and (endj % 2 == 0)):\n\tprint('Impossible')\nelif i == endi and j == endj:\n\tprint(0)\nelif i == endi and j != endj:\n\tif endj > j:\n\t\tans = abs(endj - j) // 2\n\t\tprint(ans)\n\t\tprint('R ' * ans)\n\telse:\n\t\tans = abs(j - endj) // 2\n\t\tprint(ans)\n\t\tprint('L ' * ans)\nelif i != endi and j == endj:\n\tif i > endi:\n\t\tans = abs(i - endi) // 4\n\t\tprint(2 * ans)\n\t\tprint('UL UR ' * ans)\n\telse:\n\t\tans = abs(endi - i) // 4\n\t\tprint(2 * ans)\n\t\tprint('LR LL ' * ans)\nelif endi < i and endj < j:\n\tStr = ''\n\trdiff = abs(i - endi)\n\tN_ul = rdiff // 2\n\tans += N_ul\n\tcnew = abs(j - N_ul)\n\tStr += 'UL ' * N_ul\n\tif cnew >= endj:\n\t\tcdiff = abs(cnew - endj)\n\t\tN_l = cdiff // 2\n\t\tans += N_l\n\t\tStr += 'L ' * N_l\n\t\tprint(ans)\n\t\tprint(Str)\n\telse:\n\t\tcdiff = abs(endj - cnew)\n\t\tN_r = cdiff // 2\n\t\tans += N_r\n\t\tStr += 'L ' * N_r\n\t\tprint(ans)\n\t\tprint(Str)\nelif endi < i and endj > j:\n\tStr = ''\n\trdiff = abs(i - endi)\n\tN_ur = rdiff // 2\n\tans += N_ur\n\tcnew = i + N_ur\n\tStr += 'UR ' * N_ur\n\tif cnew >= endj:\n\t\tcdiff = abs(cnew - endj)\n\t\tN_l = cdiff // 2\n\t\tans += N_l\n\t\tStr += 'L ' * N_l\n\t\tprint(ans)\n\t\tprint(Str)\n\telse:\n\t\tcdiff = abs(endj - cnew)\n\t\tN_r = cdiff // 2\n\t\tans += N_r\n\t\tStr += 'R ' * N_r\n\t\tprint(ans)\n\t\tprint(Str)\nelif endi > i and endj < j:\n\tif (endi - i) // 2 > j - endj:\n\t\tti = endi\n\t\ttj = endj\n\t\tcount = 0\n\t\twhile (ti - i) // 2 != tj - j:\n\t\t\tcount += 1\n\t\t\tti -= 2\n\t\t\ttj += 1\n\t\tStr = ''\n\t\tN_lr = (ti - i) // 2\n\t\tN_ll = count\n\t\tStr += 'LR ' * N_lr\n\t\tStr += 'LL ' * N_ll\n\t\tans += N_lr + N_ll\n\t\tprint(ans)\n\t\tprint(Str)\n\telse:\n\t\trdiff = abs(endi - i)\n\t\tN_ll = rdiff // 2\n\t\tans += N_ll\n\t\tcnew = abs(j - N_ll)\n\t\tStr += 'LL ' * N_ll\n\t\tif cnew >= endj:\n\t\t\tcdiff = abs(cnew - endj)\n\t\t\tN_l = cdiff // 2\n\t\t\tStr += 'L ' * N_l\n\t\t\tans += N_l\n\t\t\tprint(ans)\n\t\t\tprint(Str)\n\t\telse:\n\t\t\tcdiff = abs(endj - cnew)\n\t\t\tN_r = cdiff // 2\n\t\t\tStr += 'R ' * N_r\n\t\t\tans += N_r\n\t\t\tprint(ans)\n\t\t\tprint(Str)\nelif (endi - i) // 2 > endj - j:\n\tStr = ''\n\tcount = 0\n\tti = endi\n\ttj = endj\n\twhile (ti - i) // 2 != tj - j:\n\t\tcount += 1\n\t\tti -= 2\n\t\ttj += 1\n\tN_lr = (ti - i) // 2\n\tN_ll = count\n\tStr += 'LR ' * N_lr\n\tStr += 'LL ' * N_ll\n\tans += N_lr + N_ll\n\tprint(ans)\n\tprint(Str)\nelse:\n\trdiff = abs(endi - i)\n\tN_lr = rdiff // 2\n\tcnew = j + N_lr\n\tStr = ''\n\tans += N_lr\n\tcdiff = abs(cnew - endj)\n\tN_r = cdiff // 2\n\tStr += 'R ' * N_r\n\tStr += 'LR ' * N_lr\n\tans += N_r\n\tprint(ans)\n\tprint(Str)\n", "import sys\n\ndef options(n, tup):\n\toptions = []\n\ti = tup[0]\n\tj = tup[1]\n\tif i - 2 >= 0:\n\t\tif j - 1 >= 0:\n\t\t\toptions.append((i - 2, j - 1))\n\t\tif j + 1 < n:\n\t\t\toptions.append((i - 2, j + 1))\n\tif j + 2 < n:\n\t\toptions.append((i, j + 2))\n\tif i + 2 < n:\n\t\tif j + 1 < n:\n\t\t\toptions.append((i + 2, j + 1))\n\t\tif j - 1 >= 0:\n\t\t\toptions.append((i + 2, j - 1))\n\tif j - 2 >= 0:\n\t\toptions.append((i, j - 2))\n\treturn options\n\ndef whatMove(cur, prev):\n\tdi = cur[0] - prev[0]\n\tdj = cur[1] - prev[1]\n\tif di == 0:\n\t\tif dj == -2:\n\t\t\treturn 'L'\n\t\tif dj == 2:\n\t\t\treturn 'R'\n\tif di == -2:\n\t\tif dj == -1:\n\t\t\treturn 'UL'\n\t\tif dj == 1:\n\t\t\treturn 'UR'\n\tif di == 2:\n\t\tif dj == -1:\n\t\t\treturn 'LL'\n\t\tif dj == 1:\n\t\t\treturn 'LR'\n\ndef printShortestPath(n, i_start, j_start, i_end, j_end):\n\tprev = {}\n\tvisited = []\n\tqueue = [(i_start, j_start)]\n\twhile queue:\n\t\tcurrent = queue.pop(0)\n\t\tvisited.append(current)\n\t\tif current == (i_end, j_end):\n\t\t\tpath = []\n\t\t\twhile current != (i_start, j_start):\n\t\t\t\tparent = prev[current]\n\t\t\t\tpath.append(whatMove(current, parent))\n\t\t\t\tcurrent = parent\n\t\t\tprint(len(path))\n\t\t\tpath.reverse()\n\t\t\tprint(*path)\n\t\t\treturn\n\t\tfor option in options(n, current):\n\t\t\tif option not in visited and option not in queue:\n\t\t\t\tprev[option] = current\n\t\t\t\tqueue.append(option)\n\tprint('Impossible')\nn = int(input().strip())\n(i_start, j_start, i_end, j_end) = input().strip().split(' ')\n(i_start, j_start, i_end, j_end) = [int(i_start), int(j_start), int(i_end), int(j_end)]\nprintShortestPath(n, i_start, j_start, i_end, j_end)\n", "import sys\n\ndef printShortestPath(n, i_start, j_start, i_end, j_end):\n\tq = []\n\tv = [i_start, j_start]\n\tq.append(v)\n\twhile len(q) > 0:\n\t\tcv = q.pop(0)\n\t\tnd = chess[cv[0]][cv[1]] + 1\n\t\tsi = cv[0]\n\t\tsj = cv[1]\n\t\tpossibleN = [[si - 2, sj - 1], [si - 2, sj + 1], [si, sj + 2], [si + 2, sj + 1], [si + 2, sj - 1], [si, sj - 2]]\n\t\tfor (mov, nei) in enumerate(possibleN, 1):\n\t\t\tii = nei[0]\n\t\t\tjj = nei[1]\n\t\t\tif ii < 0 or ii > n - 1 or jj < 0 or (jj > n - 1):\n\t\t\t\tcontinue\n\t\t\telif chess[ii][jj] != 0:\n\t\t\t\tcontinue\n\t\t\telse:\n\t\t\t\tchess[ii][jj] = nd\n\t\t\t\tpre[ii][jj] = cv\n\t\t\t\tchoices[ii][jj] = mov\n\t\t\t\tq.append(nei)\n\t\t\t\tif cv == [i_end, j_end]:\n\t\t\t\t\treturn 0\n\treturn 0\nn = int(input().strip())\n(i_start, j_start, i_end, j_end) = input().strip().split(' ')\n(i_start, j_start, i_end, j_end) = [int(i_start), int(j_start), int(i_end), int(j_end)]\nchess = [[0 for i in range(n)] for j in range(n)]\npre = [[None for i in range(n)] for j in range(n)]\nchoices = [[0 for i in range(n)] for j in range(n)]\nprintShortestPath(n, i_start, j_start, i_end, j_end)\nspath = chess[i_end][j_end]\ndicto = {1: 'UL', 2: 'UR', 3: 'R', 4: 'LR', 5: 'LL', 6: 'L'}\nres = []\nif spath <= 0:\n\tprint('Impossible')\nelse:\n\tprint(spath)\n\tfor i in range(spath):\n\t\tflag = choices[i_end][j_end]\n\t\tres.append(dicto[flag])\n\t\t(i_end, j_end) = pre[i_end][j_end]\n\tfor j in range(len(res) - 1, -1, -1):\n\t\tprint(res[j], end=' ')\n", "import sys\n\ndef printShortestPath(n, i_start, j_start, i_end, j_end):\n\n\tdef is_valid(p):\n\t\tif 0 <= p[0] < n and 0 <= p[1] < n:\n\t\t\treturn True\n\t\treturn False\n\tfrom collections import deque\n\tB = [[-1] * n for _ in range(n)]\n\tq = deque()\n\tstart = (i_start, j_start)\n\tq.append(start)\n\tB[i_start][j_start] = -2\n\tmoves = [(-2, -1), (-2, 1), (0, 2), (2, 1), (2, -1), (0, -2)]\n\tmoves_str = ['UL', 'UR', 'R', 'LR', 'LL', 'L']\n\twhile q:\n\t\tp = q.popleft()\n\t\tfor (i, move) in enumerate(moves):\n\t\t\tnew_p = (p[0] + move[0], p[1] + move[1])\n\t\t\tif is_valid(new_p) and B[new_p[0]][new_p[1]] == -1:\n\t\t\t\tB[new_p[0]][new_p[1]] = i\n\t\t\t\tif new_p == (i_end, j_end):\n\t\t\t\t\tq = []\n\t\t\t\t\tbreak\n\t\t\t\tq.append(new_p)\n\tif B[i_end][j_end] != -1:\n\t\t(i, j) = (i_end, j_end)\n\t\tresults = []\n\t\twhile i != i_start or j != j_start:\n\t\t\tidx = B[i][j]\n\t\t\tresults.append(moves_str[idx])\n\t\t\ti -= moves[idx][0]\n\t\t\tj -= moves[idx][1]\n\t\tprint(len(results))\n\t\tresults.reverse()\n\t\tprint(' '.join(results))\n\telse:\n\t\tprint('Impossible')\nn = int(input().strip())\n(i_start, j_start, i_end, j_end) = input().strip().split(' ')\n(i_start, j_start, i_end, j_end) = [int(i_start), int(j_start), int(i_end), int(j_end)]\nprintShortestPath(n, i_start, j_start, i_end, j_end)\n", "import sys\nfrom collections import deque\n\ndef printShortestPath(n, i_start, j_start, i_end, j_end):\n\tassert 5 <= n <= 200\n\tassert (i_start, j_start) != (i_end, j_end)\n\t(is_reachable, directions) = find_path(n, i_start, j_start, i_end, j_end)\n\tif is_reachable:\n\t\tprint(len(directions))\n\t\tprint(*directions, sep=' ')\n\telse:\n\t\tprint('Impossible')\n\ndef find_path(n, i_s, j_s, i_e, j_e):\n\tis_reachable = False\n\t(ci, cj) = (i_s, j_s)\n\tparent = [[None for _ in range(n)] for _ in range(n)]\n\tparent[ci][cj] = (ci, cj)\n\tq = deque()\n\tq.append((ci, cj))\n\twhile q:\n\t\t(ci, cj) = q.popleft()\n\t\tif (ci, cj) == (i_e, j_e):\n\t\t\tis_reachable = True\n\t\t\tbreak\n\t\tfor (ni, nj) in next_moves(n, ci, cj):\n\t\t\tif parent[ni][nj]:\n\t\t\t\tcontinue\n\t\t\tparent[ni][nj] = (ci, cj)\n\t\t\tq.append((ni, nj))\n\tif is_reachable:\n\t\treturn (True, conf_path(parent, n, i_s, j_s, i_e, j_e))\n\telse:\n\t\treturn (False, [])\n\ndef next_moves(n, i, j):\n\tdidjs = [(-2, -1), (-2, 1), (0, 2), (2, 1), (2, -1), (0, -2)]\n\tfor (di, dj) in didjs:\n\t\t(ni, nj) = (i + di, j + dj)\n\t\tif 0 <= ni < n and 0 <= nj < n:\n\t\t\tyield (ni, nj)\n\ndef conf_path(parent, n, i_s, j_s, i_e, j_e):\n\tassert parent[i_s][j_s] == (i_s, j_s)\n\tassert parent[i_e][j_e] != None\n\t(i, j) = (i_e, j_e)\n\tstack = []\n\twhile (i, j) != (i_s, j_s):\n\t\tstack.append((i, j))\n\t\t(i, j) = parent[i][j]\n\tassert (i, j) == (i_s, j_s)\n\tstack.append((i_s, j_s))\n\tdidjs = {(-2, 1): 'UR', (0, 2): 'R', (2, 1): 'LR', (2, -1): 'LL', (0, -2): 'L', (-2, -1): 'UL'}\n\tdirections = []\n\tnodes = stack[::-1]\n\tfor x in range(len(nodes) - 1):\n\t\t((ai, aj), (bi, bj)) = (nodes[x], nodes[x + 1])\n\t\tdirection = didjs[bi - ai, bj - aj]\n\t\tdirections.append(direction)\n\treturn directions\nn = int(input().strip())\n(i_start, j_start, i_end, j_end) = input().strip().split(' ')\n(i_start, j_start, i_end, j_end) = [int(i_start), int(j_start), int(i_end), int(j_end)]\nprintShortestPath(n, i_start, j_start, i_end, j_end)\n", "import sys\nimport math\nmoveset_dict = {(-2, -1): 'UL', (-2, 1): 'UR', (0, 2): 'R', (2, 1): 'LR', (2, -1): 'LL', (0, -2): 'L'}\nmoveset = [(-2, -1), (-2, 1), (0, 2), (2, 1), (2, -1), (0, -2)]\n\ndef printShortestPath(n, i_start, j_start, i_end, j_end):\n\tmatrix = [[() for c in range(n)] for r in range(n)]\n\tqueue = [(i_start, j_start)]\n\twhile queue:\n\t\t(r_pos, c_pos) = queue.pop(0)\n\t\tmoves = get_moves(r_pos, c_pos)\n\t\tfor move in moves:\n\t\t\t(add_r, add_c) = move\n\t\t\t(new_r, new_c) = (r_pos + add_r, c_pos + add_c)\n\t\t\tif not matrix[new_r][new_c]:\n\t\t\t\tqueue.append((new_r, new_c))\n\t\t\t\tmatrix[new_r][new_c] = move\n\tto_prev = matrix[i_end][j_end]\n\tif not to_prev:\n\t\tprint('Impossible')\n\telse:\n\t\tnum_moves = 0\n\t\tpath = ''\n\t\tr = i_end\n\t\tc = j_end\n\t\twhile r != i_start or c != j_start:\n\t\t\tmove = moveset_dict[to_prev]\n\t\t\tpath = move + ' ' + path\n\t\t\tr -= to_prev[0]\n\t\t\tc -= to_prev[1]\n\t\t\tto_prev = matrix[r][c]\n\t\t\tnum_moves += 1\n\t\tprint(num_moves)\n\t\tprint(path[:-1])\n\ndef get_moves(r_pos, c_pos):\n\tmoves = []\n\tfor move in moveset:\n\t\tif 0 <= r_pos + move[0] < n and 0 <= c_pos + move[1] < n:\n\t\t\tmoves.append(move)\n\treturn moves\nn = int(input().strip())\n(i_start, j_start, i_end, j_end) = input().strip().split(' ')\n(i_start, j_start, i_end, j_end) = [int(i_start), int(j_start), int(i_end), int(j_end)]\nprintShortestPath(n, i_start, j_start, i_end, j_end)\n", "import sys\nmove = []\nmy_own_order = ['UL', 'UR', 'R', 'LR', 'LL', 'L']\norder = {key: i for (i, key) in enumerate(my_own_order)}\n\ndef printShortestPath(n, i_start, j_start, i_end, j_end):\n\tdiff_i = i_end - i_start\n\tdiff_j = j_end - j_start\n\tif diff_i == 0 and diff_j == 0:\n\t\tprint(len(move))\n\t\tprint(' '.join(sorted(move, key=lambda d: order[d])))\n\t\treturn\n\tif diff_i % 2 != 0:\n\t\tprint('Impossible')\n\t\treturn\n\telif diff_i < 0:\n\t\tif diff_j <= 0:\n\t\t\tmove.append('UL')\n\t\t\tprintShortestPath(n, i_start - 2, j_start - 1, i_end, j_end)\n\t\tif diff_j > 0:\n\t\t\tmove.append('UR')\n\t\t\tprintShortestPath(n, i_start - 2, j_start + 1, i_end, j_end)\n\telif diff_i > 0:\n\t\tif diff_j < 0:\n\t\t\tmove.append('LL')\n\t\t\tprintShortestPath(n, i_start + 2, j_start - 1, i_end, j_end)\n\t\tif diff_j >= 0:\n\t\t\tmove.append('LR')\n\t\t\tprintShortestPath(n, i_start + 2, j_start + 1, i_end, j_end)\n\telif diff_i == 0:\n\t\tif diff_j % 2 != 0:\n\t\t\tprint('Impossible')\n\t\t\treturn\n\t\telif diff_j > 0:\n\t\t\tmove.append('R')\n\t\t\tprintShortestPath(n, i_start, j_start + 2, i_end, j_end)\n\t\telif diff_j < 0:\n\t\t\tmove.append('L')\n\t\t\tprintShortestPath(n, i_start, j_start - 2, i_end, j_end)\nn = int(input().strip())\n(i_start, j_start, i_end, j_end) = input().strip().split(' ')\n(i_start, j_start, i_end, j_end) = [int(i_start), int(j_start), int(i_end), int(j_end)]\nprintShortestPath(n, i_start, j_start, i_end, j_end)\n", "import sys\n\ndef printShortestPath(n, i_start, j_start, i_end, j_end):\n\tx = j_end - j_start\n\ty = i_end - i_start\n\tsteps = []\n\tif y % 2 == 1:\n\t\tprint('Impossible')\n\t\treturn\n\twhile y != 0:\n\t\tif y < 0:\n\t\t\ty += 2\n\t\t\tif x <= 0:\n\t\t\t\tx += 1\n\t\t\t\tsteps.append('UL')\n\t\t\telse:\n\t\t\t\tx -= 1\n\t\t\t\tsteps.append('UR')\n\t\telse:\n\t\t\ty -= 2\n\t\t\tif x <= 0:\n\t\t\t\tx += 1\n\t\t\t\tsteps.append('LL')\n\t\t\telse:\n\t\t\t\tx -= 1\n\t\t\t\tsteps.append('LR')\n\tif x % 2 == 1:\n\t\tprint('Impossible')\n\t\treturn\n\twhile x != 0:\n\t\tif x >= 0:\n\t\t\tx -= 2\n\t\t\tsteps.append('R')\n\t\telse:\n\t\t\tx += 2\n\t\t\tsteps.append('L')\n\tmyorder = ['UL', 'UR', 'R', 'LR', 'LL', 'L']\n\tsteps.sort(key=lambda v: myorder.index(v))\n\tprint(len(steps))\n\tprint(' '.join(steps))\nn = int(input().strip())\n(i_start, j_start, i_end, j_end) = input().strip().split(' ')\n(i_start, j_start, i_end, j_end) = [int(i_start), int(j_start), int(i_end), int(j_end)]\nprintShortestPath(n, i_start, j_start, i_end, j_end)\n", "import sys\narr = [[-1, 2], [1, 2], [2, 0], [1, -2], [-1, -2], [0, -2]]\n\ndef printShortestPath(n1, i_start, j_start, i_end, j_end):\n\tx = j_end - j_start\n\ty = i_end - i_start\n\tst = ''\n\tn = 0\n\tc1 = 0\n\tc2 = 0\n\tc3 = 0\n\tc4 = 0\n\tr = 0\n\tflag = 0\n\twhile (x != 0 or y != 0) and flag == 0:\n\t\twhile x > 0 and flag == 0:\n\t\t\tif y > 0:\n\t\t\t\tc1 = 1\n\t\t\t\tst += 'LR '\n\t\t\t\ty -= 2\n\t\t\t\tx -= 1\n\t\t\t\tj_start += 1\n\t\t\t\ti_start += 2\n\t\t\t\tif j_start >= n1 or i_start >= n1 or j_start < 0 or (i_start < 0):\n\t\t\t\t\tflag = 1\n\t\t\t\t\tbreak\n\t\t\t\tn += 1\n\t\t\t\tif y < 0 or y == 1:\n\t\t\t\t\tflag = 1\n\t\t\t\t\tbreak\n\t\t\t\tif x == 0 and y == 0:\n\t\t\t\t\tbreak\n\t\t\telif y == 0:\n\t\t\t\tif x % 2 == 0:\n\t\t\t\t\tif c1 == 1:\n\t\t\t\t\t\tst = 'R ' + st\n\t\t\t\t\telse:\n\t\t\t\t\t\tst += 'R '\n\t\t\t\t\tx = x - 2\n\t\t\t\t\tj_start += 2\n\t\t\t\t\tif j_start >= n1 or i_start >= n1 or j_start < 0 or (i_start < 0):\n\t\t\t\t\t\tflag = 1\n\t\t\t\t\t\tbreak\n\t\t\t\t\tn += 1\n\t\t\t\telse:\n\t\t\t\t\tflag = 1\n\t\t\t\t\tbreak\n\t\t\telif y + 2 > 0:\n\t\t\t\tflag = 1\n\t\t\t\tbreak\n\t\t\telse:\n\t\t\t\ty += 2\n\t\t\t\tx -= 1\n\t\t\t\tst += 'UR '\n\t\t\t\tr = 1\n\t\t\t\tn += 1\n\t\t\t\tj_start += 1\n\t\t\t\ti_start -= 2\n\t\t\t\tif j_start >= n1 or i_start >= n1 or j_start < 0 or (i_start < 0):\n\t\t\t\t\tflag = 1\n\t\t\t\t\tbreak\n\t\t\t\tif y > 0:\n\t\t\t\t\tflag = 1\n\t\t\t\t\tbreak\n\t\twhile x < 0 and flag == 0:\n\t\t\tif y > 0:\n\t\t\t\tst += 'LL '\n\t\t\t\ty -= 2\n\t\t\t\tx += 1\n\t\t\t\tc2 = 1\n\t\t\t\tn += 1\n\t\t\t\tj_start -= 1\n\t\t\t\ti_start += 2\n\t\t\t\tif j_start >= n1 or i_start >= n1 or j_start < 0 or (i_start < 0):\n\t\t\t\t\tflag = 1\n\t\t\t\t\tbreak\n\t\t\t\tif y < 0:\n\t\t\t\t\tflag = 1\n\t\t\t\t\tbreak\n\t\t\t\tif x == 0 and y == 0:\n\t\t\t\t\tbreak\n\t\t\telif y == 0:\n\t\t\t\twhile x < 0 and abs(x) % 2 == 0:\n\t\t\t\t\tst += 'L '\n\t\t\t\t\tx = x + 2\n\t\t\t\t\tj_start -= 2\n\t\t\t\t\tif j_start >= n1 or i_start >= n1 or j_start < 0 or (i_start < 0):\n\t\t\t\t\t\tflag = 1\n\t\t\t\t\t\tbreak\n\t\t\t\t\tn += 1\n\t\t\t\tif x != 0:\n\t\t\t\t\tflag = 1\n\t\t\t\t\tbreak\n\t\t\telse:\n\t\t\t\ty += 2\n\t\t\t\tx += 1\n\t\t\t\tst += 'UL '\n\t\t\t\tn += 1\n\t\t\t\tj_start -= 1\n\t\t\t\ti_start -= 2\n\t\t\t\tif j_start >= n1 or i_start >= n1 or j_start < 0 or (i_start < 0):\n\t\t\t\t\tflag = 1\n\t\t\t\t\tbreak\n\t\t\t\tif y > 0:\n\t\t\t\t\tflag = 1\n\t\t\t\t\tbreak\n\t\twhile x == 0 and flag == 0:\n\t\t\tif y > 0:\n\t\t\t\tif y % 4 == 0:\n\t\t\t\t\ty -= 4\n\t\t\t\t\tif c2 == 0 and c4 == 0:\n\t\t\t\t\t\tst += 'LR LL '\n\t\t\t\t\t\tc4 = 1\n\t\t\t\t\telif c2 == 0 and c4 == 1:\n\t\t\t\t\t\tst = 'LR ' + st + 'LL '\n\t\t\t\t\telse:\n\t\t\t\t\t\tst = 'LR LL ' + st\n\t\t\t\t\tn += 2\n\t\t\t\t\ti_start += 4\n\t\t\t\t\tif j_start >= n1 or i_start >= n1 or j_start < 0 or (i_start < 0):\n\t\t\t\t\t\tflag = 1\n\t\t\t\t\t\tbreak\n\t\t\t\telse:\n\t\t\t\t\tflag = 1\n\t\t\t\t\tbreak\n\t\t\telif y == 0:\n\t\t\t\tbreak\n\t\t\telif abs(y) % 4 == 0:\n\t\t\t\tif r == 0 and c3 == 0:\n\t\t\t\t\tst += 'UL UR '\n\t\t\t\t\tc3 = 1\n\t\t\t\telif r == 0 and c3 == 1:\n\t\t\t\t\tst = 'UL ' + st + 'UR '\n\t\t\t\telse:\n\t\t\t\t\tst = 'UL UR ' + st\n\t\t\t\ty += 4\n\t\t\t\tn += 2\n\t\t\t\ti_start -= 4\n\t\t\t\tif j_start >= n1 or i_start >= n1 or j_start < 0 or (i_start < 0):\n\t\t\t\t\tflag = 1\n\t\t\t\t\tbreak\n\t\t\t\tif y > 0:\n\t\t\t\t\tflag = 1\n\t\t\t\t\tbreak\n\t\t\telse:\n\t\t\t\tflag = 1\n\t\t\t\tbreak\n\tif flag == 0:\n\t\tprint(n)\n\t\tl = st.strip().split(' ')\n\t\torder = {'UL': 1, 'UR': 2, 'R': 3, 'LR': 4, 'LL': 5, 'L': 6}\n\t\torder_rev = {1: 'UL', 2: 'UR', 3: 'R', 4: 'LR', 5: 'LL', 6: 'L'}\n\t\tst2 = []\n\t\tfor i in l:\n\t\t\tst2.append(order[i])\n\t\tst2.sort()\n\t\tst3 = ''\n\t\tfor i in st2:\n\t\t\tst3 += order_rev[i] + ' '\n\t\tprint(st3.strip())\n\telse:\n\t\tprint('Impossible')\nn = int(input().strip())\n(i_start, j_start, i_end, j_end) = input().strip().split(' ')\n(i_start, j_start, i_end, j_end) = [int(i_start), int(j_start), int(i_end), int(j_end)]\nprintShortestPath(n, i_start, j_start, i_end, j_end)\n", "import sys\n\ndef printShortestPath(n, i_start, j_start, i_end, j_end):\n\tdir_map = {'UL': (-1, -2), 'UR': (1, -2), 'R': (2, 0), 'LL': (-1, 2), 'LR': (1, 2), 'L': (-2, 0)}\n\tnext_posd = lambda xy, d: (xy[0] + dir_map[d][0], xy[1] + dir_map[d][1], d)\n\tpath_order = ['UL', 'UR', 'R', 'LR', 'LL', 'L']\n\tall_starts = [(j_start, i_start, d)[:2] for d in path_order]\n\tvisited = set()\n\tgoal = (j_end, i_end)\n\tq = [all_starts[0]]\n\treached_goal = False\n\tgoal_node = None\n\treverse_path = {}\n\twhile len(q) > 0:\n\t\tcurd = q.pop(0)\n\t\tif reached_goal:\n\t\t\tbreak\n\t\tif (curd[0], curd[1]) == goal:\n\t\t\tgoal_node = curd\n\t\t\tbreak\n\t\tfor d in path_order:\n\t\t\tnext_curd = next_posd(curd[:2], d)\n\t\t\tif next_curd[0] >= 0 and next_curd[0] < n and (next_curd[1] >= 0) and (next_curd[1] < n):\n\t\t\t\tif next_curd[:2] not in visited:\n\t\t\t\t\tq.append(next_curd)\n\t\t\t\t\tvisited.add(next_curd[:2])\n\t\t\t\t\treverse_path[next_curd] = curd\n\t\t\t\t\tif (next_curd[0], next_curd[1]) == goal:\n\t\t\t\t\t\treached_goal = True\n\t\t\t\t\t\tgoal_node = next_curd\n\t\t\t\t\t\tbreak\n\tif goal_node is None:\n\t\tprint('Impossible')\n\t\treturn\n\tcur = goal_node\n\tpath = []\n\twhile cur != all_starts[0]:\n\t\tpath += [cur[2]]\n\t\tcur = reverse_path[cur]\n\tprint(len(path))\n\tprint(*path[::-1])\nn = int(input().strip())\n(i_start, j_start, i_end, j_end) = input().strip().split(' ')\n(i_start, j_start, i_end, j_end) = [int(i_start), int(j_start), int(i_end), int(j_end)]\nprintShortestPath(n, i_start, j_start, i_end, j_end)\n", "class Move(object):\n\n\tdef __init__(self, i, j, move, prior):\n\t\tself.i = i\n\t\tself.j = j\n\t\tself.move = move\n\t\tself.prior = prior\n\ndef on_board(n, i, j):\n\tif i < 0 or i > n - 1:\n\t\treturn False\n\tif j < 0 or j > n - 1:\n\t\treturn False\n\treturn True\n\ndef get_path(final_move):\n\tmove_list = []\n\tlast_move = final_move\n\twhile last_move.prior:\n\t\tmove_list.append(last_move.move)\n\t\tlast_move = last_move.prior\n\tmove_list.reverse()\n\treturn move_list\n\ndef get_moves(previously_occupied, queue, i_end, j_end):\n\tmoves = []\n\twhile queue:\n\t\tmove = queue.pop(0)\n\t\ti = move.i\n\t\tj = move.j\n\t\tif i == i_end and j == j_end:\n\t\t\tmoves = get_path(move)\n\t\t\tbreak\n\t\tif on_board(n, i - 2, j - 1):\n\t\t\tif not previously_occupied[i - 2][j - 1]:\n\t\t\t\tqueue.append(Move(i - 2, j - 1, 'UL', move))\n\t\t\t\tpreviously_occupied[i - 2][j - 1] = True\n\t\tif on_board(n, i - 2, j + 1):\n\t\t\tif not previously_occupied[i - 2][j + 1]:\n\t\t\t\tqueue.append(Move(i - 2, j + 1, 'UR', move))\n\t\t\t\tpreviously_occupied[i - 2][j + 1] = True\n\t\tif on_board(n, i, j + 2):\n\t\t\tif not previously_occupied[i][j + 2]:\n\t\t\t\tqueue.append(Move(i, j + 2, 'R', move))\n\t\t\t\tpreviously_occupied[i][j + 2] = True\n\t\tif on_board(n, i + 2, j + 1):\n\t\t\tif not previously_occupied[i + 2][j + 1]:\n\t\t\t\tqueue.append(Move(i + 2, j + 1, 'LR', move))\n\t\t\t\tpreviously_occupied[i + 2][j + 1] = True\n\t\tif on_board(n, i + 2, j - 1):\n\t\t\tif not previously_occupied[i + 2][j - 1]:\n\t\t\t\tqueue.append(Move(i + 2, j - 1, 'LL', move))\n\t\t\t\tpreviously_occupied[i + 2][j - 1] = True\n\t\tif on_board(n, i, j - 2):\n\t\t\tif not previously_occupied[i][j - 2]:\n\t\t\t\tqueue.append(Move(i, j - 2, 'L', move))\n\t\t\t\tpreviously_occupied[i][j - 2] = True\n\treturn moves\n\ndef printShortestPath(n, i_start, j_start, i_end, j_end):\n\tmove_queue = [Move(i_start, j_start, None, None)]\n\tboard = [[False] * n for _ in range(n)]\n\tmoves = get_moves(board, move_queue, i_end, j_end)\n\tif not moves:\n\t\tprint('Impossible')\n\telse:\n\t\tprint(len(moves))\n\t\tprint(' '.join(moves))\nn = int(input().strip())\n(i_start, j_start, i_end, j_end) = input().strip().split(' ')\n(i_start, j_start, i_end, j_end) = [int(i_start), int(j_start), int(i_end), int(j_end)]\nprintShortestPath(n, i_start, j_start, i_end, j_end)\n", "from operator import itemgetter\nn = int(input())\n(si, sj, ei, ej) = map(int, input().split())\nui = si\nuj = sj\ncheck = 0\npath = []\nif abs(si - ei) % 2 == 1:\n\tprint('Impossible')\nelif abs(sj - ej) % 2 == 1 and si == ei:\n\tprint('Impossible')\nelse:\n\twhile True:\n\t\tc = 0\n\t\tif uj == ej:\n\t\t\tc = 1\n\t\t\tfor i in range(abs(ui - ei) // 4):\n\t\t\t\tif ei > ui:\n\t\t\t\t\tpath.append('LR')\n\t\t\t\t\tpath.append('LL')\n\t\t\t\t\tui = ui + 4\n\t\t\t\telse:\n\t\t\t\t\tprint('UR', end=' ')\n\t\t\t\t\tprint('UL', end=' ')\n\t\t\t\t\tui = ui - 4\n\t\tif ui == ei:\n\t\t\tc = 1\n\t\t\tfor i in range(abs(uj - ej) // 2):\n\t\t\t\tif uj > ej:\n\t\t\t\t\tpath.append('L')\n\t\t\t\t\tuj = uj - 2\n\t\t\t\telse:\n\t\t\t\t\tpath.append('R')\n\t\t\t\t\tuj = uj + 2\n\t\tif c == 0:\n\t\t\tif ui < ei:\n\t\t\t\tif uj < ej:\n\t\t\t\t\tpath.append('LR')\n\t\t\t\t\tuj += 1\n\t\t\t\t\tui += 2\n\t\t\t\telse:\n\t\t\t\t\tpath.append('LL')\n\t\t\t\t\tuj -= 1\n\t\t\t\t\tui += 2\n\t\t\telif uj < ej:\n\t\t\t\tpath.append('UR')\n\t\t\t\tuj += 1\n\t\t\t\tui -= 2\n\t\t\telse:\n\t\t\t\tpath.append('UL')\n\t\t\t\tuj -= 1\n\t\t\t\tui -= 2\n\t\tif abs(ui - ei) == 1 and abs(uj - ej) == 1:\n\t\t\tcheck = 1\n\t\tif abs(ui - ei) == 1 and abs(uj - ej) == 0:\n\t\t\tcheck = 1\n\t\tif abs(ui - ei) == 0 and abs(uj - ej) == 1:\n\t\t\tcheck = 1\n\t\tif abs(ui - ei) == 2 and abs(uj - ej) == 0:\n\t\t\tcheck = 1\n\t\tif ui >= n or uj >= n:\n\t\t\tcheck = 1\n\t\tif ui == ei and uj == ej:\n\t\t\tbreak\n\t\tif check == 1:\n\t\t\tbreak\np = 1\nif check == 0:\n\tpr = []\n\tfor i in path:\n\t\tif i == 'UL':\n\t\t\tpr.append(1)\n\t\tif i == 'UR':\n\t\t\tpr.append(2)\n\t\tif i == 'R':\n\t\t\tpr.append(3)\n\t\tif i == 'LR':\n\t\t\tpr.append(4)\n\t\tif i == 'LL':\n\t\t\tpr.append(5)\n\t\tif i == 'L':\n\t\t\tpr.append(6)\n\tspath = list(zip(pr, path))\n\tspath.sort(key=itemgetter(0))\n\tprint(len(path) or '')\n\tfor i in range(len(path)):\n\t\tprint(spath[i][1], end=' ')\nelse:\n\tprint('Impossible')\n", "import sys\nmove = {'UL': (-2, -1, 0), 'UR': (-2, 1, 1), 'R': (0, 2, 2), 'LR': (2, 1, 3), 'LL': (2, -1, 4), 'L': (0, -2, 5)}\n\ndef reorder(moves):\n\treturn sorted(moves, key=lambda x: move[x][2])\n\ndef printShortestPath(n, i_start, j_start, i_end, j_end):\n\tif abs(i_start - i_end) % 2:\n\t\tprint('Impossible')\n\t\treturn\n\tif (j_start - j_end) % 2 - (i_start - i_end) / 2 % 2 != 0:\n\t\tprint('Impossible')\n\t\treturn\n\tmoves = []\n\ti_curr = i_start\n\tj_curr = j_start\n\twhile i_curr < i_end:\n\t\tif j_curr <= j_end:\n\t\t\tkey = 'LR'\n\t\telse:\n\t\t\tkey = 'LL'\n\t\tmoves += [key]\n\t\ti_curr += move[key][0]\n\t\tj_curr += move[key][1]\n\twhile i_curr > i_end:\n\t\tif j_curr >= j_end:\n\t\t\tkey = 'UL'\n\t\telse:\n\t\t\tkey = 'UR'\n\t\tmoves += [key]\n\t\ti_curr += move[key][0]\n\t\tj_curr += move[key][1]\n\twhile j_curr > j_end:\n\t\tkey = 'L'\n\t\tmoves += [key]\n\t\ti_curr += move[key][0]\n\t\tj_curr += move[key][1]\n\twhile j_curr < j_end:\n\t\tkey = 'R'\n\t\tmoves += [key]\n\t\ti_curr += move[key][0]\n\t\tj_curr += move[key][1]\n\tmoves = reorder(moves)\n\tprint(len(moves))\n\tprint(' '.join(moves))\nn = int(input().strip())\n(i_start, j_start, i_end, j_end) = input().strip().split(' ')\n(i_start, j_start, i_end, j_end) = [int(i_start), int(j_start), int(i_end), int(j_end)]\nprintShortestPath(n, i_start, j_start, i_end, j_end)\n", "import sys\n\ndef printShortestPath(n, i_start, j_start, i_end, j_end):\n\tif i_start % 2 != i_end % 2 or abs((i_start - i_end) // 2) % 2 != abs(j_start - j_end) % 2:\n\t\tprint('Impossible')\n\telse:\n\t\tans = []\n\t\twhile i_start > i_end:\n\t\t\ti_start -= 2\n\t\t\tif j_start + 1 < n and (j_start < j_end or abs(j_start + 1 - j_end) <= (i_start - i_end) // 2):\n\t\t\t\tj_start += 1\n\t\t\t\tans.append('UR')\n\t\t\telse:\n\t\t\t\tj_start -= 1\n\t\t\t\tans.append('UL')\n\t\twhile j_start < j_end and abs(j_start - j_end) > (i_end - i_start) // 2:\n\t\t\tj_start += 2\n\t\t\tans.append('R')\n\t\twhile i_start < i_end:\n\t\t\ti_start += 2\n\t\t\tif j_start + 1 < n and (j_start < j_end or abs(j_start + 1 - j_end) <= (i_end - i_start) // 2):\n\t\t\t\tj_start += 1\n\t\t\t\tans.append('LR')\n\t\t\telse:\n\t\t\t\tj_start -= 1\n\t\t\t\tans.append('LL')\n\t\twhile j_start > j_end:\n\t\t\tj_start -= 2\n\t\t\tans.append('L')\n\t\tprint(len(ans))\n\t\tprint(' '.join(ans))\nn = int(input().strip())\n(i_start, j_start, i_end, j_end) = input().strip().split(' ')\n(i_start, j_start, i_end, j_end) = [int(i_start), int(j_start), int(i_end), int(j_end)]\nprintShortestPath(n, i_start, j_start, i_end, j_end)\n", "import sys\nd = {1: 'UL', 2: 'UR', 3: 'R', 4: 'LR', 5: 'LL', 6: 'L'}\n\ndef printShortestPath(n, i_start, j_start, i_end, j_end):\n\tmoves = []\n\tcounter = 0\n\tif (i_start - i_end) % 2 == 1:\n\t\tprint('Impossible')\n\telif (i_start - i_end) % 4 == 2 and (j_start - j_end) % 2 == 0:\n\t\tprint('Impossible')\n\telif (i_start - i_end) % 4 == 0 and (j_start - j_end) % 2 == 1:\n\t\tprint('Impossible')\n\telse:\n\t\twhile abs(i_start - i_end) + abs(j_start - j_end) > 0:\n\t\t\tcounter += 1\n\t\t\tif i_start == i_end:\n\t\t\t\tif j_start > j_end:\n\t\t\t\t\tmoves.append(6)\n\t\t\t\t\tj_start -= 2\n\t\t\t\telse:\n\t\t\t\t\tmoves.append(3)\n\t\t\t\t\tj_start += 2\n\t\t\telif i_end > i_start:\n\t\t\t\ti_start += 2\n\t\t\t\tif j_start <= j_end and j_start != n - 1:\n\t\t\t\t\tmoves.append(4)\n\t\t\t\t\tj_start += 1\n\t\t\t\telse:\n\t\t\t\t\tmoves.append(5)\n\t\t\t\t\tj_start -= 1\n\t\t\telse:\n\t\t\t\ti_start -= 2\n\t\t\t\tif j_start >= j_end and j_start != 0:\n\t\t\t\t\tmoves.append(1)\n\t\t\t\t\tj_start -= 1\n\t\t\t\telse:\n\t\t\t\t\tmoves.append(2)\n\t\t\t\t\tj_start += 1\n\t\tmoves = sorted(moves)\n\t\tprint(counter)\n\t\tfor m in moves:\n\t\t\tprint(d[m], end=' ')\nn = int(input().strip())\n(i_start, j_start, i_end, j_end) = input().strip().split(' ')\n(i_start, j_start, i_end, j_end) = [int(i_start), int(j_start), int(i_end), int(j_end)]\nprintShortestPath(n, i_start, j_start, i_end, j_end)\n", "from collections import deque\nimport sys\n\ndef printShortestPath(n, i_start, j_start, i_end, j_end):\n\t(iDiff, jDiff) = (i_end - i_start, j_end - j_start)\n\tif iDiff % 2 == 1 or (iDiff / 2 - jDiff) % 2 == 1:\n\t\tprint('Impossible')\n\telse:\n\t\t(actions, leftTemp) = (deque(), deque())\n\t\twhile (iDiff, jDiff) != (0, 0):\n\t\t\tif iDiff == 0:\n\t\t\t\tfor i in range(0, abs(jDiff), 2):\n\t\t\t\t\tif jDiff > 0:\n\t\t\t\t\t\tactions.append('R')\n\t\t\t\t\telse:\n\t\t\t\t\t\tactions.append('L')\n\t\t\t\tbreak\n\t\t\telif iDiff < 0:\n\t\t\t\twhile iDiff != 0 and jDiff != 0:\n\t\t\t\t\tif jDiff < 0:\n\t\t\t\t\t\t(iDiff, jDiff) = (iDiff + 2, jDiff + 1)\n\t\t\t\t\t\tactions.append('UL')\n\t\t\t\t\telse:\n\t\t\t\t\t\t(iDiff, jDiff) = (iDiff + 2, jDiff - 1)\n\t\t\t\t\t\tactions.append('UR')\n\t\t\t\tif jDiff == 0:\n\t\t\t\t\tfor i in range(0, abs(iDiff), 4):\n\t\t\t\t\t\tactions.appendleft('UL')\n\t\t\t\t\t\tactions.append('UR')\n\t\t\telse:\n\t\t\t\tsurplus = abs(jDiff) - int(abs(iDiff) / 2)\n\t\t\t\tfor i in range(0, max(surplus, 0), 2):\n\t\t\t\t\tif jDiff > 0:\n\t\t\t\t\t\tjDiff -= 2\n\t\t\t\t\t\tactions.append('R')\n\t\t\t\t\telse:\n\t\t\t\t\t\tjDiff += 2\n\t\t\t\t\t\tleftTemp.append('L')\n\t\t\t\tfor i in range(abs(jDiff)):\n\t\t\t\t\tif jDiff < 0:\n\t\t\t\t\t\tleftTemp.appendleft('LL')\n\t\t\t\t\telse:\n\t\t\t\t\t\tactions.append('LR')\n\t\t\t\tiDiff -= 2 * abs(jDiff)\n\t\t\t\tfor i in range(0, abs(iDiff), 4):\n\t\t\t\t\tactions.append('LR')\n\t\t\t\tfor i in range(0, abs(iDiff), 4):\n\t\t\t\t\tactions.append('LL')\n\t\t\t\tbreak\n\t\tactions = actions + leftTemp\n\t\tprint(len(actions))\n\t\tprint(' '.join(actions))\n\treturn\nn = int(input().strip())\n(i_start, j_start, i_end, j_end) = input().strip().split(' ')\n(i_start, j_start, i_end, j_end) = [int(i_start), int(j_start), int(i_end), int(j_end)]\nprintShortestPath(n, i_start, j_start, i_end, j_end)\n", "n = int(input())\n(u, v, x, y) = list(map(int, input().split()))\nlevel = [[-1 for i in range(n)] for j in range(n)]\nparent = [['' for i in range(n)] for j in range(n)]\nparent2 = [[-1 for i in range(n)] for j in range(n)]\nfrontier = [(u, v)]\nlevel[u][v] = 0\nwhile len(frontier) > 0:\n\tnew_frontier = []\n\tfor f in frontier:\n\t\ti = f[0]\n\t\tj = f[1]\n\t\tif i - 2 >= 0 and j - 1 >= 0 and (level[i - 2][j - 1] == -1):\n\t\t\tlevel[i - 2][j - 1] = level[i][j] + 1\n\t\t\tparent[i - 2][j - 1] = 'UL'\n\t\t\tparent2[i - 2][j - 1] = (i, j)\n\t\t\tnew_frontier.append((i - 2, j - 1))\n\t\tif i - 2 >= 0 and j + 1 < n and (level[i - 2][j + 1] == -1):\n\t\t\tlevel[i - 2][j + 1] = level[i][j] + 1\n\t\t\tparent[i - 2][j + 1] = 'UR'\n\t\t\tnew_frontier.append((i - 2, j + 1))\n\t\t\tparent2[i - 2][j + 1] = (i, j)\n\t\tif j + 2 < n and level[i][j + 2] == -1:\n\t\t\tlevel[i][j + 2] = level[i][j] + 1\n\t\t\tparent[i][j + 2] = 'R'\n\t\t\tnew_frontier.append((i, j + 2))\n\t\t\tparent2[i][j + 2] = (i, j)\n\t\tif i + 2 < n and j + 1 < n and (level[i + 2][j + 1] == -1):\n\t\t\tlevel[i + 2][j + 1] = level[i][j] + 1\n\t\t\tparent[i + 2][j + 1] = 'LR'\n\t\t\tnew_frontier.append((i + 2, j + 1))\n\t\t\tparent2[i + 2][j + 1] = (i, j)\n\t\tif i + 2 < n and j - 1 >= 0 and (level[i + 2][j - 1] == -1):\n\t\t\tlevel[i + 2][j - 1] = level[i][j] + 1\n\t\t\tparent[i + 2][j - 1] = 'LL'\n\t\t\tparent2[i + 2][j - 1] = (i, j)\n\t\t\tnew_frontier.append((i + 2, j - 1))\n\t\tif j - 2 >= 0 and level[i][j - 2] == -1:\n\t\t\tlevel[i][j - 2] = level[i][j] + 1\n\t\t\tparent[i][j - 2] = 'L'\n\t\t\tparent2[i][j - 2] = (i, j)\n\t\t\tnew_frontier.append((i, j - 2))\n\tfrontier = new_frontier\nif level[x][y] == -1:\n\tprint('Impossible')\nelse:\n\tprint(level[x][y])\n\tans = []\n\twhile not (x == u and y == v):\n\t\tans.append(parent[x][y])\n\t\t(x, y) = parent2[x][y]\n\tans.reverse()\n\tprint(' '.join((x for x in ans)))\n", "from collections import deque\nmoves = [('UL', -2, -1), ('UR', -2, 1), ('R', 0, 2), ('LR', 2, 1), ('LL', 2, -1), ('L', 0, -2)]\nn = int(input())\n(si, sj, ti, tj) = map(int, input().split())\nunvisited = set()\nfor i in range(n):\n\tfor j in range(n):\n\t\tunvisited.add((i, j))\nq = deque()\nq.append(((si, sj), -1, None))\nunvisited.remove((si, sj))\ni = 0\nwhile unvisited and i < len(q):\n\t(node, parent, parentMove) = q[i]\n\tif node == (ti, tj):\n\t\tbreak\n\tfor (move, di, dj) in moves:\n\t\tnewNode = (node[0] + di, node[1] + dj)\n\t\tif newNode in unvisited:\n\t\t\tunvisited.remove(newNode)\n\t\t\tq.append((newNode, i, move))\n\ti += 1\nif i >= len(q):\n\tprint('Impossible')\nelse:\n\tresult = []\n\t(node, parent, parentMove) = q[i]\n\twhile parent >= 0:\n\t\tresult.append(parentMove)\n\t\t(node, parent, parentMove) = q[parent]\n\tresult.reverse()\n\tprint(len(result))\n\tprint(' '.join(result))\n", "import sys\n\ndef printShortestPath(n, i_start, j_start, i_end, j_end):\n\tmovs = []\n\tif (i_end - i_start) % 2 != 0:\n\t\tprint('Impossible')\n\t\treturn\n\tv_hops = abs(i_end - i_start) // 2\n\tif v_hops % 2 == 0 and (j_end - j_start) % 2 != 0:\n\t\tprint('Impossible')\n\t\treturn\n\tif v_hops % 2 != 0 and (j_end - j_start) % 2 == 0:\n\t\tprint('Impossible')\n\t\treturn\n\tfor i in range(v_hops):\n\t\tv_dir = i_end > i_start and 'L' or 'U'\n\t\tif j_start > j_end or j_start == n - 1:\n\t\t\tmovs.append(v_dir + 'L')\n\t\t\tj_start -= 1\n\t\telse:\n\t\t\tmovs.append(v_dir + 'R')\n\t\t\tj_start += 1\n\tif j_start != j_end:\n\t\th_dir = j_end > j_start and 'R' or 'L'\n\t\tfor i in range(abs(j_end - j_start) // 2):\n\t\t\tmovs.append(h_dir)\n\treturn movs\n\ndef find_move(movs, m):\n\ttry:\n\t\treturn movs.index(m)\n\texcept ValueError:\n\t\treturn -1\nn = int(input().strip())\n(i_start, j_start, i_end, j_end) = input().strip().split(' ')\n(i_start, j_start, i_end, j_end) = [int(i_start), int(j_start), int(i_end), int(j_end)]\nmovs = printShortestPath(n, i_start, j_start, i_end, j_end)\nif movs:\n\tprint(len(movs))\n\tord_movs = []\n\twhile movs:\n\t\tidx = False\n\t\tfor m in ['UL', 'UR', 'R', 'LR', 'LL', 'L']:\n\t\t\tidx = find_move(movs, m)\n\t\t\tif idx >= 0:\n\t\t\t\tbreak\n\t\tord_movs.append(movs[idx])\n\t\tmovs.remove(movs[idx])\n\tprint(' '.join(ord_movs))\n", "import sys\n\ndef printShortestPath(n, i_start, j_start, i_end, j_end):\n\tdiff_i = i_end - i_start\n\tdiff_j = j_end - j_start\n\ti = i_start\n\tj = j_start\n\tif diff_i % 2 == 1:\n\t\tprint('Impossible')\n\t\treturn\n\tif diff_i % 4 == 0 and diff_j % 2 == 1:\n\t\tprint('Impossible')\n\t\treturn\n\tif diff_i % 4 == 2 and diff_j % 2 == 0:\n\t\tprint('Impossible')\n\t\treturn\n\tmoves = []\n\twhile diff_i < 0 and diff_i // -2 > diff_j:\n\t\tif j == 0:\n\t\t\tdiff_i += 2\n\t\t\tdiff_j -= 1\n\t\t\ti -= 2\n\t\t\tj += 1\n\t\t\tmoves.append('UR')\n\t\t\tcontinue\n\t\tdiff_i += 2\n\t\tdiff_j += 1\n\t\ti -= 2\n\t\tj -= 1\n\t\tmoves.append('UL')\n\twhile diff_i < 0:\n\t\tdiff_i += 2\n\t\tdiff_j -= 1\n\t\ti -= 2\n\t\tj += 1\n\t\tmoves.append('UR')\n\twhile diff_j > 0 and diff_j > diff_i // 2:\n\t\tmoves.append('R')\n\t\tj += 2\n\t\tdiff_j -= 2\n\twhile diff_i > 0 and diff_i // -2 < diff_j:\n\t\tif j == n - 1:\n\t\t\tdiff_i -= 2\n\t\t\tdiff_j += 1\n\t\t\ti += 2\n\t\t\tj -= 1\n\t\t\tmoves.append('LL')\n\t\t\tcontinue\n\t\tmoves.append('LR')\n\t\tdiff_i -= 2\n\t\tdiff_j -= 1\n\t\ti += 2\n\t\tj += 1\n\twhile diff_i > 0:\n\t\tdiff_i -= 2\n\t\tdiff_j += 1\n\t\ti += 2\n\t\tj -= 1\n\t\tmoves.append('LL')\n\tif diff_i == 0:\n\t\tif diff_j > 0:\n\t\t\tmove = diff_j // 2\n\t\t\tmoves += ['R'] * move\n\t\telse:\n\t\t\tmove = -diff_j // 2\n\t\t\tmoves += ['L'] * move\n\tprint(len(moves))\n\tprint(' '.join(moves))\nn = int(input().strip())\n(i_start, j_start, i_end, j_end) = input().strip().split(' ')\n(i_start, j_start, i_end, j_end) = [int(i_start), int(j_start), int(i_end), int(j_end)]\nprintShortestPath(n, i_start, j_start, i_end, j_end)\n", "import sys\n\ndef printShortestPath(n, i_start, j_start, i_end, j_end):\n\tmoves = 0\n\tn_ul = 0\n\tn_ur = 0\n\tn_r = 0\n\tn_l = 0\n\tn_ll = 0\n\tn_lr = 0\n\ti_diff = i_start - i_end\n\tj_diff = j_start - j_end\n\tif abs(i_diff) % 2 != 0 or (abs(j_diff) - abs(i_diff / 2)) % 2 != 0:\n\t\tprint('Impossible')\n\telse:\n\t\twhile i_diff != 0:\n\t\t\tif i_diff > 0 and j_diff >= 0:\n\t\t\t\tn_ul += 1\n\t\t\t\tmoves += 1\n\t\t\t\ti_diff -= 2\n\t\t\t\tj_diff -= 1\n\t\t\telif i_diff > 0 and j_diff < 0:\n\t\t\t\tn_ur += 1\n\t\t\t\tmoves += 1\n\t\t\t\ti_diff -= 2\n\t\t\t\tj_diff += 1\n\t\t\telif i_diff < 0 and j_diff > 0:\n\t\t\t\tn_ll += 1\n\t\t\t\tmoves += 1\n\t\t\t\ti_diff += 2\n\t\t\t\tj_diff -= 1\n\t\t\telif i_diff < 0 and j_diff <= 0:\n\t\t\t\tn_lr += 1\n\t\t\t\tmoves += 1\n\t\t\t\ti_diff += 2\n\t\t\t\tj_diff += 1\n\t\twhile j_diff != 0:\n\t\t\tif j_diff > 0:\n\t\t\t\tn_l += 1\n\t\t\t\tmoves += 1\n\t\t\t\tj_diff -= 2\n\t\t\telse:\n\t\t\t\tn_r += 1\n\t\t\t\tmoves += 1\n\t\t\t\tj_diff += 2\n\t\tprint(moves)\n\t\tfor x in range(n_ul):\n\t\t\tprint('UL', end=' ')\n\t\tfor x in range(n_ur):\n\t\t\tprint('UR', end=' ')\n\t\tfor x in range(n_r):\n\t\t\tprint('R', end=' ')\n\t\tfor x in range(n_lr):\n\t\t\tprint('LR', end=' ')\n\t\tfor x in range(n_ll):\n\t\t\tprint('LL', end=' ')\n\t\tfor x in range(n_l):\n\t\t\tprint('L', end=' ')\nn = int(input().strip())\n(i_start, j_start, i_end, j_end) = input().strip().split(' ')\n(i_start, j_start, i_end, j_end) = [int(i_start), int(j_start), int(i_end), int(j_end)]\nprintShortestPath(n, i_start, j_start, i_end, j_end)\n", "import sys\n\ndef printShortestPath(n, i_start, j_start, i_end, j_end):\n\tvisited = [[False for i in range(n)] for j in range(n)]\n\tparent = [[0 for i in range(n)] for j in range(n)]\n\tQ = [[i_start, j_start, 0]]\n\tsol = False\n\twhile len(Q) > 0:\n\t\tcurr = Q.pop(0)\n\t\tif curr[0] == i_end and curr[1] == j_end:\n\t\t\tsol = True\n\t\t\tbreak\n\t\tif visited[curr[0]][curr[1]] != False:\n\t\t\tcontinue\n\t\tvisited[curr[0]][curr[1]] = True\n\t\tif curr[0] - 2 >= 0:\n\t\t\tif curr[1] - 1 >= 0:\n\t\t\t\tif visited[curr[0] - 2][curr[1] - 1] == False:\n\t\t\t\t\tQ.append([curr[0] - 2, curr[1] - 1, curr[2] + 1])\n\t\t\t\t\tif parent[curr[0] - 2][curr[1] - 1] == 0:\n\t\t\t\t\t\tparent[curr[0] - 2][curr[1] - 1] = 'UL'\n\t\t\tif curr[1] + 1 < n:\n\t\t\t\tif visited[curr[0] - 2][curr[1] + 1] == False:\n\t\t\t\t\tQ.append([curr[0] - 2, curr[1] + 1, curr[2] + 1])\n\t\t\t\t\tif parent[curr[0] - 2][curr[1] + 1] == 0:\n\t\t\t\t\t\tparent[curr[0] - 2][curr[1] + 1] = 'UR'\n\t\tif curr[1] + 2 < n:\n\t\t\tif visited[curr[0]][curr[1] + 2] == False:\n\t\t\t\tQ.append([curr[0], curr[1] + 2, curr[2] + 1])\n\t\t\t\tif parent[curr[0]][curr[1] + 2] == 0:\n\t\t\t\t\tparent[curr[0]][curr[1] + 2] = 'R'\n\t\tif curr[0] + 2 < n:\n\t\t\tif curr[1] + 1 < n:\n\t\t\t\tif visited[curr[0] + 2][curr[1] + 1] == False:\n\t\t\t\t\tQ.append([curr[0] + 2, curr[1] + 1, curr[2] + 1])\n\t\t\t\t\tif parent[curr[0] + 2][curr[1] + 1] == 0:\n\t\t\t\t\t\tparent[curr[0] + 2][curr[1] + 1] = 'LR'\n\t\t\tif curr[1] - 1 >= 0:\n\t\t\t\tif visited[curr[0] + 2][curr[1] - 1] == False:\n\t\t\t\t\tQ.append([curr[0] + 2, curr[1] - 1, curr[2] + 1])\n\t\t\t\t\tif parent[curr[0] + 2][curr[1] - 1] == 0:\n\t\t\t\t\t\tparent[curr[0] + 2][curr[1] - 1] = 'LL'\n\t\tif curr[1] - 2 >= 0:\n\t\t\tif visited[curr[0]][curr[1] - 2] == False:\n\t\t\t\tQ.append([curr[0], curr[1] - 2, curr[2] + 1])\n\t\t\t\tif parent[curr[0]][curr[1] - 2] == 0:\n\t\t\t\t\tparent[curr[0]][curr[1] - 2] = 'L'\n\tif sol:\n\t\tprint(curr[2])\n\t\tpath = []\n\t\twhile i_end != i_start or j_end != j_start:\n\t\t\tparentletter = parent[i_end][j_end]\n\t\t\tpath.append(parentletter)\n\t\t\tif parentletter == 'UR':\n\t\t\t\ti_end = i_end + 2\n\t\t\t\tj_end = j_end - 1\n\t\t\tif parentletter == 'R':\n\t\t\t\ti_end = i_end\n\t\t\t\tj_end = j_end - 2\n\t\t\tif parentletter == 'LR':\n\t\t\t\ti_end = i_end - 2\n\t\t\t\tj_end = j_end - 1\n\t\t\tif parentletter == 'LL':\n\t\t\t\ti_end = i_end - 2\n\t\t\t\tj_end = j_end + 1\n\t\t\tif parentletter == 'L':\n\t\t\t\ti_end = i_end\n\t\t\t\tj_end = j_end + 2\n\t\t\tif parentletter == 'UL':\n\t\t\t\ti_end = i_end + 2\n\t\t\t\tj_end = j_end + 1\n\t\tfor qw in range(len(path)):\n\t\t\tprint(path[-1 - qw], end=' ')\n\telse:\n\t\tprint('Impossible')\nn = int(input().strip())\n(i_start, j_start, i_end, j_end) = input().strip().split(' ')\n(i_start, j_start, i_end, j_end) = [int(i_start), int(j_start), int(i_end), int(j_end)]\nprintShortestPath(n, i_start, j_start, i_end, j_end)\n", "import sys\nmoves = ['UL', 'UR', 'R', 'LR', 'LL', 'L']\n\ndef step(n, i_start, j_start, move, history):\n\tif move == 'UL' and i_start > 0 and (j_start > 1):\n\t\treturn (i_start - 1, j_start - 2, move, history)\n\tif move == 'UR' and i_start < n - 1 and (j_start > 1):\n\t\treturn (i_start + 1, j_start - 2, move, history)\n\tif move == 'R' and j_start < n - 2:\n\t\treturn (i_start + 2, j_start, move, history)\n\tif move == 'LL' and i_start > 0 and (j_start < n - 2):\n\t\treturn (i_start - 1, j_start + 2, move, history)\n\tif move == 'LR' and i_start < n - 1 and (j_start < n - 2):\n\t\treturn (i_start + 1, j_start + 2, move, history)\n\tif move == 'L' and i_start > 1:\n\t\treturn (i_start - 2, j_start, move, history)\n\treturn None\n\ndef distance(i_start, j_start, i_end, j_end):\n\treturn abs(i_end - i_start) + abs(j_end - j_start)\n\ndef printShortestPath(n, j_start, i_start, j_end, i_end):\n\tvisited = [(i_start, j_start)]\n\tcandidates = [(i_start, j_start, None, None)]\n\tdist = 9999\n\tfound = False\n\twhile not found:\n\t\tnew_candidates = []\n\t\tfor candidate in candidates:\n\t\t\tcur_dist = distance(candidate[0], candidate[1], i_end, j_end)\n\t\t\tif cur_dist == 0:\n\t\t\t\tfound = True\n\t\t\t\tnew_candidates.append(candidate)\n\t\t\t\tbreak\n\t\t\tfor move in moves:\n\t\t\t\tnext = step(n, candidate[0], candidate[1], move, candidate)\n\t\t\t\tif next != None:\n\t\t\t\t\tnew_dist = distance(next[0], next[1], i_end, j_end)\n\t\t\t\t\tif new_dist < cur_dist and (next[0], next[1]) not in visited:\n\t\t\t\t\t\tnew_candidates.append(next)\n\t\t\t\t\t\tvisited.append((next[0], next[1]))\n\t\tif len(new_candidates) == 0:\n\t\t\tbreak\n\t\tcandidates = new_candidates\n\tfound = False\n\tfor c in candidates:\n\t\tif c[0] == i_end and c[1] == j_end:\n\t\t\tfound = True\n\t\t\tl = 0\n\t\t\tpath = ''\n\t\t\tx = c\n\t\t\twhile x[2] is not None:\n\t\t\t\tpath = x[2] + ' ' + path\n\t\t\t\tx = x[3]\n\t\t\t\tl += 1\n\t\t\tprint(l)\n\t\t\tprint(path)\n\t\t\tbreak\n\tif not found:\n\t\tprint('Impossible')\nn = int(input().strip())\n(i_start, j_start, i_end, j_end) = input().strip().split(' ')\n(i_start, j_start, i_end, j_end) = [int(i_start), int(j_start), int(i_end), int(j_end)]\nprintShortestPath(n, i_start, j_start, i_end, j_end)\n", "import sys\n\ndef printShortestPath(n, i_start, j_start, i_end, j_end):\n\tif i_start % 2 != i_end % 2 or (i_start % 4 == i_end % 4 and j_start % 2 != j_end % 2) or (i_start % 4 != i_end % 4 and j_start % 2 == j_end % 2):\n\t\tprint('Impossible')\n\telse:\n\t\tmoves = 0\n\t\tsmoves = ''\n\t\twhile i_start != i_end or j_start != j_end:\n\t\t\tmoves += 1\n\t\t\tif i_start > i_end and j_start > j_end - (i_start - i_end) // 2 and (j_start > 0):\n\t\t\t\tsmoves += 'UL '\n\t\t\t\ti_start -= 2\n\t\t\t\tj_start -= 1\n\t\t\telif i_start > i_end:\n\t\t\t\tsmoves += 'UR '\n\t\t\t\ti_start -= 2\n\t\t\t\tj_start += 1\n\t\t\telif i_start <= i_end and j_start < j_end - (i_end - i_start) // 2:\n\t\t\t\tsmoves += 'R '\n\t\t\t\tj_start += 2\n\t\t\telif i_start < i_end and j_start < j_end + (i_end - i_start) // 2:\n\t\t\t\tsmoves += 'LR '\n\t\t\t\ti_start += 2\n\t\t\t\tj_start += 1\n\t\t\telif i_start < i_end and j_start >= j_end + (i_end - i_start) // 2:\n\t\t\t\tsmoves += 'LL '\n\t\t\t\ti_start += 2\n\t\t\t\tj_start -= 1\n\t\t\telse:\n\t\t\t\tsmoves += 'L '\n\t\t\t\tj_start -= 2\n\t\tprint(moves)\n\t\tprint(smoves[:len(smoves) - 1])\nn = int(input().strip())\n(i_start, j_start, i_end, j_end) = input().strip().split(' ')\n(i_start, j_start, i_end, j_end) = [int(i_start), int(j_start), int(i_end), int(j_end)]\nprintShortestPath(n, i_start, j_start, i_end, j_end)\n", "import sys\n\ndef printShortestPath(n, ist, jst, ien, jen):\n\ts = []\n\ti = 1\n\tcount = 0\n\tflag = False\n\td = abs(ist - ien) + abs(jst - jen)\n\twhile d != 0 and i < 100000:\n\t\tk = [100000] * 6\n\t\td1 = d\n\t\tif jst - 1 >= 0 and ist - 2 >= 0:\n\t\t\tk[0] = abs(jst - 1 - jen) + abs(ist - 2 - ien)\n\t\tif jst + 1 < n and ist - 2 >= 0:\n\t\t\tk[1] = abs(jst + 1 - jen) + abs(ist - 2 - ien)\n\t\tif jst + 2 < n:\n\t\t\tk[2] = abs(jst + 2 - jen) + abs(ist - ien)\n\t\tif jst + 1 < n and ist + 2 < n:\n\t\t\tk[3] = abs(jst + 1 - jen) + abs(ist + 2 - ien)\n\t\tif jst - 1 >= 0 and ist + 2 < n:\n\t\t\tk[4] = abs(jst - 1 - jen) + abs(ist + 2 - ien)\n\t\tif jst - 2 >= 0:\n\t\t\tk[5] = abs(jst - 2 - jen) + abs(ist - ien)\n\t\tl = min(k)\n\t\tif l == k[0]:\n\t\t\tcount += 1\n\t\t\tjst = jst - 1\n\t\t\tist = ist - 2\n\t\t\ts.append(0)\n\t\telif l == k[1]:\n\t\t\tcount += 1\n\t\t\tjst = jst + 1\n\t\t\tist = ist - 2\n\t\t\ts.append(1)\n\t\telif l == k[2]:\n\t\t\tcount += 1\n\t\t\tjst = jst + 2\n\t\t\ts.append(2)\n\t\telif l == k[3]:\n\t\t\tcount += 1\n\t\t\tjst = jst + 1\n\t\t\tist = ist + 2\n\t\t\ts.append(3)\n\t\telif l == k[4]:\n\t\t\tcount += 1\n\t\t\tjst = jst - 1\n\t\t\tist = ist + 2\n\t\t\ts.append(4)\n\t\telif l == k[5]:\n\t\t\tcount += 1\n\t\t\tjst = jst - 2\n\t\t\ts.append(5)\n\t\td = abs(ist - ien) + abs(jst - jen)\n\t\ti += 1\n\t\tif d1 < d:\n\t\t\tflag = True\n\t\t\tbreak\n\ts.sort()\n\tfor i in range(len(s)):\n\t\tif s[i] == 0:\n\t\t\ts[i] = 'UL'\n\t\telif s[i] == 1:\n\t\t\ts[i] = 'UR'\n\t\telif s[i] == 2:\n\t\t\ts[i] = 'R'\n\t\telif s[i] == 3:\n\t\t\ts[i] = 'LR'\n\t\telif s[i] == 4:\n\t\t\ts[i] = 'LL'\n\t\telse:\n\t\t\ts[i] = 'L'\n\tif flag == True or d != 0:\n\t\tprint('Impossible')\n\telif d == 0:\n\t\tprint(count)\n\t\tprint(*s)\nn = int(input().strip())\n(i_start, j_start, i_end, j_end) = input().strip().split(' ')\n(i_start, j_start, i_end, j_end) = [int(i_start), int(j_start), int(i_end), int(j_end)]\nprintShortestPath(n, i_start, j_start, i_end, j_end)\n", "import sys\nfrom collections import namedtuple\nCell = namedtuple('Cell', ['x', 'y'])\nPRIORITY = ['UL', 'UR', 'R', 'LR', 'LL', 'L']\n\ndef convert_to_intlist(line):\n\treturn [int(item) for item in line.split()]\n\ndef is_valid(point, gridsize):\n\treturn 0 <= point.x < gridsize and 0 <= point.y < gridsize\n\ndef valid_neighbours_in_order(cell, gridsize):\n\t(x, y) = cell\n\tneighbours = [Cell(x - 1, y - 2), Cell(x + 1, y - 2), Cell(x + 2, y), Cell(x + 1, y + 2), Cell(x - 1, y + 2), Cell(x - 2, y)]\n\treturn [point if is_valid(point, gridsize) else None for point in neighbours]\n\ndef neighbours_of_cells(cells, distances, next_level, backtrack, gridsize):\n\tunvisited_neighbours = []\n\tfor cell in cells:\n\t\tneighbours = valid_neighbours_in_order(cell, gridsize)\n\t\tfor (neighbour, direction) in zip(neighbours, PRIORITY):\n\t\t\tif neighbour is not None and neighbour not in distances:\n\t\t\t\tdistances[neighbour] = next_level\n\t\t\t\tbacktrack[neighbour] = (cell, direction)\n\t\t\t\tunvisited_neighbours.append(neighbour)\n\treturn unvisited_neighbours\n\ndef get_complete_path(start, end, backtrack):\n\tpath = []\n\tpoint = end\n\twhile point != start:\n\t\t(point, direction) = backtrack[point]\n\t\tpath.append(direction)\n\treturn ' '.join(path[::-1])\n\ndef find_shortest_path(start, end, gridsize):\n\tdistances = {start: 0}\n\tbacktrack = {}\n\tnext_level = 1\n\tneighbours = neighbours_of_cells([start], distances, next_level, backtrack, gridsize)\n\twhile neighbours and end not in neighbours:\n\t\tnext_level += 1\n\t\tneighbours = neighbours_of_cells(neighbours, distances, next_level, backtrack, gridsize)\n\tif end not in distances:\n\t\treturn None\n\treturn (distances[end], get_complete_path(start, end, backtrack))\ndata = sys.stdin.read().splitlines()\ngridsize = int(data[0])\n(start_y, start_x, end_y, end_x) = convert_to_intlist(data[1])\nstart = Cell(start_x, start_y)\nend = Cell(end_x, end_y)\npath = find_shortest_path(start, end, gridsize)\nif path is None:\n\tprint('Impossible')\nelse:\n\tprint(path[0])\n\tprint(path[1])\n"]

difficulty: MEDIUM

source: hacker rank

skill_types: ['Complete search']

question:
In ordinary chess, the pieces are only of two colors, black and white. In our version of chess, we are including new pieces with unique movements. One of the most powerful pieces in this version is the red knight.

The red knight can move to six different positions based on its current position (UpperLeft, UpperRight, Right, LowerRight, LowerLeft, Left) as shown in the figure below.

![image](1.png)
The board is a grid of size $n\times n$. Each cell is identified with a pair of coordinates $(i,j)$, where $\boldsymbol{i}$ is the row number and $j$ is the column number, both zero-indexed. Thus, $(0,0)$ is the upper-left corner and $(n-1,n-1)$ is the bottom-right corner.

Complete the function printShortestPath, which takes as input the grid size $n$, and the coordinates of the starting and ending position $(i_{start},j_{start})$ and $(i_{end},j_{end})$ respectively, as input. The function does not return anything.

Given the coordinates of the starting position of the red knight and the coordinates of the destination, print the minimum number of moves that the red knight has to make in order to reach the destination and after that, print the order of the moves that must be followed to reach the destination in the shortest way. If the destination cannot be reached, print only the word "Impossible".

Note: There may be multiple shortest paths leading to the destination. Hence, assume that the red knight considers its possible neighbor locations in the following order of priority: UL, UR, R, LR, LL, L. In other words, if there are multiple possible options, the red knight prioritizes the first move in this list, as long as the shortest path is still achievable. Check sample input $2$ for an illustration.

Input Format

The first line of input contains a single integer $n$. The second line contains four space-separated integers $i_{start},j_{start},i_{end},j_{end}$. $(i_{start},j_{start})$ denotes the coordinates of the starting position and $(i_{end},j_{end})$ denotes the coordinates of the final position.

Constraints

$5\leq n\leq200$
$0\leq i_{start},j_{start},i_{end},j_{end}<n$
the starting and the ending positions are different

Output Format

If the destination can be reached, print two lines. In the first line, print a single integer denoting the minimum number of moves that the red knight has to make in order to reach the destination. In the second line, print the space-separated sequence of moves.

If the destination cannot be reached, print a single line containing only the word Impossible.

![image](2.png)

![image](3.png)
Sample Input 0
7
6 6 0 1

Sample Output 0
4
UL UL UL L

Explanation 0

Sample Input 1
6
5 1 0 5

Sample Output 1
Impossible

Explanation 1

Sample Input 2
7
0 3 4 3

Sample Output 2
2
LR LL

Explanation 2
![image](4.png)

image_tags: Chessboard Chessboard Chessboard Chessboard

data_split: test