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. 

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.

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

Source: hackerrank | Difficulty: MEDIUM
Tags: Complete search


Solutions:
from collections import deque
surround = [(-2, -1, 'UL'), (-2, 1, 'UR'), (0, 2, 'R'), (2, 1, 'LR'), (2, -1, 'LL'), (0, -2, 'L')]

def printShortestPath(n, i_start, j_start, i_end, j_end):
	dist = [[-1 for _ in range(n)] for _ in range(n)]
	path = [[[] for _ in range(n)] for _ in range(n)]
	q = deque([(i_start, j_start)])
	dist[i_start][j_start] = 0
	while len(q) > 0:
		(i, j) = q.popleft()
		if i == i_end and j == j_end:
			print(dist[i][j])
			print(*path[i][j])
			return
		for (dx, dy, name) in surround:
			if 0 <= i + dx < n and 0 <= j + dy < n and (dist[i + dx][j + dy] == -1):
				q.append((i + dx, j + dy))
				dist[i + dx][j + dy] = dist[i][j] + 1
				path[i + dx][j + dy] = path[i][j] + [name]
	print('Impossible')
n = int(input().strip())
(i_start, j_start, i_end, j_end) = input().strip().split(' ')
(i_start, j_start, i_end, j_end) = [int(i_start), int(j_start), int(i_end), int(j_end)]
printShortestPath(n, i_start, j_start, i_end, j_end)


import sys

def printShortestPath(n, i_start, j_start, i_end, j_end):
	fromdict = {}
	tovisit = [(i_start, j_start)]
	while len(tovisit) > 0:
		(i, j) = tovisit.pop(0)
		if (i, j) == (i_end, j_end):
			break
		if i > 1 and j > 0 and ((i - 2, j - 1) not in fromdict):
			tovisit.append((i - 2, j - 1))
			fromdict[i - 2, j - 1] = ('UL', i, j)
		if i > 1 and j < n - 1 and ((i - 2, j + 1) not in fromdict):
			tovisit.append((i - 2, j + 1))
			fromdict[i - 2, j + 1] = ('UR', i, j)
		if j < n - 2 and (i, j + 2) not in fromdict:
			tovisit.append((i, j + 2))
			fromdict[i, j + 2] = ('R', i, j)
		if i < n - 2 and j < n - 1 and ((i + 2, j + 1) not in fromdict):
			tovisit.append((i + 2, j + 1))
			fromdict[i + 2, j + 1] = ('LR', i, j)
		if i < n - 2 and j > 0 and ((i + 2, j - 1) not in fromdict):
			tovisit.append((i + 2, j - 1))
			fromdict[i + 2, j - 1] = ('LL', i, j)
		if j > 1 and (i, j - 2) not in fromdict:
			tovisit.append((i, j - 2))
			fromdict[i, j - 2] = ('L', i, j)
	if (i_end, j_end) not in fromdict:
		print('Impossible')
	else:
		ans = []
		(i, j) = (i_end, j_end)
		while (i, j) != (i_start, j_start):
			(dr, i_n, j_n) = fromdict[i, j]
			ans.append(dr)
			(i, j) = (i_n, j_n)
		ans = ans[::-1]
		print(len(ans))
		print(' '.join(ans))
n = int(input().strip())
(i_start, j_start, i_end, j_end) = input().strip().split(' ')
(i_start, j_start, i_end, j_end) = [int(i_start), int(j_start), int(i_end), int(j_end)]
printShortestPath(n, i_start, j_start, i_end, j_end)


import sys

def printShortestPath(n, i_start, j_start, i_end, j_end):
	level = [(i_start, j_start)]
	move = {}
	parent = {(i_start, j_start): None}
	options = [('UL', (-2, -1)), ('UR', (-2, 1)), ('R', (0, 2)), ('LR', (2, 1)), ('LL', (2, -1)), ('L', (0, -2))]
	n_level = 0
	while level:
		new_level = []
		for (i, j) in level:
			if i == i_end and j == j_end:
				print(n_level)
				moves = []
				curr = (i_end, j_end)
				while curr in move:
					moves.append(move[curr])
					curr = parent[curr]
				print(' '.join(moves[::-1]))
				return None
			else:
				for (key, value) in options:
					(di, dj) = value
					(new_i, new_j) = (i + di, j + dj)
					if 0 <= new_i < n and 0 <= new_j < n and ((new_i, new_j) not in parent):
						new_level.append((new_i, new_j))
						parent[new_i, new_j] = (i, j)
						move[new_i, new_j] = key
		level = new_level
		n_level += 1
	print('Impossible')
n = int(input().strip())
(i_start, j_start, i_end, j_end) = input().strip().split(' ')
(i_start, j_start, i_end, j_end) = [int(i_start), int(j_start), int(i_end), int(j_end)]
printShortestPath(n, i_start, j_start, i_end, j_end)


import sys

def printShortestPath(n, i_start, j_start, i_end, j_end):
	paths = [[''] * n for _ in range(n)]
	visited = [[-1] * n for _ in range(n)]
	if i_start == i_end and j_start == j_end:
		print('0')
		print()
		return
	visited[i_start][j_start] = 0
	stack = [(i_start, j_start)]
	while stack:
		(i, j) = stack.pop(0)
		cur_path = paths[i][j]
		directions = [('UL', (-2, -1)), ('UR', (-2, 1)), ('R', (0, 2)), ('LR', (2, 1)), ('LL', (2, -1)), ('L', (0, -2))]
		for (name, (dx, dy)) in directions:
			ni = i + dx
			nj = j + dy
			if 0 <= ni < n and 0 <= nj < n and (visited[ni][nj] == -1):
				visited[ni][nj] = visited[i][j] + 1
				paths[ni][nj] = cur_path + ' ' + name
				if ni == i_end and nj == j_end:
					print(visited[ni][nj])
					print(paths[ni][nj].strip())
					return
				stack.append((ni, nj))
	print('Impossible')
	return
n = int(input().strip())
(i_start, j_start, i_end, j_end) = input().strip().split(' ')
(i_start, j_start, i_end, j_end) = [int(i_start), int(j_start), int(i_end), int(j_end)]
printShortestPath(n, i_start, j_start, i_end, j_end)


from collections import deque

def parseInput(s):
	return [int(x) for x in s.split()]

def printShortestPath(n, i_start, j_start, i_end, j_end):
	dirs = [(-2, -1, 'UL'), (-2, 1, 'UR'), (0, 2, 'R'), (2, 1, 'LR'), (2, -1, 'LL'), (0, -2, 'L')]
	grid = [[0 for j in range(n)] for i in range(n)]
	grid[i_start][j_start] = 1
	q = deque()
	q.append([(i_start, j_start)])
	while q:
		current = q.popleft()
		(posx, posy) = (current[-1][0], current[-1][1])
		for (dx, dy, name) in dirs:
			(nx, ny) = (posx + dx, posy + dy)
			if 0 <= nx < n and 0 <= ny < n:
				if (nx, ny) == (i_end, j_end):
					print(len(current))
					print(' '.join((point[2] for point in current if len(point) == 3)) + ' ' + name)
					return
				elif grid[nx][ny]:
					pass
				else:
					grid[nx][ny] = 1
					q.append(current + [(nx, ny, name)])
	print('Impossible')
	return
n = int(input().strip())
(i_start, j_start, i_end, j_end) = input().strip().split(' ')
(i_start, j_start, i_end, j_end) = [int(i_start), int(j_start), int(i_end), int(j_end)]
printShortestPath(n, i_start, j_start, i_end, j_end)


import sys

def printShortestPath(n, i_start, j_start, i_end, j_end):
	if abs(i_end - i_start) % 2 == 1 or abs(j_end - j_start) % 2 != abs(i_end - i_start) / 2 % 2:
		print('Impossible')
		return
	re = []
	while i_start > i_end:
		if (i_start - i_end) / 2 > j_end - j_start:
			re.append('UL')
			j_start -= 1
		else:
			re.append('UR')
			j_start += 1
		i_start -= 2
	while j_start < j_end and j_end - j_start > (i_end - i_start) / 2:
		re.append('R')
		j_start += 2
	while i_end > i_start:
		if (i_end - i_start) / 2 > j_start - j_end:
			re.append('LR')
			j_start += 1
		else:
			re.append('LL')
			j_start -= 1
		i_start += 2
	while j_start > j_end:
		re.append('L')
		j_start -= 2
	print(len(re))
	print(*re)
n = int(input().strip())
(i_start, j_start, i_end, j_end) = input().strip().split(' ')
(i_start, j_start, i_end, j_end) = [int(i_start), int(j_start), int(i_end), int(j_end)]
printShortestPath(n, i_start, j_start, i_end, j_end)


import sys
map = {0: 'UL', 1: 'UR', 2: 'R', 3: 'LR', 4: 'LL', 5: 'L'}

def printShortestPath(n, i_start, j_start, i_end, j_end):
	current = {(i_start, j_start): tuple([])}
	visited = set([(i_start, j_start)])
	while current:
		new = {}
		for (i, j) in current:
			path = current[i, j]
			if i > 1:
				if j > 0:
					pos = (i - 2, j - 1)
					if pos not in visited:
						if pos in new:
							if path + (0,) < new[pos]:
								new[pos] = path + (0,)
						else:
							new[pos] = path + (0,)
				if j < n - 1:
					pos = (i - 2, j + 1)
					if pos not in visited:
						if pos in new:
							if path + (1,) < new[pos]:
								new[pos] = path + (1,)
						else:
							new[pos] = path + (1,)
			if j > 1:
				pos = (i, j - 2)
				if pos not in visited:
					if pos in new:
						if path + (5,) < new[pos]:
							new[pos] = path + (5,)
					else:
						new[pos] = path + (5,)
			if j < n - 2:
				pos = (i, j + 2)
				if pos not in visited:
					if pos in new:
						if path + (2,) < new[pos]:
							new[pos] = path + (2,)
					else:
						new[pos] = path + (2,)
			if i < n - 2:
				if j > 0:
					pos = (i + 2, j - 1)
					if pos not in visited:
						if pos in new:
							if path + (4,) < new[pos]:
								new[pos] = path + (4,)
						else:
							new[pos] = path + (4,)
				if j < n - 1:
					pos = (i + 2, j + 1)
					if pos not in visited:
						if pos in new:
							if path + (3,) < new[pos]:
								new[pos] = path + (3,)
						else:
							new[pos] = path + (3,)
		if (i_end, j_end) in new:
			path = new[i_end, j_end]
			print(len(path))
			print(' '.join([map[i] for i in path]))
			return
		current = new
		for pos in new:
			visited.add(pos)
	print('Impossible')
n = int(input().strip())
(i_start, j_start, i_end, j_end) = input().strip().split(' ')
(i_start, j_start, i_end, j_end) = [int(i_start), int(j_start), int(i_end), int(j_end)]
printShortestPath(n, i_start, j_start, i_end, j_end)


import sys
from collections import *
MOVES_STR = ('UL', 'UR', 'R', 'LR', 'LL', 'L')
MOVES = ((-2, -1), (-2, 1), (0, 2), (2, 1), (2, -1), (0, -2))

def solve(r0, c0, r1, c1, F, P, N):
	q = deque([(r0, c0)])
	F[r0][c0] = 0
	while q:
		(r, c) = q.popleft()
		f = F[r][c]
		p = P[r][c]
		if r == r1 and c == c1:
			return (f, p)
		for (i, dd) in enumerate(MOVES):
			(nr, nc) = (r + dd[0], c + dd[1])
			if nr < 0 or nc < 0 or nr >= N or (nc >= N):
				continue
			if F[nr][nc] == None:
				F[nr][nc] = f + 1
				P[nr][nc] = p + ' ' + MOVES_STR[i]
				q.append((nr, nc))
	return (0, [])
N = int(input().strip())
F = [[None] * N for _ in range(N)]
P = [[''] * N for _ in range(N)]
(r0, c0, r1, c1) = map(int, input().strip().split(' '))
res = solve(r0, c0, r1, c1, F, P, N)
if res[0] == 0:
	print('Impossible')
else:
	print(res[0])
	print(res[1][1:])


import sys
from collections import deque

def printShortestPath(n, i_start, j_start, i_end, j_end):
	dp = [[(None, float('inf')) for i in range(n)] for _ in range(n)]
	count = 0
	movei = [-2, -2, 0, 2, 2, 0]
	movej = [-1, 1, 2, 1, -1, -2]
	word = ['UL', 'UR', 'R', 'LR', 'LL', 'L']
	bfs = deque()
	bfs.append((i_start, j_start))
	dp[i_start][j_start] = ('', 0)
	while len(bfs) > 0:
		(i, j) = bfs.popleft()
		chars = dp[i][j][0]
		for index in range(len(word)):
			(newindexi, newindexj, count) = (i + movei[index], j + movej[index], dp[i][j][1] + 1)
			if newindexi >= 0 and newindexi < n and (newindexj >= 0) and (newindexj < n):
				if dp[newindexi][newindexj][1] > count:
					dp[newindexi][newindexj] = (chars + str(index), count)
					bfs.append((newindexi, newindexj))
				elif dp[newindexi][newindexj][1] == count:
					if chars + str(index) < dp[newindexi][newindexj][0]:
						dp[newindexi][newindexj] = (chars + str(index), count)
						bfs.append((newindexi, newindexj))
	if dp[i_end][j_end][0] == None:
		print('Impossible')
	else:
		print(dp[i_end][j_end][1])
		for i in dp[i_end][j_end][0]:
			print(word[int(i)], end=' ')
n = int(input().strip())
(i_start, j_start, i_end, j_end) = input().strip().split(' ')
(i_start, j_start, i_end, j_end) = [int(i_start), int(j_start), int(i_end), int(j_end)]
printShortestPath(n, i_start, j_start, i_end, j_end)


moves_labels = ['UL', 'UR', 'R', 'LR', 'LL', 'L']
moves = [(-2, -1), (-2, 1), (0, 2), (2, 1), (2, -1), (0, -2)]

def move_to_next(pos, move):
	next_pos = (pos[0] + move[0], pos[1] + move[1])
	return next_pos

def is_valid_pos(pos, n):
	inside_x = 0 <= pos[1] <= n
	inside_y = 0 <= pos[0] <= n
	return inside_x and inside_y

def is_destination(pos_a, pos_b):
	return pos_a == pos_b

def printShortestPath(n, i_start, j_start, i_end, j_end):
	start = (i_start, j_start)
	end = (i_end, j_end)
	to_visit_from = [(start, [])]
	visited = set()
	for node_path in to_visit_from:
		node = node_path[0]
		path = node_path[1]
		if node in visited:
			continue
		if is_destination(node, end):
			final_path = ' '.join(path)
			print(len(path))
			print(final_path)
			return
		visited.add(node)
		for (i, m) in enumerate(moves):
			next_position = move_to_next(node, m)
			if is_valid_pos(next_position, n):
				next_path = path.copy()
				next_path.append(moves_labels[i])
				next_node_path = (next_position, next_path)
				to_visit_from.append(next_node_path)
	print('Impossible')
n = int(input().strip())
(i_start, j_start, i_end, j_end) = input().strip().split(' ')
(i_start, j_start, i_end, j_end) = [int(i_start), int(j_start), int(i_end), int(j_end)]
printShortestPath(n, i_start, j_start, i_end, j_end)


import sys
from collections import deque

def next_possible_positions(n, row, col):
	possible_positions = []
	for (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)]:
		if r >= 0 and r < n and (c >= 0) and (c < n):
			possible_positions.append((move, r, c))
	return possible_positions

def backtrack_cell(r, c, move):
	if move == 'UL':
		return (r + 2, c + 1)
	if move == 'UR':
		return (r + 2, c - 1)
	if move == 'R':
		return (r, c - 2)
	if move == 'LR':
		return (r - 2, c - 1)
	if move == 'LL':
		return (r - 2, c + 1)
	if move == 'L':
		return (r, c + 2)
	return None

def backtracked_path(matrix, r_start, c_start, r_end, c_end):
	moves = deque()
	(r, c) = (r_end, c_end)
	while not (r == r_start and c == c_start):
		move = matrix[r][c]
		moves.appendleft(move)
		(r, c) = backtrack_cell(r, c, move)
	return moves

def printShortestPath(n, r_start, c_start, r_end, c_end):
	next_to_visit = deque()
	next_to_visit.append((r_start, c_start))
	matrix = [[None for _ in range(n)] for _ in range(n)]
	while len(next_to_visit) > 0:
		(c_r, c_c) = next_to_visit.popleft()
		for (move, n_r, n_c) in next_possible_positions(n, c_r, c_c):
			if matrix[n_r][n_c] is not None:
				continue
			matrix[n_r][n_c] = move
			if (n_r, n_c) == (r_end, c_end):
				moves = backtracked_path(matrix, r_start, c_start, r_end, c_end)
				print(len(moves))
				print(' '.join(moves))
				return
			next_to_visit.append((n_r, n_c))
	print('Impossible')
n = int(input().strip())
(i_start, j_start, i_end, j_end) = input().strip().split(' ')
(i_start, j_start, i_end, j_end) = [int(i_start), int(j_start), int(i_end), int(j_end)]
printShortestPath(n, i_start, j_start, i_end, j_end)


from collections import defaultdict as dd
n = int(input())
a = n
(s1, s2, e1, e2) = [int(i) for i in input().split()]
(r1, r2) = (e1, e2)
g = dd(list)
for i in range(n):
	for j in range(n):
		if i - 2 >= 0 and j - 1 >= 0:
			g[i, j].append(((i - 2, j - 1), 'UL'))
		if i - 2 >= 0 and j + 1 < a:
			g[i, j].append(((i - 2, j + 1), 'UR'))
		if i < a and j + 2 < a:
			g[i, j].append(((i, j + 2), 'R'))
		if i + 2 < a and j + 1 < a:
			g[i, j].append(((i + 2, j + 1), 'LR'))
		if i + 2 < a and j - 1 >= 0:
			g[i, j].append(((i + 2, j - 1), 'LL'))
		if i < a and j - 2 >= 0:
			g[i, j].append(((i, j - 2), 'L'))
d = []
ch = [[0 for i in range(a + 1)] for j in range(a + 1)]
dis = [[[] for i in range(a + 1)] for j in range(a + 1)]

def bfs(i, j):
	ch[s1][s2] = 1
	d.append([s1, s2])
	while d:
		k = d.pop(0)
		for i in g[k[0], k[1]]:
			if ch[i[0][0]][i[0][1]] == 0:
				ch[i[0][0]][i[0][1]] = 1
				d.append([i[0][0], i[0][1]])
				dis[i[0][0]][i[0][1]] = [k[0], k[1]]
		if ch[e1][e2] == 1:
			break

def ret(i, j, k, l):
	if k + 2 == i and l + 1 == j:
		return 'UL'
	elif k + 2 == i and l - 1 == j:
		return 'UR'
	elif k == i and l - 2 == j:
		return 'R'
	elif k - 2 == i and l - 1 == j:
		return 'LR'
	elif k - 2 == i and l + 1 == j:
		return 'LL'
	elif k == i and l + 2 == j:
		return 'L'
bfs(s1, s2)
path = []
while len(dis[e1][e2]) != 0:
	path.append(dis[e1][e2])
	(e1, e2) = dis[e1][e2]
if len(path) == 0:
	print('Impossible')
else:
	print(len(path))
	k = []
	path1 = path[::-1] + [[r1, r2]]
	for i in range(len(path1) - 1):
		k.append(ret(path1[i][0], path1[i][1], path1[i + 1][0], path1[i + 1][1]))
	print(*k)


import sys
from collections import deque
n = int(input())
(sy, sx, ey, ex) = map(int, input().split())
Q = deque()
Q.append(('', sx, sy, 0))
moves = [(-1, -2), (1, -2), (2, 0), (1, 2), (-1, 2), (-2, 0)]
name = {(-1, -2): 'UL ', (1, -2): 'UR ', (2, 0): 'R ', (1, 2): 'LR ', (-1, 2): 'LL ', (-2, 0): 'L '}
M = {}
while Q:
	(way, x, y, d) = Q.popleft()
	if x == ex and y == ey:
		print(d)
		print(way.strip())
		sys.exit(0)
	if (x, y) in M:
		continue
	M[x, y] = d
	for (dx, dy) in moves:
		if 0 <= x + dx < n and 0 <= y + dy < n:
			Q.append((way + name[dx, dy], x + dx, y + dy, d + 1))
print('Impossible')


from collections import deque
from collections import namedtuple

class Position(namedtuple('Position', 'i j move')):

	def __eq__(self, other):
		return self.i == other.i and self.j == other.j

	def next(self, n):
		return 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')])

def printShortestPath(n, i_start, j_start, i_end, j_end):
	start = Position(i_start, j_start, None)
	end = Position(i_end, j_end, None)
	prev = []
	visited = []
	for i in range(n):
		prev.append([])
		visited.append([])
		for j in range(n):
			prev[i].append(None)
			visited[i].append(False)
	q = deque()
	q.append(Position(i_start, j_start, None))
	while len(q) > 0:
		u = q.popleft()
		visited[u.i][u.j] = True
		if u == end:
			path = [u.move]
			while prev[u.i][u.j] != None:
				if prev[u.i][u.j].move != None:
					path.append(prev[u.i][u.j].move)
				u = prev[u.i][u.j]
			print(len(path))
			print(*path[::-1], sep=' ')
			return
		for v in u.next(n):
			if not visited[v.i][v.j]:
				visited[v.i][v.j] = True
				prev[v.i][v.j] = u
				q.append(v)
	print('Impossible')
n = int(input().strip())
(i_start, j_start, i_end, j_end) = map(int, input().strip().split(' '))
printShortestPath(n, i_start, j_start, i_end, j_end)


import sys

def printShortestPath(n, i_start, j_start, i_end, j_end):
	j = j_start
	iDiff = i_end - i_start
	jDiff = j_end - j_start
	numSteps = 0
	string = ''
	if iDiff % 2 == 1 or (iDiff // 2 + jDiff) % 2 == 1:
		print('Impossible')
	else:
		while iDiff != 0 or jDiff != 0:
			if iDiff > 0:
				if j == n - 1 or jDiff <= -iDiff // 2:
					string += 'LL '
					numSteps += 1
					j -= 1
					iDiff -= 2
					jDiff += 1
				elif jDiff <= iDiff // 2:
					string += 'LR '
					numSteps += 1
					j += 1
					iDiff -= 2
					jDiff -= 1
				else:
					string += 'R '
					numSteps += 1
					j += 2
					jDiff -= 2
			elif iDiff < 0:
				if j == 0 or jDiff >= -iDiff // 2:
					string += 'UR '
					numSteps += 1
					j += 1
					iDiff += 2
					jDiff -= 1
				else:
					string += 'UL '
					numSteps += 1
					j -= 1
					iDiff += 2
					jDiff += 1
			elif jDiff > 0:
				string += 'R '
				numSteps += 1
				j += 2
				jDiff -= 2
			else:
				string += 'L '
				numSteps += 1
				j -= 2
				jDiff += 2
		print(numSteps)
		print(string.rstrip())
n = int(input().strip())
(i_start, j_start, i_end, j_end) = input().strip().split(' ')
(i_start, j_start, i_end, j_end) = [int(i_start), int(j_start), int(i_end), int(j_end)]
printShortestPath(n, i_start, j_start, i_end, j_end)


from collections import deque
import sys
m = ['UL', 'UR', 'R', 'LR', 'LL', 'L']
di = [-2, -2, +0, +2, +2, +0]
dj = [-1, +1, +2, +1, -1, -2]
dp = list(zip(di, dj, m))

def printShortestPath(n, ibeg, jbeg, iend, jend):
	D = [n * [None] for _ in range(n)]
	P = [n * [None] for _ in range(n)]
	D[ibeg][jbeg] = 0
	Q = deque([(ibeg, jbeg)])
	while Q:
		(i0, j0) = Q.popleft()
		d = D[i0][j0] + 1
		for (di, dj, m) in dp:
			(i, j) = (i0 + di, j0 + dj)
			if 0 <= i < n and 0 <= j < n:
				if P[i][j] is None:
					Q.append((i, j))
				if D[i][j] is None or d < D[i][j]:
					(D[i][j], P[i][j]) = (d, (i0, j0, m))
	(i, j, M) = (iend, jend, [])
	d = D[i][j]
	if d is None:
		print('Impossible')
	else:
		print(d)
		while P[i][j]:
			(i, j, m) = P[i][j]
			M.append(m)
		print(*M[::-1])
	return
n = int(input().strip())
(i_start, j_start, i_end, j_end) = input().strip().split(' ')
(i_start, j_start, i_end, j_end) = [int(i_start), int(j_start), int(i_end), int(j_end)]
printShortestPath(n, i_start, j_start, i_end, j_end)


import sys

def printShortestPath(n, i_start, j_start, i_end, j_end):
	INF = 1e+18
	MOVES = [[-2, -1, 'UL'], [-2, +1, 'UR'], [0, +2, 'R'], [+2, +1, 'LR'], [+2, -1, 'LL'], [0, -2, 'L']]
	d = [[INF] * n for x in range(n)]
	d[i_end][j_end] = 0
	s = [[i_end, j_end]]
	k = 0
	while k < len(s):
		(i, j) = s[k]
		k += 1
		for (di, dj, c) in MOVES:
			if 0 <= i + di < n and 0 <= j + dj < n and (d[i + di][j + dj] == INF):
				d[i + di][j + dj] = d[i][j] + 1
				s += [[i + di, j + dj]]
	if d[i_start][j_start] == INF:
		print('Impossible')
		return
	print(d[i_start][j_start])
	while i_start != i_end or j_start != j_end:
		for (di, dj, c) in MOVES:
			if 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):
				print(c, end=' ')
				i_start += di
				j_start += dj
				break
n = int(input().strip())
(i_start, j_start, i_end, j_end) = input().strip().split(' ')
(i_start, j_start, i_end, j_end) = [int(i_start), int(j_start), int(i_end), int(j_end)]
printShortestPath(n, i_start, j_start, i_end, j_end)


from queue import Queue

def shortedPath(size, rootx, rooty, endx, endy):
	dis = [[[] for i in range(size)] for j in range(size)]
	dis[rootx][rooty].append('')
	q = Queue()
	q.put([rootx, rooty])
	while not q.empty():
		(curx, cury) = q.get()
		for i in range(len(move)):
			x = curx + move[i][1]
			y = cury + move[i][0]
			if x < 0 or x >= size:
				continue
			if y < 0 or y >= size:
				continue
			if len(dis[x][y]) != 0:
				continue
			dis[x][y] = dis[curx][cury] + [move[i][2]]
			if x == endx and y == endy:
				return dis[x][y]
			q.put([x, y])
	return dis[endx][endy]

def main():
	size = int(input())
	(rootx, rooty, endx, endy) = [int(i) for i in input().split(' ')]
	res = shortedPath(size, rootx, rooty, endx, endy)
	if len(res) == 0:
		print('Impossible')
		return
	res.remove('')
	print(len(res))
	print(' '.join(res))
move = [[-1, -2, 'UL'], [1, -2, 'UR'], [2, 0, 'R'], [1, 2, 'LR'], [-1, 2, 'LL'], [-2, 0, 'L']]
main()


import sys
from collections import namedtuple
Position = namedtuple('Position', ('i', 'j'))

def printShortestPath(n, i_start, j_start, i_end, j_end):
	if i_start % 2 != i_end % 2:
		print('Impossible')
		return
	Move = namedtuple('Move', ('name', 'delta_i', 'delta_j'))
	s = Position(i_start, j_start)
	t = Position(i_end, j_end)
	moves = [Move('UL', -2, -1), Move('UR', -2, 1), Move('R', 0, 2), Move('LR', 2, 1), Move('LL', 2, -1), Move('L', 0, -2)]
	final_moves = BFS(n, moves, s, t)
	if final_moves is False:
		print('Impossible')
	else:
		print(len(final_moves))
		print(*final_moves)

def BFS(n, moves, s, t):
	if s == t:
		return []
	parent = {s: None}
	move_dict = {}
	end = False
	frontier = [s]
	while frontier and (not end):
		next_frontier = []
		for pos in frontier:
			for m in moves:
				new_pos = Position(pos.i + m.delta_i, pos.j + m.delta_j)
				if new_pos.i < 0 or new_pos.i >= n or new_pos.j < 0 or (new_pos.j >= n):
					continue
				if new_pos.i + 1 == t.i or new_pos.i - 1 == t.i:
					return False
				if new_pos not in parent:
					parent[new_pos] = pos
					move_dict[new_pos] = m.name
					next_frontier.append(new_pos)
					if new_pos == t:
						end = True
						break
			if end:
				break
		frontier = next_frontier
	if t not in parent:
		return False
	final_moves = []
	current = t
	while current in move_dict:
		final_moves.append(move_dict[current])
		current = parent[current]
	final_moves.reverse()
	return final_moves
n = int(input().strip())
(i_start, j_start, i_end, j_end) = input().strip().split(' ')
(i_start, j_start, i_end, j_end) = [int(i_start), int(j_start), int(i_end), int(j_end)]
printShortestPath(n, i_start, j_start, i_end, j_end)


from collections import deque

def printShortestPath(n, i_start, j_start, i_end, j_end):
	todo = deque([(i_start, j_start, [])])
	visited = [list([False] * n) for _ in range(n)]
	while todo:
		(i, j, path) = todo.popleft()
		if i == i_end and j == j_end:
			print(len(path))
			print(*path)
			return
		for (di, dj, dir) in [(-2, -1, 'UL'), (-2, 1, 'UR'), (0, 2, 'R'), (2, 1, 'LR'), (2, -1, 'LL'), (0, -2, 'L')]:
			(i2, j2) = (i + di, j + dj)
			if 0 <= i2 < n and 0 <= j2 < n and (not visited[i2][j2]):
				todo.append((i2, j2, path + [dir]))
				visited[i2][j2] = True
	print('Impossible')
n = int(input().strip())
(i_start, j_start, i_end, j_end) = input().strip().split(' ')
(i_start, j_start, i_end, j_end) = [int(i_start), int(j_start), int(i_end), int(j_end)]
printShortestPath(n, i_start, j_start, i_end, j_end)


INF = float('inf')
moves = [('UL', -2, -1), ('UR', -2, 1), ('R', 0, 2), ('LR', 2, 1), ('LL', 2, -1), ('L', 0, -2)]
n = int(input())
(i0, j0, i1, j1) = map(int, input().split())

def adj(i, j):
	return ((desc, i + di, j + dj) for (desc, di, dj) in moves if 0 <= i + di < n and 0 <= j + dj < n)

def bfs(i0, j0):
	d = [[INF for _ in range(n)] for _ in range(n)]
	d[i0][j0] = 0
	(q, qi) = ([(i0, j0)], 0)
	while qi < len(q):
		(i, j) = q[qi]
		for (_, ii, jj) in adj(i, j):
			if d[ii][jj] == INF:
				d[ii][jj] = d[i][j] + 1
				q.append((ii, jj))
		qi += 1
	return d

def path(i, j, i1, j1):
	for _ in range(best):
		(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))
		yield desc
(d0, d1) = (bfs(i0, j0), bfs(i1, j1))
best = d0[i1][j1]
if best == INF:
	print('Impossible')
else:
	print(best)
	print(' '.join(path(i0, j0, i1, j1)))


def printShortestPath(n, i_start, j_start, i_end, j_end):
	x_moves = [-1, 1, 2, 1, -1, -2]
	y_moves = [-2, -2, 0, 2, 2, 0]
	actions = ['UL', 'UR', 'R', 'LR', 'LL', 'L']
	target = (j_end, i_end)
	done = False
	visited = {(j_start, i_start): (j_start, i_start, -1)}
	frontier = [(j_start, i_start)]
	steps = 0
	while len(frontier) != 0:
		steps += 1
		new_frontier = []
		for i in frontier:
			for j in range(6):
				x = i[0] + x_moves[j]
				y = i[1] + y_moves[j]
				if x < 0 or x > n - 1 or y < 0 or (y > n - 1):
					continue
				if (x, y) in visited:
					continue
				visited[x, y] = (i[0], i[1], j)
				if (x, y) == target:
					done = True
					break
				new_frontier.append((x, y))
			if done:
				new_frontier = []
				break
		frontier = new_frontier
	if done:
		print(steps)
		pos = (j_end, i_end, -1)
		r = []
		while not (pos[0] == j_start and pos[1] == i_start):
			pos = visited[pos[0], pos[1]]
			r += [actions[pos[2]]]
		print(' '.join(r[::-1]))
	else:
		print('Impossible')
n = int(input().strip())
(i_start, j_start, i_end, j_end) = input().strip().split(' ')
(i_start, j_start, i_end, j_end) = [int(i_start), int(j_start), int(i_end), int(j_end)]
printShortestPath(n, i_start, j_start, i_end, j_end)


import sys

def mapper(s):
	m = {'UL': (0, 'UL'), 'UR': (1, 'UR'), 'R': (2, 'R'), 'LR': (3, 'LR'), 'LL': (4, 'LL'), 'L': (5, 'L')}
	return m[s]

def printShortestPath(n, i_start, j_start, i_end, j_end):
	y = j_end - j_start
	x = i_end - i_start
	if abs(y) % 2 != 0:
		print('Impossible')
		return
	st = []
	count = 0
	while y != 0:
		if y <= 0:
			j_start -= 2
			if x <= 0:
				i_start -= 1
				st.append('UL')
			else:
				i_start += 1
				st.append('UR')
		else:
			j_start += 2
			if x < 0:
				i_start -= 1
				st.append('LL')
			else:
				i_start += 1
				st.append('LR')
		if i_start < 0 or i_start == n:
			print('Impossible')
			return
		y = j_end - j_start
		x = i_end - i_start
		count += 1
	if abs(x) % 2 != 0:
		print('Impossible')
		return
	for i in range(abs(x) // 2):
		if x < 0:
			st.append('L')
		else:
			st.append('R')
		count += 1
	print(count)
	st = list(map(mapper, st))
	st.sort()
	st = list(map(lambda x: x[1], st))
	print(*st)
n = int(input().strip())
(i_start, j_start, i_end, j_end) = input().strip().split(' ')
(i_start, j_start, i_end, j_end) = [int(i_start), int(j_start), int(i_end), int(j_end)]
printShortestPath(n, j_start, i_start, j_end, i_end)


import sys
import math
from collections import namedtuple
sys.setrecursionlimit(10000)
P = namedtuple('Pos', 'r c')
moves = [P(-2, -1), P(-2, 1), P(0, 2), P(2, 1), P(2, -1), P(0, -2)]
names = {P(-2, -1): 'UL', P(-2, 1): 'UR', P(0, 2): 'R', P(2, 1): 'LR', P(2, -1): 'LL', P(0, -2): 'L'}

def shortest(start, end, N, mem):
	if start == end:
		return 0
	if mem[start.r][start.c] is not None:
		return mem[start.r][start.c][0]
	mn = math.inf
	mem[start.r][start.c] = (math.inf, None)
	bst = None
	for move in moves:
		n = P(start.r + move.r, start.c + move.c)
		d1 = abs(n.c - end.c) - abs(start.c - end.c)
		d2 = abs(n.r - end.r) - abs(start.r - end.r)
		if n.r >= 0 and n.r < N and (n.c >= 0) and (n.c < N) and (d1 <= 1) and (d2 <= 1):
			ans = 1 + shortest(n, end, N, mem)
			if ans < mn:
				mn = ans
				bst = move
	mem[start.r][start.c] = (mn, bst)
	return mn

def printShortestPath(n, i_start, j_start, i_end, j_end):
	start = P(i_start, j_start)
	end = P(i_end, j_end)
	mem = [[None for i in range(n)] for u in range(n)]
	s = shortest(start, end, n, mem=mem)
	if s == math.inf:
		print('Impossible')
		return
	print(s)
	m = []
	p = start
	while p != end:
		(_, b) = mem[p.r][p.c]
		assert b in names
		m.append(names[b])
		p = P(p.r + b.r, p.c + b.c)
	print(' '.join(m))
n = int(input().strip())
(i_start, j_start, i_end, j_end) = input().strip().split(' ')
(i_start, j_start, i_end, j_end) = [int(i_start), int(j_start), int(i_end), int(j_end)]
printShortestPath(n, i_start, j_start, i_end, j_end)


import sys

def printShortestPath(n, i_start, j_start, i_end, j_end):
	moves = 0
	(UL, UR, R, LR, LL, L) = (0, 0, 0, 0, 0, 0)
	v = i_start - i_end
	h = j_start - j_end

	def move():
		nonlocal h, v, moves, UL, UR, R, LR, LL, L
		while h >= 0 and v > 0:
			UL += 1
			v -= 2
			h -= 1
			moves += 1
		while h < 0 and v > 0:
			UR += 1
			v -= 2
			h += 1
			moves += 1
		while h < 0 and v == 0:
			R += 1
			h += 2
			moves += 1
		while h <= 0 and v < 0:
			LR += 1
			v += 2
			h += 1
			moves += 1
		while h > 0 and v < 0:
			LL += 1
			v += 2
			h -= 1
			moves += 1
		while h > 0 and v == 0:
			L += 1
			h -= 2
			moves += 1
	if abs(v) % 2 == 1:
		print('Impossible')
	elif h % 2 != v / 2 % 2:
		print('Impossible')
	else:
		while (h, v) != (0, 0):
			move()
		print(moves)
		print('UL ' * UL + 'UR ' * UR + 'R ' * R + 'LR ' * LR + 'LL ' * LL + 'L ' * L)
n = int(input().strip())
(i_start, j_start, i_end, j_end) = input().strip().split(' ')
(i_start, j_start, i_end, j_end) = [int(i_start), int(j_start), int(i_end), int(j_end)]
printShortestPath(n, i_start, j_start, i_end, j_end)


import sys

def printShortestPath(n, starty, startx, i_end, j_end):
	visited = [[False for x in range(n)] for y in range(n)]
	parent = [[[-1, -1] for x in range(n)] for y in range(n)]
	queue = []
	queue.append([starty, startx])
	visited[starty][startx] = True
	while queue:
		if queue[0] == [i_end, j_end]:
			break
		s = queue.pop(0)
		if s[1] >= 1 and s[0] >= 2 and (not visited[s[0] - 2][s[1] - 1]):
			queue.append([s[0] - 2, s[1] - 1])
			visited[s[0] - 2][s[1] - 1] = True
			parent[s[0] - 2][s[1] - 1] = s
		if s[1] <= n - 2 and s[0] >= 2 and (not visited[s[0] - 2][s[1] + 1]):
			queue.append([s[0] - 2, s[1] + 1])
			visited[s[0] - 2][s[1] + 1] = True
			parent[s[0] - 2][s[1] + 1] = s
		if s[1] <= n - 3 and (not visited[s[0]][s[1] + 2]):
			queue.append([s[0], s[1] + 2])
			visited[s[0]][s[1] + 2] = True
			parent[s[0]][s[1] + 2] = s
		if s[1] <= n - 2 and s[0] <= n - 3 and (not visited[s[0] + 2][s[1] + 1]):
			queue.append([s[0] + 2, s[1] + 1])
			visited[s[0] + 2][s[1] + 1] = True
			parent[s[0] + 2][s[1] + 1] = s
		if s[1] >= 1 and s[0] <= n - 3 and (not visited[s[0] + 2][s[1] - 1]):
			queue.append([s[0] + 2, s[1] - 1])
			visited[s[0] + 2][s[1] - 1] = True
			parent[s[0] + 2][s[1] - 1] = s
		if s[1] >= 2 and (not visited[s[0]][s[1] - 2]):
			queue.append([s[0], s[1] - 2])
			visited[s[0]][s[1] - 2] = True
			parent[s[0]][s[1] - 2] = s
	if not visited[i_end][j_end]:
		print('Impossible')
		return
	path = [[i_end, j_end]]
	tmp = path[0]
	while tmp != [starty, startx]:
		tmp = parent[tmp[0]][tmp[1]]
		path.append(tmp)
	path = path[::-1]
	print(len(path) - 1)
	for i in range(len(path) - 1):
		if path[i][1] > path[i + 1][1]:
			if path[i][0] < path[i + 1][0]:
				print('LL', end=' ')
			elif path[i][0] > path[i + 1][0]:
				print('UL', end=' ')
			else:
				print('L', end=' ')
		elif path[i][0] < path[i + 1][0]:
			print('LR', end=' ')
		elif path[i][0] > path[i + 1][0]:
			print('UR', end=' ')
		else:
			print('R', end=' ')
	print()
n = int(input().strip())
(i_start, j_start, i_end, j_end) = input().strip().split(' ')
(i_start, j_start, i_end, j_end) = [int(i_start), int(j_start), int(i_end), int(j_end)]
printShortestPath(n, i_start, j_start, i_end, j_end)


import sys
from queue import Queue

def print_path(i_start, j_start, i_end, j_end, parent):
	path = []
	(i, j) = (i_end, j_end)
	while (i, j) != (i_start, j_start):
		(i, j, m) = parent[i, j]
		path.append(m)
	print(' '.join((m for m in path[::-1])))

def printShortestPath(n, i_start, j_start, i_end, j_end):
	row = [-2, -2, 0, 2, 2, 0]
	col = [-1, 1, 2, 1, -1, -2]
	move_names = ['UL', 'UR', 'R', 'LR', 'LL', 'L']
	parent = {}
	q = Queue()
	marked = {(i_start, j_start)}
	q.put((i_start, j_start, 0))
	while not q.empty():
		(i_root, j_root, d) = q.get()
		if (i_root, j_root) == (i_end, j_end):
			print(d)
			print_path(i_start, j_start, i_end, j_end, parent)
			return
		for k in range(6):
			(i, j) = (i_root + row[k], j_root + col[k])
			if 0 <= i < n and 0 <= j < n and ((i, j) not in marked):
				marked.add((i, j))
				parent[i, j] = (i_root, j_root, move_names[k])
				q.put((i, j, d + 1))
	print('Impossible')
n = int(input().strip())
(i_start, j_start, i_end, j_end) = input().strip().split(' ')
(i_start, j_start, i_end, j_end) = [int(i_start), int(j_start), int(i_end), int(j_end)]
printShortestPath(n, i_start, j_start, i_end, j_end)


import sys
moves = ['UL', 'UR', 'R', 'LR', 'LL', 'L']
coords = [(-2, -1), (-2, 1), (0, 2), (2, 1), (2, -1), (0, -2)]

def printShortestPath(n, i_start, j_start, i_end, j_end):
	if i_end - i_start & 1:
		print('Impossible')
	else:
		path = []
		dist = abs(i_start - i_end) // 2
		i = i_start
		j = j_start
		for d in range(dist):
			if i < i_end:
				if j <= j_end:
					path.append('LR')
					i += 2
					j += 1
				else:
					path.append('LL')
					i += 2
					j -= 1
			elif i > i_end:
				if j >= j_end:
					path.append('UL')
					i -= 2
					j -= 1
				else:
					path.append('UR')
					i -= 2
					j += 1
		if j != j_end:
			dist = abs(j - j_end)
			if dist & 1:
				print('Impossible')
				return
			for d in range(dist):
				if j < j_end:
					path.append('R')
					j += 2
				elif j > j_end:
					path.append('L')
					j -= 2
		print(len(path))
		print(' '.join(sorted(path, key=moves.index)))
n = int(input().strip())
(i_start, j_start, i_end, j_end) = input().strip().split(' ')
(i_start, j_start, i_end, j_end) = [int(i_start), int(j_start), int(i_end), int(j_end)]
printShortestPath(n, i_start, j_start, i_end, j_end)


import sys, math

def coord_to_inx(n, c):
	return c[0] * n + c[1]

def inx_to_coord(n, i):
	return (int(math.floor(i / n)), i % n)

def move_desc(from_, to_):
	row = from_[0] - to_[0]
	col = from_[1] - to_[1]
	if row == 2:
		if col == 1:
			return 'UL'
		if col == -1:
			return 'UR'
	if row == 0:
		if col == 2:
			return 'L'
		if col == -2:
			return 'R'
	if row == -2:
		if col == 1:
			return 'LL'
		if col == -1:
			return 'LR'
	raise 'invalid coords: ' + str(from_) + ' ' + str(to_)

def adj(n, v, quarter):
	(row, col) = v
	if row - 2 >= 0:
		if col - 1 >= 0:
			yield (row - 2, col - 1)
		if col + 1 < n:
			yield (row - 2, col + 1)
	if col + 2 < n:
		yield (row, col + 2)
	if row + 2 < n:
		if col + 1 < n:
			yield (row + 2, col + 1)
		if col - 1 >= 0:
			yield (row + 2, col - 1)
	if col - 2 >= 0:
		yield (row, col - 2)

def get_quarter(s, t):
	(s_row, s_col) = s
	(t_row, t_col) = t
	if t_row <= s_row:
		if t_col >= s_col:
			return 1
		else:
			return 2
	elif t_col >= s_col:
		return 3
	else:
		return 4

def printShortestPath(n, i_start, j_start, i_end, j_end):
	if i_start % 2 != i_end % 2:
		print('Impossible')
		exit()
	is_t_same_row_kind = abs(i_start - i_end) // 2 % 2 == 0
	if is_t_same_row_kind and j_start % 2 != j_end % 2:
		print('Impossible')
		exit()
	if not is_t_same_row_kind and j_start % 2 == j_end % 2:
		print('Impossible')
		exit()
	s = (i_start, j_start)
	t = (i_end, j_end)
	marked = set()
	q = []
	pathto = [-1] * (n * n)
	q.append(s)
	found = False
	quarter = get_quarter(s, t)
	while len(q) > 0:
		v = q.pop()
		v_inx = coord_to_inx(n, v)
		for w in adj(n, v, quarter):
			if w not in marked:
				marked.add(w)
				q.insert(0, w)
				pathto[coord_to_inx(n, w)] = v_inx
				if w == t:
					found = True
					break
		if found:
			break
	if not found:
		raise 'error'
	path = []
	v = t
	while True:
		w = inx_to_coord(n, pathto[coord_to_inx(n, v)])
		path += [move_desc(w, v)]
		v = w
		if v == s:
			break
	print(len(path))
	print(' '.join(reversed(path)))
n = int(input().strip())
(i_start, j_start, i_end, j_end) = input().strip().split(' ')
(i_start, j_start, i_end, j_end) = [int(i_start), int(j_start), int(i_end), int(j_end)]
printShortestPath(n, i_start, j_start, i_end, j_end)


from collections import deque, defaultdict

def calc_pos(move, x_pos, y_pos):
	if move == 'UL':
		return (x_pos - 2, y_pos - 1)
	if move == 'UR':
		return (x_pos - 2, y_pos + 1)
	if move == 'R':
		return (x_pos, y_pos + 2)
	if move == 'LR':
		return (x_pos + 2, y_pos + 1)
	if move == 'LL':
		return (x_pos + 2, y_pos - 1)
	if move == 'L':
		return (x_pos, y_pos - 2)

def bfs(a, x_s, y_s, x_e, y_e, visit):
	prev = defaultdict()
	moves = ['UL', 'UR', 'R', 'LR', 'LL', 'L']
	queue = deque()
	queue.append((x_s, y_s))
	visit[x_s][y_s] = True
	data[x_s][y_s] = 0
	while queue:
		(x_s, y_s) = queue.popleft()
		if x_s == y_s and x_e == y_e:
			return prev
		for k in moves:
			if is_safe(k, x_s, y_s, visit):
				(a, b) = calc_pos(k, x_s, y_s)
				data[a][b] = data[x_s][y_s] + 1
				prev[a, b] = [[x_s, y_s], k]
				queue.append((a, b))
				visit[a][b] = True
	return prev

def is_safe(mov, i, j, visit):
	(i, j) = calc_pos(mov, i, j)
	if n > i >= 0 and n > j >= 0 and (visit[i][j] == False):
		return True
	return False
n = int(input())
(x_start, y_start, x_end, y_end) = map(int, input().split())
data = [[0 for i in range(n)] for j in range(n)]
visit = [[False for i in range(n)] for j in range(n)]
prevv = bfs(data, x_start, y_start, x_end, y_end, visit)
if data[x_end][y_end] != 0:
	print(data[x_end][y_end])
	ans = []
	while not (x_start == x_end and y_start == y_end):
		ans.append(prevv[x_end, y_end][1])
		(x_end, y_end) = prevv[x_end, y_end][0]
	for i in range(1, len(ans) + 1):
		print(ans[-i], end=' ')
else:
	print('Impossible')


from collections import defaultdict
import sys
N = 0

def minuser():
	return -1
DP = defaultdict(minuser)

def findPath(x, y, cost, moves):
	if y % 2 != 0 or (x % 2 == 1 and y == 0):
		print('Impossible')
	elif x == 0 and y == 0:
		print(cost)
		nstr = ''
		priors = []
		moves = sorted(moves)[::-1]
		for elem in moves:
			nstr += elem + ' '
		print(nstr)
	elif x < 0 and y < -1:
		moves.append('UL')
		findPath(x + 1, y + 2, cost + 1, moves)
	elif x > 0 and y < -1:
		moves.append('UR')
		findPath(x - 1, y + 2, cost + 1, moves)
	elif x > 0 and y == 0:
		moves.append('R')
		findPath(x - 2, y, cost + 1, moves)
	elif x > 0 and y > 1:
		moves.append('LR')
		findPath(x - 1, y - 2, cost + 1, moves)
	elif x < 0 and y > 1:
		moves.append('LL')
		findPath(x + 1, y - 2, cost + 1, moves)
	elif x < 0 and y == 0:
		moves.append('L')
		findPath(x + 2, y, cost + 1, moves)
	elif y > 1:
		moves.append('LR')
		findPath(x - 1, y - 2, cost + 1, moves)
	elif y < -1:
		moves.append('UL')
		findPath(x - 1, y + 2, cost + 1, moves)

def printShortestPath(n, i_start, j_start, i_end, j_end):
	x = i_end - i_start
	y = j_end - j_start
	findPath(y, x, 0, [])
n = int(input().strip())
(i_start, j_start, i_end, j_end) = input().strip().split(' ')
(i_start, j_start, i_end, j_end) = [int(i_start), int(j_start), int(i_end), int(j_end)]
printShortestPath(n, i_start, j_start, i_end, j_end)


import collections
n = int(input())
(istart, jstart, iend, jend) = map(int, input().split())
grid = [[None] * n for i in range(n)]
moves = [(-2, -1, 'UL'), (-2, +1, 'UR'), (0, +2, 'R'), (+2, +1, 'LR'), (+2, -1, 'LL'), (0, -2, 'L')]
grid[istart][jstart] = (-1, -1, '')
active = collections.deque()
active.append((istart, jstart))
while active:
	(i, j) = active.popleft()
	for (di, dj, dir) in moves:
		i2 = i + di
		j2 = j + dj
		if i2 < 0 or i2 >= n or j2 < 0 or (j2 >= n) or grid[i2][j2]:
			continue
		grid[i2][j2] = (i, j, dir)
		if i == iend and j == jend:
			active.clear()
			break
		active.append((i2, j2))
if grid[iend][jend]:
	i = iend
	j = jend
	path = []
	while True:
		(i, j, dir) = grid[i][j]
		if dir == '':
			break
		path.append(dir)
	path.reverse()
	print(len(path))
	print(*path)
else:
	print('Impossible')


import sys

def distance(i_start, j_start, i_end, j_end):
	if min(i_start, j_start, i_end, j_end) < 0 or max(i_start, j_start, i_end, j_end) >= n:
		return -1
	fieldsDown = abs(i_end - i_start)
	fieldsRight = abs(j_end - j_start)
	if fieldsDown + fieldsRight == 0:
		return 0
	if fieldsDown % 2 == 1:
		return -1
	stepsDown = fieldsDown // 2
	if (stepsDown + fieldsRight) % 2 == 1:
		return -1
	secondSummand = max([0, (fieldsRight - stepsDown) // 2])
	return stepsDown + secondSummand

def solve(i_start, j_start, i_end, j_end):
	steps = []
	d = distance(i_start, j_start, i_end, j_end)
	if d == -1:
		print('Impossible')
		return
	else:
		print(d)
	moves = [['UL', -2, -1], ['UR', -2, 1], ['R', 0, 2], ['LR', 2, 1], ['LL', 2, -1], ['L', 0, -2]]
	while d != 0:
		for m in moves:
			newD = distance(i_start + m[1], j_start + m[2], i_end, j_end)
			if newD != -1 and newD < d:
				i_start += m[1]
				j_start += m[2]
				d = newD
				steps.append(m[0])
				break
	print(' '.join(steps))

def printShortestPath(n, i_start, j_start, i_end, j_end):
	solve(i_start, j_start, i_end, j_end)
n = int(input().strip())
(i_start, j_start, i_end, j_end) = input().strip().split(' ')
(i_start, j_start, i_end, j_end) = [int(i_start), int(j_start), int(i_end), int(j_end)]
printShortestPath(n, i_start, j_start, i_end, j_end)


import sys

def printShortestPath(n, i_start, j_start, i_end, j_end):
	v_dist = abs(i_start - i_end)
	h_dist = abs(j_start - j_end)
	if v_dist % 2 == 1:
		print('Impossible')
		return
	if h_dist % 2 != v_dist // 2 % 2:
		print('Impossible')
		return
	result = []
	(i, j) = (i_start, j_start)
	while i != i_end or j != j_end:
		if i > i_end and j < j_end:
			result.append('UR')
			i -= 2
			j += 1
		elif i < i_end and j < j_end:
			result.append('LR')
			i += 2
			j += 1
		elif i > i_end and j > j_end:
			result.append('UL')
			i -= 2
			j -= 1
		elif i < i_end and j > j_end:
			result.append('LL')
			i += 2
			j -= 1
		elif i == i_end and j < j_end:
			result.append('R')
			j += 2
		elif i == i_end and j > j_end:
			result.append('L')
			j -= 2
		elif i > i_end and j == j_end:
			if j > 0:
				result.append('UL')
				i -= 2
				j -= 1
			else:
				result.append('UR')
				i -= 2
				j += 1
		elif i < i_end and j == j_end:
			if j < n - 1:
				result.append('LR')
				i += 2
				j += 1
			else:
				result.append('LL')
				i += 2
				j -= 1
	priority = {'UL': 0, 'UR': 1, 'R': 2, 'LR': 3, 'LL': 4, 'L': 5}
	result.sort(key=lambda x: priority[x])
	print(len(result))
	print(' '.join(result))
n = int(input().strip())
(i_start, j_start, i_end, j_end) = input().strip().split(' ')
(i_start, j_start, i_end, j_end) = [int(i_start), int(j_start), int(i_end), int(j_end)]
printShortestPath(n, i_start, j_start, i_end, j_end)


from collections import deque

def printShortestPath(n, i_s, j_s, i_e, j_e):
	dist = [[None] * n for _ in range(n)]
	pth = [[None] * n for _ in range(n)]
	d = [(-2, -1, 'UL'), (-2, 1, 'UR'), (0, 2, 'R'), (2, 1, 'LR'), (2, -1, 'LL'), (0, -2, 'L'), (0, 2, 'R')]
	q = deque()
	q.append((i_s, j_s))
	dist[i_s][j_s] = 0
	while q:
		(i, j) = q.popleft()
		for (u, v, s) in ((i + di, j + dj, s) for (di, dj, s) in d):
			if all((0 <= x < n for x in (u, v))) and dist[u][v] is None:
				dist[u][v] = dist[i][j] + 1
				pth[u][v] = (i, j, s)
				if (u, v) == (i_e, j_e):
					print(dist[u][v])
					p = (i, j, s)
					l = []
					while p:
						l.append(p[2])
						p = pth[p[0]][p[1]]
					print(*reversed(l))
					return
				q.append((u, v))
	print('Impossible')
n = int(input().strip())
(i_start, j_start, i_end, j_end) = input().strip().split(' ')
(i_start, j_start, i_end, j_end) = [int(i_start), int(j_start), int(i_end), int(j_end)]
printShortestPath(n, i_start, j_start, i_end, j_end)


import sys

class Node:

	def __init__(self, present, parent):
		self.present = present
		self.parent = parent[:]

	def UL(self):
		self.present = [self.present[0] - 1, self.present[1] - 2]
		self.parent.append('UL')

	def UR(self):
		self.present = [self.present[0] + 1, self.present[1] - 2]
		self.parent.append('UR')

	def R(self):
		self.present = [self.present[0] + 2, self.present[1]]
		self.parent.append('R')

	def LR(self):
		self.present = [self.present[0] + 1, self.present[1] + 2]
		self.parent.append('LR')

	def LL(self):
		self.present = [self.present[0] - 1, self.present[1] + 2]
		self.parent.append('LL')

	def L(self):
		self.present = [self.present[0] - 2, self.present[1]]
		self.parent.append('L')

	def check(self, end):
		return self.present == end

	def boundary(self, visited, n):
		if self.present[0] < 0 or self.present[1] < 0 or self.present[0] > n - 1 or (self.present[1] > n - 1):
			return True
		elif visited[self.present[1]][self.present[0]] == True:
			return True
		else:
			visited[self.present[1]][self.present[0]] = True
			return False

def printShortestPath(n, i_start, j_start, i_end, j_end):
	end = [j_end, i_end]
	visited = dict()
	priority = {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()}
	for i in range(n):
		visited[i] = [False] * n
	queue = list()
	s = Node([j_start, i_start], [])
	queue.append(s)
	visited[i_start][j_start] = True
	while queue:
		s = queue.pop(0)
		for i in range(6):
			x = Node(s.present, s.parent)
			priority[i](x)
			if x.check(end):
				return x.parent
			elif x.boundary(visited, n):
				continue
			queue.append(x)
	return []

def printd(li):
	if len(li) == 0:
		print('Impossible')
	else:
		print(len(li))
		for i in li:
			print(i, end=' ')
		print(' ')
n = int(input().strip())
(i_start, j_start, i_end, j_end) = input().strip().split(' ')
(i_start, j_start, i_end, j_end) = [int(i_start), int(j_start), int(i_end), int(j_end)]
printd(printShortestPath(n, i_start, j_start, i_end, j_end))


import sys

def printShortestPath(n, i_start, j_start, i_end, j_end):
	if i_start % 2 == 0:
		if i_end % 2 != 0:
			print('Impossible')
			return
	elif i_end % 2 == 0:
		print('Impossible')
		return
	if j_start % 2 == 0:
		if abs(i_start - i_end) / 2 % 2 == 0:
			if j_end % 2 != 0:
				print('Impossible')
				return
		elif j_end % 2 == 0:
			print('Impossible')
			return
	elif abs(i_start - i_end) / 2 % 2 == 0:
		if j_end % 2 == 0:
			print('Impossible')
			return
	elif j_end % 2 != 0:
		print('Impossible')
		return
	s = ''
	count = 0
	while 1:
		if i_start == i_end and j_start == j_end:
			break
		elif i_start == i_end:
			if j_start < j_end:
				s += 'R '
				j_start += 2
				count += 1
			else:
				s += 'L '
				j_start -= 2
				count += 1
		elif j_start == j_end:
			if i_start < i_end:
				x = (i_end - i_start) // 4
				while x:
					s += 'LR '
					i_start += 2
					j_start += 1
					x -= 1
					count += 1
			else:
				x = (i_start - i_end) // 4
				while x:
					s += 'UL '
					i_start -= 2
					j_start -= 1
					x -= 1
					count += 1
		elif i_start < i_end and j_start < j_end:
			x = (i_end - i_start) // 2
			y = j_end - j_start
			if y > x:
				s += 'R '
				j_start += 2
				count += 1
			else:
				s += 'LR '
				i_start += 2
				j_start += 1
				count += 1
		elif i_start > i_end and j_start > j_end:
			s += 'UL '
			i_start -= 2
			j_start -= 1
			count += 1
		elif i_start < i_end and j_start > j_end:
			jumps = (i_end - i_start) // 2
			tr = j_start - j_end
			jumps = (jumps - tr) // 2
			if jumps >= 1:
				while jumps:
					s += 'LR '
					i_start += 2
					j_start += 1
					count += 1
					jumps -= 1
			else:
				s += 'LL '
				i_start += 2
				j_start -= 1
				count += 1
		else:
			s += 'UR '
			i_start -= 2
			j_start += 1
			count += 1
	print(count)
	print(s)
n = int(input().strip())
(i_start, j_start, i_end, j_end) = input().strip().split(' ')
(i_start, j_start, i_end, j_end) = [int(i_start), int(j_start), int(i_end), int(j_end)]
printShortestPath(n, i_start, j_start, i_end, j_end)


import re
import sys
FAILURE = 'Impossible'
UPLEFT = 'UL '
UPRIGHT = 'UR '
DOWNLEFT = 'LL '
DOWNRIGHT = 'LR '
LEFT = 'L '
RIGHT = 'R '

def sign(x):
	return 1 if x >= 0 else -1
lines = [line.strip() for line in sys.stdin.readlines()]
n = int(lines[0])
positions = [int(r) for r in re.split('[^\\d]', lines[1])]
start = positions[:2]
end = positions[2:]
dx = end[1] - start[1]
dy = end[0] - start[0]
absdx = abs(dx)
absdy = abs(dy)
if absdy % 2 == 1:
	print(FAILURE)
	sys.exit(0)
Ny = absdy // 2
if absdx % 2 == 0 and Ny % 2 == 1 or (absdx % 2 == 1 and Ny % 2 == 0):
	print(FAILURE)
	sys.exit(0)
if absdx >= Ny:
	oppmoves = 0
else:
	oppmoves = (Ny - absdx) // 2
if not oppmoves:
	dxprime = dx - sign(dx) * Ny
	absdxprime = abs(dxprime)
else:
	dxprime = 0
	absdxprime = 0
Nx = absdxprime // 2
resultstring = ''
if dy < 0:
	if dx < 0:
		resultstring += UPLEFT * (Ny - oppmoves)
		resultstring += UPRIGHT * oppmoves
	else:
		resultstring += UPLEFT * oppmoves
		resultstring += UPRIGHT * (Ny - oppmoves)
if dxprime > 0:
	resultstring += RIGHT * Nx
if dy > 0:
	if dx < 0:
		resultstring += DOWNRIGHT * oppmoves
		resultstring += DOWNLEFT * (Ny - oppmoves)
	else:
		resultstring += DOWNRIGHT * (Ny - oppmoves)
		resultstring += DOWNLEFT * oppmoves
if dxprime < 0:
	resultstring += LEFT * Nx
print(Ny + Nx)
print(resultstring.strip())


import sys

def printShortestPath(n, i_start, j_start, i_end, j_end):
	visited = [[0 for i in range(n)] for k in range(n)]
	prev = [[0 for i in range(n)] for k in range(n)]
	q = []
	q.append((i_start, j_start))
	move_list = [(-2, -1), (-2, 1), (0, 2), (2, 1), (2, -1), (0, -2)]
	name_list = ['UL', 'UR', 'R', 'LR', 'LL', 'L']
	flag = True
	visited[i_start][j_start] = 1
	while q:
		(x, y) = q.pop(0)
		if (x, y) == (i_end, j_end):
			path = []
			node = (x, y)
			while prev[x][y] != 0:
				(x, y, t) = prev[x][y]
				path.append(t)
			path.reverse()
			print(len(path))
			print(' '.join(path))
			flag = False
			break
		visited[x][y] = 1
		for (idx, (dx, dy)) in enumerate(move_list):
			(new_x, new_y) = (x + dx, y + dy)
			if 0 <= new_x < n and 0 <= new_y < n:
				if visited[new_x][new_y] == 1:
					continue
				else:
					q.append((new_x, new_y))
					prev[new_x][new_y] = (x, y, name_list[idx])
					visited[new_x][new_y] = 1
	if flag:
		print('Impossible')
n = int(input().strip())
(i_start, j_start, i_end, j_end) = input().strip().split(' ')
(i_start, j_start, i_end, j_end) = [int(i_start), int(j_start), int(i_end), int(j_end)]
printShortestPath(n, i_start, j_start, i_end, j_end)


import sys

def printStuff(c, s):
	print(c)
	b = ''
	temp = s.split(' ')
	final = []
	for x in range(0, len(temp) - 1):
		if temp[x] == 'UL':
			final.append('UL')
	for x in range(0, len(temp) - 1):
		if temp[x] == 'UR':
			final.append('UR')
	for x in range(0, len(temp) - 1):
		if temp[x] == 'R':
			final.append('R')
	for x in range(0, len(temp) - 1):
		if temp[x] == 'LR':
			final.append('LR')
	for x in range(0, len(temp) - 1):
		if temp[x] == 'LL':
			final.append('LL')
	for x in range(0, len(temp) - 1):
		if temp[x] == 'L':
			final.append('L')
	for x in range(0, len(final)):
		b = b + final[x] + ' '
	print(b)

def printShortestPath(n, i_start, j_start, i_end, j_end):
	t = ''
	count = 0
	y = i_start
	sy = i_start
	x = j_start
	sx = j_start
	a = i_end
	b = j_end
	if sy > a:
		while True:
			if sx >= b:
				sx -= 1
				sy -= 2
				count += 1
				t = t + 'UL '
				if sx < b and sy < a:
					print('Impossible')
					return
			elif sx < b:
				sx += 1
				sy -= 2
				count += 1
				t = t + 'UR '
				if sx > b and sy > a:
					print('Impossible')
					return
			if sy == a and sx == b:
				printStuff(count, t)
				return
			elif sy == a and sx != b:
				break
	if sy < a:
		while True:
			if sx > b:
				sx -= 1
				sy += 2
				count += 1
				t = t + 'LL '
				if sx < b and sy > a:
					print('Impossible')
					return
			elif sx <= b:
				sx += 1
				sy += 2
				count += 1
				t = t + 'LR '
				if sx > b and sy > a:
					print('Impossible')
					return
			if sy == a and sx == b:
				printStuff(count, t)
				return
			elif sy == a and sx != b:
				break
	if sy == a:
		if sx < b:
			while True:
				sx += 2
				count += 1
				t = t + 'R '
				if sx == b:
					printStuff(count, t)
					return
				elif sx > b:
					print('Impossible')
					return
		elif sx > b:
			while True:
				sx -= 2
				count += 1
				t = t + 'L '
				if sx == b:
					printStuff(count, t)
					return
				elif sx < b:
					print('Impossible')
					return
n = int(input().strip())
(i_start, j_start, i_end, j_end) = input().strip().split(' ')
(i_start, j_start, i_end, j_end) = [int(i_start), int(j_start), int(i_end), int(j_end)]
printShortestPath(n, i_start, j_start, i_end, j_end)


import sys

def printShortestPath(n, i_start, j_start, i_end, j_end):
	v = [[False for i in range(n)] for j in range(n)]
	v[i_start][j_start] = True
	p = [[(-1, -1) for i in range(n)] for j in range(n)]
	m = [['' for i in range(n)] for j in range(n)]
	q = [(i_start, j_start)]
	while q:
		curr = q.pop(0)
		if curr[0] == i_end and curr[1] == j_end:
			break
		if curr[0] - 2 >= 0 and curr[1] - 1 >= 0 and (v[curr[0] - 2][curr[1] - 1] == False):
			v[curr[0] - 2][curr[1] - 1] = True
			p[curr[0] - 2][curr[1] - 1] = curr
			m[curr[0] - 2][curr[1] - 1] = 'UL'
			q.append((curr[0] - 2, curr[1] - 1))
		if curr[0] - 2 >= 0 and curr[1] + 1 < n and (v[curr[0] - 2][curr[1] + 1] == False):
			v[curr[0] - 2][curr[1] + 1] = True
			p[curr[0] - 2][curr[1] + 1] = curr
			m[curr[0] - 2][curr[1] + 1] = 'UR'
			q.append((curr[0] - 2, curr[1] + 1))
		if curr[1] + 2 < n and v[curr[0]][curr[1] + 2] == False:
			v[curr[0]][curr[1] + 2] = True
			p[curr[0]][curr[1] + 2] = curr
			m[curr[0]][curr[1] + 2] = 'R'
			q.append((curr[0], curr[1] + 2))
		if curr[0] + 2 < n and curr[1] + 1 < n and (v[curr[0] + 2][curr[1] + 1] == False):
			v[curr[0] + 2][curr[1] + 1] = True
			p[curr[0] + 2][curr[1] + 1] = curr
			m[curr[0] + 2][curr[1] + 1] = 'LR'
			q.append((curr[0] + 2, curr[1] + 1))
		if curr[0] + 2 < n and curr[1] - 1 >= 0 and (v[curr[0] + 2][curr[1] - 1] == False):
			v[curr[0] + 2][curr[1] - 1] = True
			p[curr[0] + 2][curr[1] - 1] = curr
			m[curr[0] + 2][curr[1] - 1] = 'LL'
			q.append((curr[0] + 2, curr[1] - 1))
		if curr[1] - 2 >= 0 and v[curr[0]][curr[1] - 2] == False:
			v[curr[0]][curr[1] - 2] = True
			p[curr[0]][curr[1] - 2] = curr
			m[curr[0]][curr[1] - 2] = 'L'
			q.append((curr[0], curr[1] - 2))
	if v[i_end][j_end] == False or (i_start, j_start) == (i_end, j_end):
		print('Impossible')
	else:
		len_path = 0
		moves = ''
		end = p[i_end][j_end]
		i = i_end
		j = j_end
		while p[i][j] != (-1, -1):
			if len_path == 0:
				mid = ''
			else:
				mid = ' '
			moves = m[i][j] + mid + moves
			tmp_i = p[i][j][0]
			tmp_j = p[i][j][1]
			i = tmp_i
			j = tmp_j
			len_path += 1
		print(len_path)
		print(moves)
n = int(input().strip())
(i_start, j_start, i_end, j_end) = input().strip().split(' ')
(i_start, j_start, i_end, j_end) = [int(i_start), int(j_start), int(i_end), int(j_end)]
printShortestPath(n, i_start, j_start, i_end, j_end)


import sys

def validMove(n, i, j):
	if i < 0 or i >= n:
		return False
	if j < 0 or j >= n:
		return False
	return True
name = ['UL', 'UR', 'R', 'LR', 'LL', 'L']
moveY = [-1, 1, 2, 1, -1, -2]
moveX = [-2, -2, 0, 2, 2, 0]

def findNextLevel(inputArray, parent, level, cur_level, n, i_end, j_end):
	outputArray = []
	found = False
	for k in range(len(inputArray)):
		for i in range(6):
			if validMove(n, inputArray[k][0] + moveX[i], inputArray[k][1] + moveY[i]):
				if inputArray[k][0] + moveX[i] == i_end and inputArray[k][1] + moveY[i] == j_end:
					parent[inputArray[k][0] + moveX[i]][inputArray[k][1] + moveY[i]] = inputArray[k]
					found = True
					break
				elif level[inputArray[k][0] + moveX[i]][inputArray[k][1] + moveY[i]] == -1:
					level[inputArray[k][0] + moveX[i]][inputArray[k][1] + moveY[i]] = cur_level + 1
					parent[inputArray[k][0] + moveX[i]][inputArray[k][1] + moveY[i]] = inputArray[k]
					outputArray.append([inputArray[k][0] + moveX[i], inputArray[k][1] + moveY[i]])
		if found:
			break
	if found:
		return True
	elif len(outputArray) > 0:
		found = found or findNextLevel(outputArray, parent, level, cur_level + 1, n, i_end, j_end)
	return found

def printShortestPath(n, i_start, j_start, i_end, j_end):
	parent = [[[-1, -1] for i in range(n)] for j in range(n)]
	level = [[-1 for i in range(n)] for j in range(n)]
	cur_level = 0
	level[i_start][j_start] = 0
	found = findNextLevel([[i_start, j_start]], parent, level, cur_level, n, i_end, j_end)
	if found:
		start = [i_end, j_end]
		result = []
		while start != [-1, -1]:
			temp = parent[start[0]][start[1]]
			delX = -temp[0] + start[0]
			delY = -temp[1] + start[1]
			for i in range(6):
				if [delX, delY] == [moveX[i], moveY[i]]:
					result.append(name[i])
					break
			start = temp
		print(len(result))
		strToWrite = ''
		for i in range(len(result)):
			strToWrite += result[len(result) - 1 - i] + ' '
		print(strToWrite[:-1])
	else:
		print('Impossible')
n = int(input().strip())
(i_start, j_start, i_end, j_end) = input().strip().split(' ')
(i_start, j_start, i_end, j_end) = [int(i_start), int(j_start), int(i_end), int(j_end)]
printShortestPath(n, i_start, j_start, i_end, j_end)


import sys

def printShortestPath(n, i_start, j_start, i_end, j_end):
	if i_start % 2 != i_end % 2:
		print('Impossible')
	elif i_start % 4 == i_end % 4 and j_start % 2 != j_end % 2:
		print('Impossible')
	elif i_start % 4 != i_end % 4 and j_start % 2 == j_end % 2:
		print('Impossible')
	else:
		numMoves = 0
		moveStr = ''
		while i_start != i_end or j_start != j_end:
			if i_start - i_end > max((j_end - j_start) * 2, 0) and j_start > 0:
				moveStr += 'UL '
				i_start -= 2
				j_start -= 1
			elif i_start > i_end and j_start >= j_end and (j_start > 0):
				moveStr += 'UL '
				i_start -= 2
				j_start -= 1
			elif (i_start > i_end and j_start <= j_end) and j_start < n - 1:
				moveStr += 'UR '
				i_start -= 2
				j_start += 1
			elif j_end > j_start and (j_end - j_start) * 2 > i_end - i_start and (j_start < n - 2):
				moveStr += 'R '
				j_start += 2
			elif i_end - i_start > max((j_start - j_end) * 2, 0) and j_start < n - 1:
				moveStr += 'LR '
				i_start += 2
				j_start += 1
			elif i_start < i_end and j_start <= j_end and (j_start < n - 1):
				moveStr += 'LR '
				i_start += 2
				j_start += 1
			elif (i_start < i_end and j_start >= j_end) and j_start > 0:
				moveStr += 'LL '
				i_start += 2
				j_start -= 1
			elif (i_start == i_end and j_start > j_end) and j_start > 1:
				moveStr += 'L '
				j_start -= 2
			numMoves += 1
		print(numMoves)
		print(moveStr.strip())
n = int(input().strip())
(i_start, j_start, i_end, j_end) = input().strip().split(' ')
(i_start, j_start, i_end, j_end) = [int(i_start), int(j_start), int(i_end), int(j_end)]
printShortestPath(n, i_start, j_start, i_end, j_end)


import sys

def update_table(board, path, cells, i_old, j_old, i_new, j_new, current_l, move):
	board[i_new][j_new] = current_l
	cells.append((i_new, j_new))
	path[i_new, j_new] = path[i_old, j_old].copy()
	path[i_new, j_new].append(move)

def printShortestPath(n, i_start, j_start, i_end, j_end):
	moves_order = ['UpperLeft', 'UpperRight', 'Right', 'LowerRight', 'LowerLeft', 'Left']
	board = []
	for _ in range(n):
		board.append([-1] * n)
	board[i_start][j_start] = 0
	path = {(i_start, j_start): []}
	current_l = 0
	current_cells = [(i_start, j_start)]
	can_move = 1
	while can_move:
		current_l += 1
		can_move = 0
		new_cells = []
		for cell in current_cells:
			if cell[0] > 1:
				if cell[1] > 0 and board[cell[0] - 2][cell[1] - 1] < 0:
					update_table(board, path, new_cells, cell[0], cell[1], cell[0] - 2, cell[1] - 1, current_l, 'UL')
					can_move = 1
				if cell[1] < n - 1 and board[cell[0] - 2][cell[1] + 1] < 0:
					update_table(board, path, new_cells, cell[0], cell[1], cell[0] - 2, cell[1] + 1, current_l, 'UR')
					can_move = 1
			if cell[1] < n - 2 and board[cell[0]][cell[1] + 2] < 0:
				update_table(board, path, new_cells, cell[0], cell[1], cell[0], cell[1] + 2, current_l, 'R')
				can_move = 1
			if cell[0] < n - 2:
				if cell[1] < n - 1 and board[cell[0] + 2][cell[1] + 1] < 0:
					update_table(board, path, new_cells, cell[0], cell[1], cell[0] + 2, cell[1] + 1, current_l, 'LR')
					can_move = 1
				if cell[1] > 0 and board[cell[0] + 2][cell[1] - 1] < 0:
					update_table(board, path, new_cells, cell[0], cell[1], cell[0] + 2, cell[1] - 1, current_l, 'LL')
					can_move = 1
			if cell[1] > 1 and board[cell[0]][cell[1] - 2] < 0:
				update_table(board, path, new_cells, cell[0], cell[1], cell[0], cell[1] - 2, current_l, 'L')
				can_move = 1
		current_cells = new_cells
	if board[i_end][j_end] == -1:
		print('Impossible')
	else:
		print(board[i_end][j_end])
		print(' '.join(path[i_end, j_end]))
n = int(input().strip())
(i_start, j_start, i_end, j_end) = input().strip().split(' ')
(i_start, j_start, i_end, j_end) = [int(i_start), int(j_start), int(i_end), int(j_end)]
printShortestPath(n, i_start, j_start, i_end, j_end)


import sys
from collections import OrderedDict
from operator import add
ds = ['UL', 'UR', 'R', 'LR', 'LL', 'L']
dirs = [('UL', (-1, -2)), ('UR', (1, -2)), ('R', (2, 0)), ('LR', (1, 2)), ('LL', (-1, 2)), ('L', (-2, 0))]

def dist(p1, p2):
	return abs(p1[0] - p2[0]) + abs(p1[1] - p2[1])

def nextStep(pos, dest):
	best = None
	currdist = dist(pos, dest)
	if currdist == 0:
		return 'Done'
	mindist = None
	minpos = None
	for i in dirs:
		newpos = list(map(add, pos, i[1]))
		newdist = dist(newpos, dest)
		print('{}, {}, {:}, {}, {}, {}'.format(pos, dest, currdist, i, newpos, newdist), file=sys.stderr)
		if mindist is None or mindist > newdist:
			mindist = newdist
			minpos = newpos
			best = i
	print('best: {}, [{}] -> [{}], dist:{} -> {}'.format(best, pos, minpos, currdist, mindist), file=sys.stderr)
	if mindist > currdist:
		print('Got further: Abort', file=sys.stderr)
		best = None
	if mindist == currdist:
		print('No closer: Abort', file=sys.stderr)
		best = None
	return best

def printShortestPath(n, i_start, j_start, i_end, j_end):
	pos = (j_start, i_start)
	dest = (j_end, i_end)
	steps = []
	while True:
		bestMove = nextStep(pos, dest)
		if bestMove is None:
			print('Impossible')
			return
		elif bestMove == 'Done':
			break
		else:
			steps.append(bestMove)
			pos = list(map(add, pos, bestMove[1]))
	print(len(steps))
	steps = sorted(steps, key=lambda x: ds.index(x[0]))
	print(' '.join((s[0] for s in steps)))
n = int(input().strip())
(i_start, j_start, i_end, j_end) = input().strip().split(' ')
(i_start, j_start, i_end, j_end) = [int(i_start), int(j_start), int(i_end), int(j_end)]
printShortestPath(n, i_start, j_start, i_end, j_end)


import sys

def printShortestPath(n, i_start, j_start, i_end, j_end):
	shortestPaths = {(i_start, j_start): []}
	moves = {'UL': (-2, -1), 'UR': (-2, 1), 'LL': (2, -1), 'LR': (2, 1), 'L': (0, -2), 'R': (0, 2)}
	moveorder = ['UL', 'UR', 'R', 'LR', 'LL', 'L']
	new = [(i_start, j_start)]
	while len(new) > 0:
		curr = new.pop(0)
		for m in moveorder:
			next_pos = (curr[0] + moves[m][0], curr[1] + moves[m][1])
			if next_pos not in shortestPaths and min(next_pos) >= 0 and (max(next_pos) < n):
				shortestPaths[next_pos] = shortestPaths[curr] + [m]
				new.append(next_pos)
	if (i_end, j_end) in shortestPaths:
		print(len(shortestPaths[i_end, j_end]))
		print(' '.join(shortestPaths[i_end, j_end]))
	else:
		print('Impossible')
n = int(input().strip())
(i_start, j_start, i_end, j_end) = input().strip().split(' ')
(i_start, j_start, i_end, j_end) = [int(i_start), int(j_start), int(i_end), int(j_end)]
printShortestPath(n, i_start, j_start, i_end, j_end)


class node:

	def __init__(self):
		self.i = None
		self.j = None
		self.h = None
		self.parent = None
		self.move = None

class pathnode:

	def __init__(self):
		self.a = []
		self.length = len(self.a)

class redknight_chess:

	def __init__(self, n, s, e):
		self.start = s
		self.end = e
		self.start.h = self.heuristic(self.start)
		self.end.h = self.heuristic(self.end)
		self.n = n
		self.openx = []
		self.openx.append(s)
		self.paths = [None for i in range(100)]
		self.closex = []

	def search(self):
		k = 0
		while len(self.openx) > 0:
			if k == 5:
				return
			x = self.openx[0]
			del self.openx[0]
			self.closex.append(x)
			if x.i == self.end.i and x.j == self.end.j:
				self.printpath(x)
				k = k + 1
			adj = self.movegen(x)
			adjr = self.removeseen(adj)
			self.openx = self.openx + adjr

	def movegen(self, e):
		m = e.i
		n = e.j
		move = []
		p = m - 1
		q = n - 2
		nod = node()
		nod.i = p
		nod.j = q
		if p >= 0 and q >= 0 and (p < self.n) and (q < self.n):
			nod.h = self.heuristic(nod)
			nod.parent = e
			nod.move = 'UL'
			if nod.h < e.h:
				move.append(nod)
		p = m + 1
		q = n - 2
		nod = node()
		nod.i = p
		nod.j = q
		if p >= 0 and q >= 0 and (p < self.n) and (q < self.n):
			nod.h = self.heuristic(nod)
			nod.parent = e
			nod.move = 'UR'
			if nod.h < e.h:
				move.append(nod)
		p = m + 2
		q = n
		nod = node()
		nod.i = p
		nod.j = q
		if p >= 0 and q >= 0 and (p < self.n) and (q < self.n):
			nod.h = self.heuristic(nod)
			nod.parent = e
			nod.move = 'R'
			if nod.h < e.h:
				move.append(nod)
		p = m + 1
		q = n + 2
		nod = node()
		nod.i = p
		nod.j = q
		if p >= 0 and q >= 0 and (p < self.n) and (q < self.n):
			nod.h = self.heuristic(nod)
			nod.parent = e
			nod.move = 'LR'
			if nod.h < e.h:
				move.append(nod)
		p = m - 1
		q = n + 2
		nod = node()
		nod.i = p
		nod.j = q
		if p >= 0 and q >= 0 and (p < self.n) and (q < self.n):
			nod.h = self.heuristic(nod)
			nod.parent = e
			nod.move = 'LL'
			if nod.h < e.h:
				move.append(nod)
		p = m - 2
		q = n
		nod = node()
		nod.i = p
		nod.j = q
		if p >= 0 and q >= 0 and (p < self.n) and (q < self.n):
			nod.h = self.heuristic(nod)
			nod.parent = e
			nod.move = 'L'
			if nod.h < e.h:
				move.append(nod)
		return move

	def heuristic(self, n):
		n.i
		max_i = max(n.i, self.end.i)
		min_i = min(n.i, self.end.i)
		max_j = max(n.j, self.end.j)
		min_j = min(n.j, self.end.j)
		a = max_i - min_i
		b = max_j - min_j
		a = a * a
		b = b * b
		s = a + b
		return s

	def compare(self, a, b):
		if a.i == b.i and a.j == b.j:
			return True
		return False

	def removeseen(self, n):
		for i in range(len(n)):
			t = 0
			for j in range(len(self.openx)):
				if self.compare(n[i], self.openx[j]) == True:
					del n[i]
					t = 1
					break
			if t == 1:
				break
		for i in range(len(n)):
			t = 0
			for j in range(len(self.openx)):
				if self.compare(n[i], self.openx[j]) == True:
					del n[i]
					t = 1
					break
			if t == 1:
				break
		for i in range(len(n)):
			t = 0
			for j in range(len(self.openx)):
				if self.compare(n[i], self.openx[j]) == True:
					del n[i]
					t = 1
					break
			if t == 1:
				break
		for i in range(len(n)):
			t = 0
			for j in range(len(self.openx)):
				if self.compare(n[i], self.openx[j]) == True:
					del n[i]
					t = 1
					break
			if t == 1:
				break
		for i in range(len(n)):
			t = 0
			for j in range(len(self.openx)):
				if self.compare(n[i], self.openx[j]) == True:
					del n[i]
					t = 1
					break
			if t == 1:
				break
		for i in range(len(n)):
			t = 0
			for j in range(len(self.openx)):
				if self.compare(n[i], self.openx[j]) == True:
					del n[i]
					t = 1
					break
			if t == 1:
				break
		for i in range(len(n)):
			t = 0
			for j in range(len(self.closex)):
				if self.compare(n[i], self.closex[j]) == True:
					del n[i]
					t = 1
					break
			if t == 1:
				break
		for i in range(len(n)):
			t = 0
			for j in range(len(self.closex)):
				if self.compare(n[i], self.closex[j]) == True:
					del n[i]
					t = 1
					break
			if t == 1:
				break
		for i in range(len(n)):
			t = 0
			for j in range(len(self.closex)):
				if self.compare(n[i], self.closex[j]) == True:
					del n[i]
					t = 1
					break
			if t == 1:
				break
		for i in range(len(n)):
			t = 0
			for j in range(len(self.closex)):
				if self.compare(n[i], self.closex[j]) == True:
					del n[i]
					t = 1
					break
			if t == 1:
				break
		for i in range(len(n)):
			t = 0
			for j in range(len(self.closex)):
				if self.compare(n[i], self.closex[j]) == True:
					del n[i]
					t = 1
					break
			if t == 1:
				break
		for i in range(len(n)):
			t = 0
			for j in range(len(self.closex)):
				if self.compare(n[i], self.closex[j]) == True:
					del n[i]
					t = 1
					break
			if t == 1:
				break
		return n

	def printpath(self, x):
		a = []
		a.append(x)
		par = x.parent
		while par != None:
			a.append(par)
			par = par.parent
		if self.paths[len(a)] == None:
			self.paths[len(a)] = a

	def solution(self):
		for i in range(100):
			if self.paths[i] != None:
				print(i - 1)
				for j in range(len(self.paths[i])):
					if self.paths[i][-1 - j].move != None:
						print(self.paths[i][-1 - j].move, end=' ')
				return
		sol = 'Impossible'
		print(sol)
		return

def main():
	n = int(input())
	x = input()
	x = x.split()
	for i in range(len(x)):
		x[i] = int(x[i])
	s = node()
	e = node()
	s.i = x[1]
	s.j = x[0]
	e.i = x[3]
	e.j = x[2]
	find = redknight_chess(n, s, e)
	find.search()
	find.solution()
main()


import sys

def printShortestPath(n, i_start, j_start, i_end, j_end):
	seen = {(i_start, j_start)}
	pathes = [[(i_start, j_start)]]
	reached = False
	while pathes and (not reached):
		temp = []
		for path in pathes:
			(x, y) = path[-1]
			ul = (x - 2, y - 1)
			ur = (x - 2, y + 1)
			r = (x, y + 2)
			l = (x, y - 2)
			lr = (x + 2, y + 1)
			ll = (x + 2, y - 1)
			order = [ul, ur, r, lr, ll, l]
			if (i_end, j_end) in order:
				reached = path[:] + [(i_end, j_end)]
				break
			else:
				for (i, j) in order:
					if i in range(n) and j in range(n):
						if (i, j) not in seen:
							seen.add((i, j))
							temp.append(path[:] + [(i, j)])
		pathes = temp
	if not reached:
		print('Impossible')
	else:
		print(len(reached) - 1)
		order = ''
		pos = (i_start, j_start)
		for (i, j) in reached[1:]:
			if i == pos[0]:
				if j > pos[1]:
					order = order + 'R '
				else:
					order = order + 'L '
			elif i > pos[0]:
				if j > pos[1]:
					order = order + 'LR '
				else:
					order = order + 'LL '
			elif j > pos[1]:
				order = order + 'UR '
			else:
				order = order + 'UL '
			pos = (i, j)
		print(order[:-1])
n = int(input().strip())
(i_start, j_start, i_end, j_end) = input().strip().split(' ')
(i_start, j_start, i_end, j_end) = [int(i_start), int(j_start), int(i_end), int(j_end)]
printShortestPath(n, i_start, j_start, i_end, j_end)


import sys

class Node:

	def __init__(self, i, j, d, p):
		self.i = i
		self.j = j
		self.d = d
		self.p = p

def printShortestPath(n, ist, jst, ind, jnd):
	if n <= 3:
		print('Impossible')
		return
	mps = [[-2, -1], [-2, 1], [0, 2], [2, 1], [2, -1], [0, -2]]
	nts = ['UL', 'UR', 'R', 'LR', 'LL', 'L']
	pts = [Node(ist, jst, None, None)]
	visited = [ist * n + jst + 1]
	no = 0
	nn = None
	is_continue = True
	while is_continue:
		tpts = []
		no += 1
		for p in pts:
			for (mp, nt) in zip(mps, nts):
				ni = p.i + mp[0]
				nj = p.j + mp[1]
				idx = ni * n + nj + 1
				if ni < 0 or ni >= n or nj < 0 or (nj >= n) or (idx in visited):
					continue
				else:
					nn = Node(ni, nj, nt, p)
					if ni == ind and nj == jnd:
						print(no)
						tnn = nn
						pns = []
						while tnn.p:
							pns.append(tnn.d)
							tnn = tnn.p
						print(' '.join(reversed(pns)))
						return
					else:
						tpts.append(nn)
						visited.append(idx)
		if not tpts:
			print('Impossible')
			return
		else:
			pts = tpts
n = int(input().strip())
(i_start, j_start, i_end, j_end) = input().strip().split(' ')
(i_start, j_start, i_end, j_end) = [int(i_start), int(j_start), int(i_end), int(j_end)]
printShortestPath(n, i_start, j_start, i_end, j_end)


__author__ = 'Tola'
from collections import deque
import sys

def printShortestPath(n, i_start, j_start, i_end, j_end, queue, state):
	while True:
		if len(queue) == 0:
			break
		current = queue.popleft()
		(i_s, j_s, moves) = current
		if 0 <= i_s - 2 < n and 0 <= j_s - 1 < n and state[i_s - 2][j_s - 1]:
			state[i_s - 2][j_s - 1] = False
			if i_s - 2 == i_end and j_s - 1 == j_end:
				return moves + ['UL']
			queue.append([i_s - 2, j_s - 1, moves + ['UL']])
		if 0 <= i_s - 2 < n and 0 <= j_s + 1 < n and state[i_s - 2][j_s + 1]:
			state[i_s - 2][j_s + 1] = False
			if i_s - 2 == i_end and j_s + 1 == j_end:
				return moves + ['UR']
			queue.append([i_s - 2, j_s + 1, moves + ['UR']])
		if 0 <= j_s + 2 < n and state[i_s][j_s + 2]:
			state[i_s][j_s + 2] = False
			if i_s == i_end and j_s + 2 == j_end:
				return moves + ['R']
			queue.append([i_s, j_s + 2, moves + ['R']])
		if 0 <= i_s + 2 < n and 0 <= j_s + 1 < n and state[i_s + 2][j_s + 1]:
			state[i_s + 2][j_s + 1] = False
			if i_s + 2 == i_end and j_s + 1 == j_end:
				return moves + ['LR']
			queue.append([i_s + 2, j_s + 1, moves + ['LR']])
		if 0 <= i_s + 2 < n and 0 <= j_s - 1 < n and state[i_s + 2][j_s - 1]:
			state[i_s + 2][j_s - 1] = False
			if i_s + 2 == i_end and j_s - 1 == j_end:
				return moves + ['LL']
			queue.append([i_s + 2, j_s - 1, moves + ['LL']])
		if 0 <= j_s - 2 < n and state[i_s][j_s - 2]:
			state[i_s][j_s - 2] = False
			if i_s == i_end and j_s - 2 == j_end:
				return moves + ['L']
			queue.append([i_s, j_s - 2, moves + ['L']])
n = int(input().strip())
(i_start, j_start, i_end, j_end) = input().strip().split(' ')
(i_start, j_start, i_end, j_end) = [int(i_start), int(j_start), int(i_end), int(j_end)]
state = [[True] * n for i in range(n)]
queue = deque([[i_start, j_start, []]])
state[i_start][j_start] = False
retVal = printShortestPath(n, i_start, j_start, i_end, j_end, queue, state)
if retVal:
	print(len(retVal))
	print(' '.join(retVal))
else:
	print('Impossible')


from collections import defaultdict
from itertools import product
n = int(input())
(x1, y1, x2, y2) = map(int, input().strip().split())
(start, end) = ((x1, y1), (x2, y2))
dist = defaultdict(lambda : float('inf'))
dist[end] = 0
for _ in range(n * n + 1):
	unchanged = True
	for (x, y) in product(range(n), range(n)):
		val = 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])
		if val < dist[x, y]:
			dist[x, y] = val
			unchanged = False
	if unchanged:
		break
if dist[start] == float('inf'):
	print('Impossible')
else:
	(x, y) = start
	path = []
	while (x, y) != end:
		d = dist[x, y]
		if dist[x - 2, y - 1] == d - 1:
			path.append('UL')
			(x, y) = (x - 2, y - 1)
		elif dist[x - 2, y + 1] == d - 1:
			path.append('UR')
			(x, y) = (x - 2, y + 1)
		elif dist[x, y + 2] == d - 1:
			path.append('R')
			(x, y) = (x, y + 2)
		elif dist[x + 2, y + 1] == d - 1:
			path.append('LR')
			(x, y) = (x + 2, y + 1)
		elif dist[x + 2, y - 1] == d - 1:
			path.append('LL')
			(x, y) = (x + 2, y - 1)
		elif dist[x, y - 2] == d - 1:
			path.append('L')
			(x, y) = (x, y - 2)
	print(dist[start])
	print(*path, sep=' ')


import sys

def printShortestPath(n, i_start, j_start, i_end, j_end):
	moveNames = ['UL ', 'UR ', 'R ', 'LR ', 'LL ', 'L ']
	moves = [(-2, -1), (-2, 1), (0, 2), (2, 1), (2, -1), (0, -2)]
	moveCounts = [[-1 for i in range(n)] for j in range(n)]
	currCount = 0
	moveCounts[i_end][j_end] = 0
	currLocs = [(i_end, j_end)]
	while len(currLocs) > 0:
		currCount += 1
		nextLocs = set()
		for (i, j) in currLocs:
			for (iDiff, jDiff) in moves:
				newI = i + iDiff
				newJ = j + jDiff
				if newI >= 0 and newI < n and (newJ >= 0) and (newJ < n) and (moveCounts[newI][newJ] == -1):
					nextLocs.add((newI, newJ))
					moveCounts[newI][newJ] = currCount
		currLocs = nextLocs
	if moveCounts[i_start][j_start] == -1:
		print('Impossible')
	else:
		moveCount = moveCounts[i_start][j_start]
		moveList = ''
		i = i_start
		j = j_start
		while i != i_end or j != j_end:
			for index in range(len(moves)):
				newI = i + moves[index][0]
				newJ = j + moves[index][1]
				if newI >= 0 and newI < n and (newJ >= 0) and (newJ < n) and (moveCounts[newI][newJ] == moveCount - 1):
					i = newI
					j = newJ
					moveList += moveNames[index]
					moveCount -= 1
					break
		print(moveCounts[i_start][j_start])
		print(moveList)
n = int(input().strip())
(i_start, j_start, i_end, j_end) = input().strip().split(' ')
(i_start, j_start, i_end, j_end) = [int(i_start), int(j_start), int(i_end), int(j_end)]
printShortestPath(n, i_start, j_start, i_end, j_end)


import sys
sys.setrecursionlimit(150000)
d = {1: 'UL', 2: 'UR', 3: 'R', 4: 'LR', 5: 'LL', 6: 'L'}

def trace_route(i1, j1, i2, j2):
	count = 0
	s = []
	while i1 != i2 or j1 != j2:
		if i1 - i2 >= 2 and j1 - j2 >= 1:
			s.append(1)
			i1 -= 2
			j1 -= 1
		elif i1 - i2 >= 2 and j2 - j1 >= 1:
			s.append(2)
			i1 -= 2
			j1 += 1
		elif i1 == i2 and j2 - j1 >= 2:
			s.append(3)
			j1 += 2
		elif i2 - i1 >= 2 and j2 - j1 >= 1:
			s.append(4)
			j1 += 1
			i1 += 2
		elif i2 - i1 >= 2 and j1 - j2 >= 1:
			s.append(5)
			j1 -= 1
			i1 += 2
		elif i1 == i2 and j1 - j2 >= 2:
			s.append(6)
			j1 -= 2
		elif j2 == j1:
			if i1 < i2:
				s.append(4)
				j1 += 1
				i1 += 2
			else:
				s.append(1)
				i1 -= 2
				j1 -= 1
		count += 1
	return (count, list(sorted(s)))

def is_ok(grid, i, j, n):
	return i >= 0 and j >= 0 and (i < n) and (j < n) and (not grid[i][j])

def propagate(i, j, grid, n):
	grid[i][j] = True
	if is_ok(grid, i - 2, j - 1, n):
		propagate(i - 2, j - 1, grid, n)
	if is_ok(grid, i - 2, j + 1, n):
		propagate(i - 2, j + 1, grid, n)
	if is_ok(grid, i, j + 2, n):
		propagate(i, j + 2, grid, n)
	if is_ok(grid, i + 2, j + 1, n):
		propagate(i + 2, j + 1, grid, n)
	if is_ok(grid, i + 2, j - 1, n):
		propagate(i + 2, j - 1, grid, n)
	if is_ok(grid, i, j - 2, n):
		propagate(i, j - 2, grid, n)
n = int(input())
grid = []
for i in range(n):
	l = []
	for j in range(n):
		l.append(False)
	grid.append(l)
(istart, jstart, iend, jend) = list(map(int, input().split()))
propagate(istart, jstart, grid, n)
if grid[iend][jend]:
	(c, s) = trace_route(istart, jstart, iend, jend)
	print(c)
	s = list(map(lambda x: d[x], s))
	print(' '.join(s))
else:
	print('Impossible')


def printShortestPath(n, i_start, j_start, i_end, j_end):
	vertdist = i_end - i_start
	hordist = j_end - j_start
	if vertdist % 2 == 1:
		print('Impossible')
	elif vertdist % 4 == 2 and hordist % 2 == 0:
		print('Impossible')
	elif vertdist % 4 == 0 and hordist % 2 == 1:
		print('Impossible')
	else:
		vertmoves = int(abs(vertdist / 2))
		if abs(hordist) <= vertmoves:
			moves = vertmoves
			hormoves = 0
		else:
			hormoves = int((abs(hordist) - vertmoves) / 2)
			moves = vertmoves + hormoves
		print(int(moves))
		s = ''
		if vertdist == 0:
			if hordist > 0:
				for i in range(hormoves):
					s += 'R '
			elif hordist < 0:
				for i in range(hormoves):
					s += 'L '
		elif vertdist < 0:
			if abs(hordist) >= vertmoves:
				if hordist < 0:
					for i in range(vertmoves):
						s += 'UL '
					for i in range(hormoves):
						s += 'L '
				else:
					for i in range(vertmoves):
						s += 'UR '
					for i in range(hormoves):
						s += 'R '
			else:
				ulmoves = int((vertmoves - hordist) / 2)
				urmoves = vertmoves - ulmoves
				if ulmoves <= j_start:
					for i in range(ulmoves):
						s += 'UL '
					for i in range(urmoves):
						s += 'UR '
				else:
					for i in range(j_start):
						s += 'UL '
					for i in range(int((vertmoves - j_start) / 2)):
						s += 'UR UL '
					if (vertmoves - j_start) % 2 == 1:
						s += 'UR '
		elif vertdist > 0:
			if abs(hordist) >= vertmoves:
				if hordist < 0:
					for i in range(vertmoves):
						s += 'LL '
					for i in range(hormoves):
						s += 'L '
				else:
					for i in range(hormoves):
						s += 'R '
					for i in range(vertmoves):
						s += 'LR '
			else:
				llmoves = int((vertmoves - hordist) / 2)
				lrmoves = vertmoves - llmoves
				if lrmoves < n - j_start:
					for i in range(lrmoves):
						s += 'LR '
					for i in range(llmoves):
						s += 'LL '
				else:
					for i in range(n - j_start - 1):
						s += 'LR '
					for i in range(int((vertmoves - n + j_start + 1) / 2)):
						s += 'LL LR '
					if (vertmoves - n + j_start + 1) % 2 == 1:
						s += 'LL '
		print(s)
n = int(input().strip())
(i_start, j_start, i_end, j_end) = input().strip().split(' ')
(i_start, j_start, i_end, j_end) = [int(i_start), int(j_start), int(i_end), int(j_end)]
printShortestPath(n, i_start, j_start, i_end, j_end)


import sys
sys.setrecursionlimit(1000000)
from copy import copy
ALREADY_DONE = set()
MOVES = {(0, 2): 'R', (0, -2): 'L', (-2, 1): 'UR', (-2, -1): 'UL', (2, 1): 'LR', (2, -1): 'LL'}
MOVES_ORDERED = [(-2, -1), (-2, 1), (0, 2), (2, 1), (2, -1), (0, -2)]

def compute_new_pos(pos, delta):
	return (pos[0] + delta[0], pos[1] + delta[1])

def is_out(pos, n):
	return pos[0] < 0 or pos[0] >= n or pos[1] >= n or (pos[1] < 0)

class RK:

	def __init__(self, position, n, target, historic, already_done):
		self.position = position
		self.target = target
		self.historic = historic
		self.already_done = already_done
		self.n = n

class RK_BFS(RK):

	def __init__(self, position, n, target, historic, already_done, count_rk, queue, all_pos):
		RK.__init__(self, position, n, target, historic, already_done)
		self.count_rk = count_rk
		self.queue = queue
		self.all_pos = all_pos + [position]

	def expand(self):
		self.count_rk += 1
		for move in MOVES_ORDERED:
			tmp_pos = compute_new_pos(self.position, move)
			if tmp_pos == self.target:
				new_histo = self.historic.copy() + [MOVES[move]]
				print(str(len(new_histo)))
				print(' '.join(new_histo))
				sys.exit(0)
			elif not is_out(tmp_pos, self.n) and (not tmp_pos in self.already_done):
				new_histo = self.historic.copy() + [MOVES[move]]
				self.count_rk += 1
				self.already_done.update([tmp_pos])
				rk_bfs = RK_BFS(tmp_pos, self.n, self.target, new_histo, self.already_done, self.count_rk, self.queue, self.all_pos)
				self.queue.append(rk_bfs)
		if len(self.queue) == 0:
			print('Impossible')
			sys.exit(0)
		rk = self.queue.pop(0)
		rk.expand()
		self.count_rk -= 1
		if self.count_rk == 0:
			print('Impossible')
			sys.exit(0)

def printShortestPath(n, i_start, j_start, i_end, j_end):
	if i_start % 2 != i_end % 2:
		print('Impossible')
		sys.exit(0)
	already_done = set(tuple([i_start, j_start]))
	historic = []
	queue = list()
	all_pos = list()
	bk = RK_BFS((i_start, j_start), n, (i_end, j_end), historic, already_done, 0, queue, all_pos)
	bk.expand()
n = int(input().strip())
(i_start, j_start, i_end, j_end) = input().strip().split(' ')
(i_start, j_start, i_end, j_end) = [int(i_start), int(j_start), int(i_end), int(j_end)]
printShortestPath(n, i_start, j_start, i_end, j_end)


import sys
dic = {'1': 'UL', '2': 'UR', '3': 'R', '4': 'LR', '5': 'LL', '6': 'L'}

def printShortestPath(n, i_start, j_start, i_end, j_end):
	moves = 0
	string = ''
	tab = []
	if 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)):
		while i_start != i_end or j_start != j_end:
			if i_start > i_end:
				if j_start >= j_end:
					string += '1 '
					moves += 1
					i_start -= 2
					j_start -= 1
				elif j_start < j_end:
					string += '2 '
					moves += 1
					i_start -= 2
					j_start += 1
			elif i_start == i_end and j_start < j_end:
				string += '3 '
				moves += 1
				j_start += 2
			elif i_start < i_end:
				if j_start <= j_end:
					string += '4 '
					moves += 1
					i_start += 2
					j_start += 1
				elif j_start > j_end:
					string += '5 '
					moves += 1
					i_start += 2
					j_start -= 1
			elif i_start == i_end and j_start > j_end:
				string += '6 '
				moves += 1
				j_start -= 2
		spl = string.split(' ')
		spl.pop()
		spl = sorted(spl)
		for item in spl:
			tab.append(dic.get(item, item))
		print(moves)
		print(' '.join(tab))
	else:
		print('Impossible')
n = int(input().strip())
(i_start, j_start, i_end, j_end) = input().strip().split(' ')
(i_start, j_start, i_end, j_end) = [int(i_start), int(j_start), int(i_end), int(j_end)]
printShortestPath(n, i_start, j_start, i_end, j_end)


import sys

def canReach(n, x0, y0, x1, y1):
	x = abs(x0 - x1)
	y = abs(y0 - y1)
	return x % 2 == 0 and (y + x / 2) % 2 == 0
order = {'UL': 0, 'UR': 1, 'R': 2, 'LR': 3, 'LL': 4, 'L': 5}

def printShortestPath(n, i_start, j_start, i_end, j_end):
	if not canReach(n, i_start, j_start, i_end, j_end):
		print('Impossible')
		return
	(x, y) = (i_start, j_start)
	ans = []
	while x != i_end or y != j_end:
		r = []
		if x > i_end:
			r.append('U')
			x -= 2
		elif x < i_end:
			r.append('L')
			x += 2
		if y > j_end:
			r.append('L')
			y -= 2 if len(r) == 1 else 1
		else:
			r.append('R')
			y += 2 if len(r) == 1 else 1
		ans.append(''.join(r))
	ans = sorted(ans, key=lambda x: order[x])
	print(len(ans))
	print(' '.join(ans))
n = int(input().strip())
(i_start, j_start, i_end, j_end) = input().strip().split(' ')
(i_start, j_start, i_end, j_end) = [int(i_start), int(j_start), int(i_end), int(j_end)]
printShortestPath(n, i_start, j_start, i_end, j_end)


import sys

class Node:
	value = None
	direction = None
	children = []
	parent = None
	visited = False
	depth = 0

	def __init__(self, value=None, direction=None):
		self.value = value
		self.direction = direction

	def isLeaf(self):
		return len(self.children) == 0

	def isRoot(self):
		return not self.parent

	def asChildOf(self, parentNode):
		self.parent = parentNode
		self.depth = parentNode.depth + 1
		parentNode.children.append(self)

	def getUL(self):
		return (self.value[0] - 2, self.value[1] - 1)

	def getUR(self):
		return (self.value[0] - 2, self.value[1] + 1)

	def getL(self):
		return (self.value[0], self.value[1] - 2)

	def getR(self):
		return (self.value[0], self.value[1] + 2)

	def getLL(self):
		return (self.value[0] + 2, self.value[1] - 1)

	def getLR(self):
		return (self.value[0] + 2, self.value[1] + 1)

	def legalCoor(self, coor, n):
		r = coor[0]
		c = coor[1]
		return (r >= 0 and r < n) and (c >= 0 and c < n)

	def isReached(self, cur, des):
		return cur == des

	def getLegalChild(self, nodes, n):
		order = ['UL', 'UR', 'R', 'LR', 'LL', 'L']
		res = dict()
		if self.legalCoor(self.getUL(), n):
			res['UL'] = self.getUL()
		if self.legalCoor(self.getUR(), n):
			res['UR'] = self.getUR()
		if self.legalCoor(self.getR(), n):
			res['R'] = self.getR()
		if self.legalCoor(self.getLR(), n):
			res['LR'] = self.getLR()
		if self.legalCoor(self.getLL(), n):
			res['LL'] = self.getLL()
		if self.legalCoor(self.getL(), n):
			res['L'] = self.getL()
		final = []
		for key in order:
			if key in res.keys() and (not nodes[res[key]].visited):
				e = nodes[res[key]]
				e.direction = key
				e.depth = self.depth + 1
				e.parent = self.value
				e.visited = True
				final.append(e)
		return final

def bfs(n, r_start, c_start, r_end, c_end, nodes):
	queue = []
	root = nodes[r_start, c_start]
	queue.append(root)
	root.visited = True
	reached = False
	while not (reached == True or queue == []):
		nextL = []
		for e in queue:
			node = nodes[e.value]
			node.visited = True
			nextL += node.getLegalChild(nodes, n)
		queue = nextL
		for e in queue:
			if e.isReached(e.value, (r_end, c_end)):
				reached = True
				break
	return nodes

def buildNodes(n):
	nodes = dict()
	for i in range(n):
		for j in range(n):
			nodes[i, j] = Node(value=(i, j))
	return nodes

def printShortestPath(n, r_start, c_start, r_end, c_end):
	nodes = buildNodes(n)
	nodes = bfs(n, r_start, c_start, r_end, c_end, nodes)
	if nodes[r_end, c_end].visited == False:
		print('Impossible')
	else:
		path = []
		end = nodes[r_end, c_end]
		print(end.depth)
		while end.parent:
			path.append(end.direction)
			end = nodes[end.parent]
		path.reverse()
		print(*path)
n = int(input().strip())
(i_start, j_start, i_end, j_end) = input().strip().split(' ')
(i_start, j_start, i_end, j_end) = [int(i_start), int(j_start), int(i_end), int(j_end)]
printShortestPath(n, i_start, j_start, i_end, j_end)


import sys
from collections import deque

def reachable(i_start, j_start, i_end, j_end):
	i_mod = abs(i_end - i_start) % 4
	j_mod = abs(j_end - j_start) % 2
	return i_mod == j_mod == 0 or (i_mod == 2 and j_mod == 1)

def printShortestPath(n, i_start, j_start, i_end, j_end):
	if not reachable(i_start, j_start, i_end, j_end):
		print('Impossible')
	else:
		move_names = {(-2, -1): 'UL', (-2, 1): 'UR', (0, 2): 'R', (2, 1): 'LR', (2, -1): 'LL', (0, -2): 'L'}
		path = shortestPath(n, i_start, j_start, i_end, j_end)
		print(len(path))
		print(' '.join((move_names[p] for p in path)))

def between(n, x, y):
	return y >= x and x <= n <= y or (y < x and y <= n <= x)

def shortestPath(n, i_start, j_start, i_end, j_end):
	end = (i_end, j_end)

	def good_moves(loc):
		for (i, j) in [(-2, -1), (-2, 1), (0, 2), (2, 1), (2, -1), (0, -2)]:
			ni = loc[0] + i
			nj = loc[1] + j
			if 0 <= ni < n and 0 <= nj < n and (between(ni, end[0], loc[0]) or between(nj, end[1], loc[1])):
				yield (ni, nj)

	def history(shortest_paths, loc):
		new_loc = shortest_paths[loc]
		path = []
		while new_loc is not None:
			path.append((loc[0] - new_loc[0], loc[1] - new_loc[1]))
			loc = new_loc
			new_loc = shortest_paths[loc]
		return list(reversed(path))
	shortest_paths = {(i_start, j_start): None}
	q = deque([(i_start, j_start)])
	while True:
		loc = q.popleft()
		for nloc in good_moves(loc):
			if nloc not in shortest_paths:
				shortest_paths[nloc] = loc
				q.append(nloc)
			if nloc == end:
				return history(shortest_paths, end)
n = int(input().strip())
(i_start, j_start, i_end, j_end) = input().strip().split(' ')
(i_start, j_start, i_end, j_end) = [int(i_start), int(j_start), int(i_end), int(j_end)]
printShortestPath(n, i_start, j_start, i_end, j_end)


import sys

def outside(x, n):
	if x['x'] < 0 or x['x'] >= n or x['y'] < 0 or (x['y'] >= n):
		return True
	else:
		return False

def printShortestPath(n, i_start, j_start, i_end, j_end):
	pos = {'x': i_start, 'y': j_start}
	des = {'x': i_end, 'y': j_end}
	nmov = 0
	direc = []
	for i in range(n):
		newpos = {'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}}
		for mov in newpos:
			newpos[mov]['d'] = abs(newpos[mov]['x'] - des['x']) + abs(newpos[mov]['y'] - des['y'])
		mov = min([(x[1]['d'], x[1]['k'], x[0]) for x in newpos.items() if not outside(x[1], n)])[2]
		if outside(newpos[mov], n) or min(newpos.items(), key=lambda x: (x[1]['d'], x[1]['k']))[1]['d'] == 1:
			print('Impossible')
			break
		pos['x'] = newpos[mov]['x']
		pos['y'] = newpos[mov]['y']
		direc.append((mov, newpos[mov]['k']))
		nmov = nmov + 1
		if pos['x'] == des['x'] and pos['y'] == des['y']:
			print(nmov)
			print(' '.join([x[0] for x in sorted(direc, key=lambda x: x[1])]))
			break
n = int(input().strip())
(i_start, j_start, i_end, j_end) = input().strip().split(' ')
(i_start, j_start, i_end, j_end) = [int(i_start), int(j_start), int(i_end), int(j_end)]
printShortestPath(n, i_start, j_start, i_end, j_end)


import sys

class Queue:

	def __init__(self):
		self.items = []

	def isEmpty(self):
		return self.items == []

	def enqueue(self, item):
		self.items.insert(0, item)

	def dequeue(self):
		return self.items.pop()

	def size(self):
		return len(self.items)

def check(n, x, y, visited):
	if x >= 0 and x < n and (y >= 0) and (y < n) and ((x, y) not in visited):
		return True
	else:
		return False

def printShortestPath(n, i_start, j_start, i_end, j_end):
	q = Queue()
	visited = set()
	all_moves = {}
	available_moves = {(-2, -1): 'UL', (-2, +1): 'UR', (0, +2): 'R', (+2, +1): 'LR', (+2, -1): 'LL', (0, -2): 'L'}
	shortest_moves = []
	dirs = [(-2, -1), (-2, +1), (0, +2), (+2, +1), (+2, -1), (0, -2)]
	q.enqueue((i_start, j_start, 0))
	while not q.isEmpty():
		(x, y, pathLen) = q.dequeue()
		if x == i_end and y == j_end:
			print(pathLen)
			previous = (x, y)
			while previous != (i_start, j_start):
				new_previous = all_moves[previous]
				dx = previous[0] - new_previous[0]
				dy = previous[1] - new_previous[1]
				shortest_moves.append(available_moves[dx, dy])
				previous = new_previous
			print(' '.join(map(str, list(reversed(shortest_moves)))))
			return 0
		for (dx, dy) in dirs:
			nx = x + dx
			ny = y + dy
			if check(n, nx, ny, visited):
				all_moves[nx, ny] = (x, y)
				q.enqueue((nx, ny, pathLen + 1))
				visited.add((nx, ny))
	return -1
n = int(input().strip())
(i_start, j_start, i_end, j_end) = input().strip().split(' ')
(i_start, j_start, i_end, j_end) = [int(i_start), int(j_start), int(i_end), int(j_end)]
result = printShortestPath(n, i_start, j_start, i_end, j_end)
if result == -1:
	print('Impossible')


t = int(input())
(x1, y1, x2, y2) = map(int, input().split())
board = [['' for i in range(t)] for j in range(t)]
board[x1][y1] = 'X'
direc = {'UL': [-2, -1], 'UR': [-2, 1], 'R': [0, 2], 'LR': [2, 1], 'LL': [2, -1], 'L': [0, -2]}
step = [(x1, y1)]
while len(step) > 0:
	(curx, cury) = (step[0][0], step[0][1])
	for d in ['UL', 'UR', 'R', 'LR', 'LL', 'L']:
		(t1, t2) = (curx + direc[d][0], cury + direc[d][1])
		if t1 >= 0 and t1 < t and (t2 >= 0) and (t2 < t) and (board[t1][t2] == ''):
			board[t1][t2] = d
			step.append((t1, t2))
	if board[x2][y2] != '':
		break
	del step[0]
if board[x2][y2] == '':
	print('Impossible')
else:
	cnt = 0
	step = []
	(x, y) = (x2, y2)
	while x != x1 or y != y1:
		step.append(board[x][y])
		(x, y) = (x - direc[board[x][y]][0], y - direc[board[x][y]][1])
		cnt += 1
	print(cnt)
	print(' '.join(step[::-1]))


def possible(si, sj, ei, ej):
	return si & 1 == ei & 1 and (si >> 1 & 1 == ei >> 1 & 1) == (sj & 1 == ej & 1)
n = int(input())
(starti, startj, endi, endj) = [int(x) for x in input().strip().split()]
(UL, UR, R, LR, LL, L) = [0] * 6
if not possible(starti, startj, endi, endj):
	print('Impossible')
	exit()
while starti != endi or startj != endj:
	if starti < endi:
		if startj <= endj and startj + 1 < n:
			LR += 1
			starti += 2
			startj += 1
		else:
			LL += 1
			starti += 2
			startj -= 1
	elif starti > endi:
		if startj <= endj and startj + 1 < n:
			UR += 1
			starti -= 2
			startj += 1
		else:
			UL += 1
			starti -= 2
			startj -= 1
	elif startj < endj:
		R += endj - startj >> 1
		startj = endj
	else:
		L += startj - endj >> 1
		startj = endj
ans = []
ans += ['UL'] * UL
ans += ['UR'] * UR
ans += ['R'] * R
ans += ['LR'] * LR
ans += ['LL'] * LL
ans += ['L'] * L
print(len(ans))
print(*ans)


import sys
from heapq import *

def printShortestPath(n, i_start, j_start, i_end, j_end):
	move_pref = {'UL': 1, 'UR': 2, 'R': 3, 'LR': 4, 'LL': 5, 'L': 6}
	visited_nodes = []
	cost_to_go = {}
	prev_node = {}
	queue = []
	cost_to_go[i_end, j_end] = 0
	heappush(queue, [0, (i_end, j_end)])
	start_reached = False
	while queue and (not start_reached):
		current_node = heappop(queue)
		current_cost = current_node[0]
		current_node = current_node[1]
		visited_nodes.append(current_node)
		if current_node == (i_start, j_start):
			start_reached = True
		else:
			neighbours = []
			if current_node[1] - 2 >= 0:
				neighbours.append([(current_node[0], current_node[1] - 2), 'R'])
			if current_node[1] + 2 < n:
				neighbours.append([(current_node[0], current_node[1] + 2), 'L'])
			if current_node[0] - 2 >= 0 and current_node[1] - 1 >= 0:
				neighbours.append([(current_node[0] - 2, current_node[1] - 1), 'LR'])
			if current_node[0] - 2 >= 0 and current_node[1] + 1 < n:
				neighbours.append([(current_node[0] - 2, current_node[1] + 1), 'LL'])
			if current_node[0] + 2 < n and current_node[1] - 1 >= 0:
				neighbours.append([(current_node[0] + 2, current_node[1] - 1), 'UR'])
			if current_node[0] + 2 < n and current_node[1] + 1 < n:
				neighbours.append([(current_node[0] + 2, current_node[1] + 1), 'UL'])
			for neighb in neighbours:
				if neighb[0] not in visited_nodes:
					if neighb[0] not in cost_to_go:
						cost_to_go[neighb[0]] = current_cost + 1
						heappush(queue, [current_cost + 1, neighb[0]])
						prev_node[neighb[0]] = [current_node, neighb[1]]
					elif current_cost + 1 < cost_to_go[neighb[0]]:
						cost_to_go[neighb[0]] = current_cost + 1
						heappush(queue, [current_cost + 1, neighb[0]])
						prev_node[neighb[0]] = [current_node, neighb[1]]
					elif current_cost + 1 == cost_to_go[neighb[0]]:
						if move_pref[neighb[1]] < move_pref[prev_node[neighb[0]][1]]:
							prev_node[neighb[0]] = [current_node, neighb[1]]
	if not start_reached:
		print('Impossible')
	else:
		on_node = (i_start, j_start)
		moves = []
		while on_node != (i_end, j_end):
			moves.append(prev_node[on_node][1])
			on_node = prev_node[on_node][0]
		print(len(moves))
		print(' '.join(moves))
n = int(input().strip())
(i_start, j_start, i_end, j_end) = input().strip().split(' ')
(i_start, j_start, i_end, j_end) = [int(i_start), int(j_start), int(i_end), int(j_end)]
printShortestPath(n, i_start, j_start, i_end, j_end)


import sys

def onBoard(n, x, y):
	return (x >= 0) & (x < n) & (y >= 0) & (y < n)

def BFS(n, board, leaves):
	nextLeaves = []
	moves = [[-2, -1, 'UL'], [-2, 1, 'UR'], [0, 2, 'R'], [2, 1, 'LR'], [2, -1, 'LL'], [0, -2, 'L']]
	for L in leaves:
		(x, y, path) = L
		for M in moves:
			(dx, dy, step) = M
			if onBoard(n, x + dx, y + dy):
				if board[x + dx][y + dy] == 2:
					return path + [step]
				elif board[x + dx][y + dy] == 0:
					board[x + dx][y + dy] = 1
					e = [x + dx, y + dy, path + [step]]
					nextLeaves.append(e)
	if nextLeaves == []:
		return 'Impossible'
	else:
		return BFS(n, board, nextLeaves)

def printShortestPath(n, i_start, j_start, i_end, j_end):
	board = []
	for i in range(n):
		board.append([0] * n)
	board[i_start][j_start] = 1
	board[i_end][j_end] = 2
	leaves = [[i_start, j_start, []]]
	p = BFS(n, board, leaves)
	if p == 'Impossible':
		print(p)
	else:
		print(len(p))
		print(' '.join(p))
n = int(input().strip())
(i_start, j_start, i_end, j_end) = input().strip().split(' ')
(i_start, j_start, i_end, j_end) = [int(i_start), int(j_start), int(i_end), int(j_end)]
printShortestPath(n, i_start, j_start, i_end, j_end)


import sys

def printShortestPath(n, i_start, j_start, i_end, j_end):
	seen = set()
	queue = [(0, i_start, j_start, [])]
	while queue:
		temp = []
		while queue:
			(count, i, j, steps) = queue.pop()
			if i < 0 or i >= n or j < 0 or (j >= n):
				continue
			if (i, j) in seen:
				continue
			seen.add((i, j))
			if i == i_end and j == j_end:
				print(count)
				print(' '.join(steps))
				return
			count += 1
			newsteps = steps[:]
			newsteps.append('UL')
			temp.append((count, i - 2, j - 1, newsteps))
			newsteps = steps[:]
			newsteps.append('UR')
			temp.append((count, i - 2, j + 1, newsteps))
			newsteps = steps[:]
			newsteps.append('R')
			temp.append((count, i, j + 2, newsteps))
			newsteps = steps[:]
			newsteps.append('LR')
			temp.append((count, i + 2, j + 1, newsteps))
			newsteps = steps[:]
			newsteps.append('LL')
			temp.append((count, i + 2, j - 1, newsteps))
			newsteps = steps[:]
			newsteps.append('L')
			temp.append((count, i, j - 2, newsteps))
		queue = list(reversed(temp))
	print('Impossible')
n = int(input().strip())
(i_start, j_start, i_end, j_end) = input().strip().split(' ')
(i_start, j_start, i_end, j_end) = [int(i_start), int(j_start), int(i_end), int(j_end)]
printShortestPath(n, i_start, j_start, i_end, j_end)


import sys

class Move:

	def __init__(self, next_i, next_j, move_name):
		self.pos_i = next_i
		self.pos_j = next_j
		self.move_name = move_name

	def __repr__(self):
		return '{}:{},{}'.format(self.move_name, self.pos_i, self.pos_j)

def printShortestPath(n, i_start, j_start, i_end, j_end):
	if not is_valid(n, i_start, j_start, i_end, j_end):
		print('Impossible')
		return
	result = get_shortest_path(n, i_start, j_start, i_end, j_end)
	priorities = {'UL': 1, 'UR': 2, 'R': 3, 'LR': 4, 'LL': 5, 'L': 6}
	result = [(priorities[n], n) for n in result]
	result.sort()
	result = [n[1] for n in result]
	print(len(result))
	print(' '.join(result))

def UL(curr_i, curr_j, last_move=None):
	return Move(curr_i - 2, curr_j - 1, 'UL')

def UR(curr_i, curr_j, last_move=None):
	return Move(curr_i - 2, curr_j + 1, 'UR')

def R(curr_i, curr_j, last_move=None):
	return Move(curr_i, curr_j + 2, 'R')

def LR(curr_i, curr_j, last_move=None):
	return Move(curr_i + 2, curr_j + 1, 'LR')

def LL(curr_i, curr_j, last_move=None):
	return Move(curr_i + 2, curr_j - 1, 'LL')

def L(curr_i, curr_j, last_move=None):
	return Move(curr_i, curr_j - 2, 'L')

def in_bounds(move, n):
	return 0 <= move.pos_i < n and 0 <= move.pos_j < n

def generate_valid_moves(curr_i, curr_j, n):
	moves = [f(curr_i, curr_j) for f in [UL, UR, R, LR, LL, L]]
	return [m for m in moves if in_bounds(m, n)]

def get_shortest_path(n, i_start, j_start, i_end, j_end):
	curr_i = i_start
	curr_j = j_start
	current_distance = abs(i_end - curr_i) + abs(j_end - curr_j)
	path = []
	while current_distance != 0:
		next_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)]
		min_dist = next_moves[0][0]
		min_move = next_moves[0][1]
		for (dist, m) in next_moves:
			if dist < min_dist:
				min_dist = dist
				min_move = m
		current_distance = min_dist
		path.append(min_move.move_name)
		curr_i = min_move.pos_i
		curr_j = min_move.pos_j
	return path

def is_valid(n, i_start, j_start, i_end, j_end):
	if abs(i_end - i_start) % 2 == 1:
		return False
	if abs(i_end - i_start) % 4 == 0 and abs(j_end - j_start) % 2 == 0:
		return True
	if abs(i_end - i_start) % 4 == 2 and abs(j_end - j_start) % 2 == 1:
		return True
	return False
n = int(input().strip())
(i_start, j_start, i_end, j_end) = input().strip().split(' ')
(i_start, j_start, i_end, j_end) = [int(i_start), int(j_start), int(i_end), int(j_end)]
printShortestPath(n, i_start, j_start, i_end, j_end)


import sys

def printShortestPath(n, ist, jst, ien, jen):
	s = []
	i = 1
	count = 0
	flag = False
	d = abs(ist - ien) + abs(jst - jen)
	while d != 0 and i < 100000:
		k = [100000] * 6
		d1 = d
		if jst - 1 >= 0 and ist - 2 >= 0:
			k[0] = abs(jst - 1 - jen) + abs(ist - 2 - ien)
		if jst + 1 < n and ist - 2 >= 0:
			k[1] = abs(jst + 1 - jen) + abs(ist - 2 - ien)
		if jst + 2 < n:
			k[2] = abs(jst + 2 - jen) + abs(ist - ien)
		if jst + 1 < n and ist + 2 < n:
			k[3] = abs(jst + 1 - jen) + abs(ist + 2 - ien)
		if jst - 1 >= 0 and ist + 2 < n:
			k[4] = abs(jst - 1 - jen) + abs(ist + 2 - ien)
		if jst - 2 >= 0:
			k[5] = abs(jst - 2 - jen) + abs(ist - ien)
		l = min(k)
		if l == k[0]:
			count += 1
			jst = jst - 1
			ist = ist - 2
			s.append(0)
		elif l == k[1]:
			count += 1
			jst = jst + 1
			ist = ist - 2
			s.append(1)
		elif l == k[2]:
			count += 1
			jst = jst + 2
			s.append(2)
		elif l == k[3]:
			count += 1
			jst = jst + 1
			ist = ist + 2
			s.append(3)
		elif l == k[4]:
			count += 1
			jst = jst - 1
			ist = ist + 2
			s.append(4)
		elif l == k[5]:
			count += 1
			jst = jst - 2
			s.append(5)
		d = abs(ist - ien) + abs(jst - jen)
		i += 1
		if d1 < d:
			flag = True
			break
	s.sort()
	for i in range(len(s)):
		if s[i] == 0:
			s[i] = 'UL'
		elif s[i] == 1:
			s[i] = 'UR'
		elif s[i] == 2:
			s[i] = 'R'
		elif s[i] == 3:
			s[i] = 'LR'
		elif s[i] == 4:
			s[i] = 'LL'
		else:
			s[i] = 'L'
	if flag == True or d != 0:
		print('Impossible')
	elif d == 0:
		print(count)
		print(*s)
n = int(input().strip())
(i_start, j_start, i_end, j_end) = input().strip().split(' ')
(i_start, j_start, i_end, j_end) = [int(i_start), int(j_start), int(i_end), int(j_end)]
printShortestPath(n, i_start, j_start, i_end, j_end)


import math
dim = int(input())
(sJ, sI, eJ, eI) = map(int, input().split())
bot = (sI, sJ)
point = (eI, eJ)
arr = [(-1, 2), (1, 2), (-2, 0), (2, 0), (-1, -2), (1, -2)]
values = ['LL', 'LR', 'L', 'R', 'UL', 'UR']
moves = list(zip(values, arr))
prior = dict(zip(['UL', 'UR', 'R', 'LR', 'LL', 'L'], list(range(1, 7))))
ordering = []

def manhattan(bot, point):
	return math.sqrt((bot[0] - point[0]) ** 2 + (bot[1] - point[1]) ** 2)

def optim(arr):
	temp = {}
	for i in arr:
		try:
			x = (bot[0] + i[1][0], bot[1] + i[1][1])
			temp[i[0]] = x
		except:
			pass
	optimumValue = min((manhattan(temp[k], point) for k in temp))
	priority = {i: j for (i, j) in temp.items() if manhattan(j, point) == optimumValue}
	val = min(priority, key=lambda k: prior[k])
	return (val, temp[val])
repeats = set()
flag = False
while bot != point:
	(val, bot) = optim(moves)
	ordering.append(val)
	if bot not in repeats:
		repeats.add(bot)
	else:
		flag = True
		break
if flag:
	print('Impossible')
else:
	print(len(ordering))
	output = sorted(ordering, key=lambda k: prior[k])
	print(*output)


import sys

def printShortestPath(n, i_start, j_start, i_end, j_end):
	moves = 0
	res = []
	if (i_end - i_start) % 2 != 0:
		print('Impossible')
		return res
	else:
		iturns = int((i_end - i_start) / 2)
		if (abs(j_end - j_start) - abs(iturns)) % 2 != 0:
			print('Impossible')
			return res
		else:
			i_curr = i_start
			j_curr = j_start
			while i_curr != i_end or j_curr != j_end:
				moves += 1
				if i_curr > i_end:
					i_curr -= 2
					if j_curr >= j_end - int((i_curr - i_end) / 2 - 1) and j_curr > 0:
						res.append('UL')
						j_curr -= 1
					else:
						res.append('UR')
						j_curr += 1
				elif i_curr <= i_end and j_curr < j_end - 1 - int((i_end - i_curr) / 2):
					j_curr += 2
					res.append('R')
				elif i_curr < i_end:
					i_curr += 2
					if j_curr <= j_end + int((i_end - i_curr) / 2) and j_curr < n - 1:
						res.append('LR')
						j_curr += 1
					else:
						res.append('LL')
						j_curr -= 1
				else:
					j_curr -= 2
					res.append('L')
			print(moves)
			print(' '.join(res))
			return res
n = int(input().strip())
(i_start, j_start, i_end, j_end) = input().strip().split(' ')
(i_start, j_start, i_end, j_end) = [int(i_start), int(j_start), int(i_end), int(j_end)]
printShortestPath(n, i_start, j_start, i_end, j_end)


from collections import deque, namedtuple
Point = namedtuple('Point', ['x', 'y'])
Path = namedtuple('Path', ['point', 'moves'])
MOVES = (('UL', Point(-1, -2)), ('UR', Point(1, -2)), ('R', Point(2, 0)), ('LR', Point(1, 2)), ('LL', Point(-1, 2)), ('L', Point(-2, 0)))

def valid_moves(size, start):
	valid = []
	for (name, move) in MOVES:
		current = Point(start.x + move.x, start.y + move.y)
		if min(current.x, current.y) >= 0 and max(current.x, current.y) < size:
			valid.append((name, current))
	return valid

def find_shortest(size, start_y, start_x, end_y, end_x):
	routes = deque()
	visited = {}
	target = Point(end_x, end_y)
	current = Path(Point(start_x, start_y), [])
	while current.point != target:
		for (move, point) in valid_moves(size, current.point):
			previous = visited.get(point)
			if not previous or len(current.moves) < previous:
				routes.append(Path(point, current.moves + [move]))
				visited[point] = len(current.moves)
		if not routes:
			return
		current = routes.popleft()
	return current.moves

def printShortestPath(size, start_y, start_x, end_y, end_x):
	path = find_shortest(size, start_y, start_x, end_y, end_x)
	if not path:
		print('Impossible')
	else:
		print(len(path))
		print(' '.join(path))
n = int(input().strip())
(i_start, j_start, i_end, j_end) = input().strip().split(' ')
(i_start, j_start, i_end, j_end) = [int(i_start), int(j_start), int(i_end), int(j_end)]
printShortestPath(n, i_start, j_start, i_end, j_end)


import sys
n = int(input().strip())
table = [[-1 for _ in range(n + 1)] for _ in range(n + 1)]
(i_start, j_start, i_end, j_end) = input().strip().split(' ')
(i_start, j_start, i_end, j_end) = [int(i_start) + 1, int(j_start) + 1, int(i_end) + 1, int(j_end) + 1]
n = 21
mid = n // 2 + 1
diffx = mid - i_start
diffy = mid - j_start
i = mid
j = mid
endi = i_end + diffx
endj = j_end + diffy
ans = 0
rb_diagonal = []
if 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)):
	print('Impossible')
elif i == endi and j == endj:
	print(0)
elif i == endi and j != endj:
	if endj > j:
		ans = abs(endj - j) // 2
		print(ans)
		print('R ' * ans)
	else:
		ans = abs(j - endj) // 2
		print(ans)
		print('L ' * ans)
elif i != endi and j == endj:
	if i > endi:
		ans = abs(i - endi) // 4
		print(2 * ans)
		print('UL UR ' * ans)
	else:
		ans = abs(endi - i) // 4
		print(2 * ans)
		print('LR LL ' * ans)
elif endi < i and endj < j:
	Str = ''
	rdiff = abs(i - endi)
	N_ul = rdiff // 2
	ans += N_ul
	cnew = abs(j - N_ul)
	Str += 'UL ' * N_ul
	if cnew >= endj:
		cdiff = abs(cnew - endj)
		N_l = cdiff // 2
		ans += N_l
		Str += 'L ' * N_l
		print(ans)
		print(Str)
	else:
		cdiff = abs(endj - cnew)
		N_r = cdiff // 2
		ans += N_r
		Str += 'L ' * N_r
		print(ans)
		print(Str)
elif endi < i and endj > j:
	Str = ''
	rdiff = abs(i - endi)
	N_ur = rdiff // 2
	ans += N_ur
	cnew = i + N_ur
	Str += 'UR ' * N_ur
	if cnew >= endj:
		cdiff = abs(cnew - endj)
		N_l = cdiff // 2
		ans += N_l
		Str += 'L ' * N_l
		print(ans)
		print(Str)
	else:
		cdiff = abs(endj - cnew)
		N_r = cdiff // 2
		ans += N_r
		Str += 'R ' * N_r
		print(ans)
		print(Str)
elif endi > i and endj < j:
	if (endi - i) // 2 > j - endj:
		ti = endi
		tj = endj
		count = 0
		while (ti - i) // 2 != tj - j:
			count += 1
			ti -= 2
			tj += 1
		Str = ''
		N_lr = (ti - i) // 2
		N_ll = count
		Str += 'LR ' * N_lr
		Str += 'LL ' * N_ll
		ans += N_lr + N_ll
		print(ans)
		print(Str)
	else:
		rdiff = abs(endi - i)
		N_ll = rdiff // 2
		ans += N_ll
		cnew = abs(j - N_ll)
		Str += 'LL ' * N_ll
		if cnew >= endj:
			cdiff = abs(cnew - endj)
			N_l = cdiff // 2
			Str += 'L ' * N_l
			ans += N_l
			print(ans)
			print(Str)
		else:
			cdiff = abs(endj - cnew)
			N_r = cdiff // 2
			Str += 'R ' * N_r
			ans += N_r
			print(ans)
			print(Str)
elif (endi - i) // 2 > endj - j:
	Str = ''
	count = 0
	ti = endi
	tj = endj
	while (ti - i) // 2 != tj - j:
		count += 1
		ti -= 2
		tj += 1
	N_lr = (ti - i) // 2
	N_ll = count
	Str += 'LR ' * N_lr
	Str += 'LL ' * N_ll
	ans += N_lr + N_ll
	print(ans)
	print(Str)
else:
	rdiff = abs(endi - i)
	N_lr = rdiff // 2
	cnew = j + N_lr
	Str = ''
	ans += N_lr
	cdiff = abs(cnew - endj)
	N_r = cdiff // 2
	Str += 'R ' * N_r
	Str += 'LR ' * N_lr
	ans += N_r
	print(ans)
	print(Str)


import sys

def options(n, tup):
	options = []
	i = tup[0]
	j = tup[1]
	if i - 2 >= 0:
		if j - 1 >= 0:
			options.append((i - 2, j - 1))
		if j + 1 < n:
			options.append((i - 2, j + 1))
	if j + 2 < n:
		options.append((i, j + 2))
	if i + 2 < n:
		if j + 1 < n:
			options.append((i + 2, j + 1))
		if j - 1 >= 0:
			options.append((i + 2, j - 1))
	if j - 2 >= 0:
		options.append((i, j - 2))
	return options

def whatMove(cur, prev):
	di = cur[0] - prev[0]
	dj = cur[1] - prev[1]
	if di == 0:
		if dj == -2:
			return 'L'
		if dj == 2:
			return 'R'
	if di == -2:
		if dj == -1:
			return 'UL'
		if dj == 1:
			return 'UR'
	if di == 2:
		if dj == -1:
			return 'LL'
		if dj == 1:
			return 'LR'

def printShortestPath(n, i_start, j_start, i_end, j_end):
	prev = {}
	visited = []
	queue = [(i_start, j_start)]
	while queue:
		current = queue.pop(0)
		visited.append(current)
		if current == (i_end, j_end):
			path = []
			while current != (i_start, j_start):
				parent = prev[current]
				path.append(whatMove(current, parent))
				current = parent
			print(len(path))
			path.reverse()
			print(*path)
			return
		for option in options(n, current):
			if option not in visited and option not in queue:
				prev[option] = current
				queue.append(option)
	print('Impossible')
n = int(input().strip())
(i_start, j_start, i_end, j_end) = input().strip().split(' ')
(i_start, j_start, i_end, j_end) = [int(i_start), int(j_start), int(i_end), int(j_end)]
printShortestPath(n, i_start, j_start, i_end, j_end)


import sys

def printShortestPath(n, i_start, j_start, i_end, j_end):
	q = []
	v = [i_start, j_start]
	q.append(v)
	while len(q) > 0:
		cv = q.pop(0)
		nd = chess[cv[0]][cv[1]] + 1
		si = cv[0]
		sj = cv[1]
		possibleN = [[si - 2, sj - 1], [si - 2, sj + 1], [si, sj + 2], [si + 2, sj + 1], [si + 2, sj - 1], [si, sj - 2]]
		for (mov, nei) in enumerate(possibleN, 1):
			ii = nei[0]
			jj = nei[1]
			if ii < 0 or ii > n - 1 or jj < 0 or (jj > n - 1):
				continue
			elif chess[ii][jj] != 0:
				continue
			else:
				chess[ii][jj] = nd
				pre[ii][jj] = cv
				choices[ii][jj] = mov
				q.append(nei)
				if cv == [i_end, j_end]:
					return 0
	return 0
n = int(input().strip())
(i_start, j_start, i_end, j_end) = input().strip().split(' ')
(i_start, j_start, i_end, j_end) = [int(i_start), int(j_start), int(i_end), int(j_end)]
chess = [[0 for i in range(n)] for j in range(n)]
pre = [[None for i in range(n)] for j in range(n)]
choices = [[0 for i in range(n)] for j in range(n)]
printShortestPath(n, i_start, j_start, i_end, j_end)
spath = chess[i_end][j_end]
dicto = {1: 'UL', 2: 'UR', 3: 'R', 4: 'LR', 5: 'LL', 6: 'L'}
res = []
if spath <= 0:
	print('Impossible')
else:
	print(spath)
	for i in range(spath):
		flag = choices[i_end][j_end]
		res.append(dicto[flag])
		(i_end, j_end) = pre[i_end][j_end]
	for j in range(len(res) - 1, -1, -1):
		print(res[j], end=' ')


import sys

def printShortestPath(n, i_start, j_start, i_end, j_end):

	def is_valid(p):
		if 0 <= p[0] < n and 0 <= p[1] < n:
			return True
		return False
	from collections import deque
	B = [[-1] * n for _ in range(n)]
	q = deque()
	start = (i_start, j_start)
	q.append(start)
	B[i_start][j_start] = -2
	moves = [(-2, -1), (-2, 1), (0, 2), (2, 1), (2, -1), (0, -2)]
	moves_str = ['UL', 'UR', 'R', 'LR', 'LL', 'L']
	while q:
		p = q.popleft()
		for (i, move) in enumerate(moves):
			new_p = (p[0] + move[0], p[1] + move[1])
			if is_valid(new_p) and B[new_p[0]][new_p[1]] == -1:
				B[new_p[0]][new_p[1]] = i
				if new_p == (i_end, j_end):
					q = []
					break
				q.append(new_p)
	if B[i_end][j_end] != -1:
		(i, j) = (i_end, j_end)
		results = []
		while i != i_start or j != j_start:
			idx = B[i][j]
			results.append(moves_str[idx])
			i -= moves[idx][0]
			j -= moves[idx][1]
		print(len(results))
		results.reverse()
		print(' '.join(results))
	else:
		print('Impossible')
n = int(input().strip())
(i_start, j_start, i_end, j_end) = input().strip().split(' ')
(i_start, j_start, i_end, j_end) = [int(i_start), int(j_start), int(i_end), int(j_end)]
printShortestPath(n, i_start, j_start, i_end, j_end)


import sys
from collections import deque

def printShortestPath(n, i_start, j_start, i_end, j_end):
	assert 5 <= n <= 200
	assert (i_start, j_start) != (i_end, j_end)
	(is_reachable, directions) = find_path(n, i_start, j_start, i_end, j_end)
	if is_reachable:
		print(len(directions))
		print(*directions, sep=' ')
	else:
		print('Impossible')

def find_path(n, i_s, j_s, i_e, j_e):
	is_reachable = False
	(ci, cj) = (i_s, j_s)
	parent = [[None for _ in range(n)] for _ in range(n)]
	parent[ci][cj] = (ci, cj)
	q = deque()
	q.append((ci, cj))
	while q:
		(ci, cj) = q.popleft()
		if (ci, cj) == (i_e, j_e):
			is_reachable = True
			break
		for (ni, nj) in next_moves(n, ci, cj):
			if parent[ni][nj]:
				continue
			parent[ni][nj] = (ci, cj)
			q.append((ni, nj))
	if is_reachable:
		return (True, conf_path(parent, n, i_s, j_s, i_e, j_e))
	else:
		return (False, [])

def next_moves(n, i, j):
	didjs = [(-2, -1), (-2, 1), (0, 2), (2, 1), (2, -1), (0, -2)]
	for (di, dj) in didjs:
		(ni, nj) = (i + di, j + dj)
		if 0 <= ni < n and 0 <= nj < n:
			yield (ni, nj)

def conf_path(parent, n, i_s, j_s, i_e, j_e):
	assert parent[i_s][j_s] == (i_s, j_s)
	assert parent[i_e][j_e] != None
	(i, j) = (i_e, j_e)
	stack = []
	while (i, j) != (i_s, j_s):
		stack.append((i, j))
		(i, j) = parent[i][j]
	assert (i, j) == (i_s, j_s)
	stack.append((i_s, j_s))
	didjs = {(-2, 1): 'UR', (0, 2): 'R', (2, 1): 'LR', (2, -1): 'LL', (0, -2): 'L', (-2, -1): 'UL'}
	directions = []
	nodes = stack[::-1]
	for x in range(len(nodes) - 1):
		((ai, aj), (bi, bj)) = (nodes[x], nodes[x + 1])
		direction = didjs[bi - ai, bj - aj]
		directions.append(direction)
	return directions
n = int(input().strip())
(i_start, j_start, i_end, j_end) = input().strip().split(' ')
(i_start, j_start, i_end, j_end) = [int(i_start), int(j_start), int(i_end), int(j_end)]
printShortestPath(n, i_start, j_start, i_end, j_end)


import sys
import math
moveset_dict = {(-2, -1): 'UL', (-2, 1): 'UR', (0, 2): 'R', (2, 1): 'LR', (2, -1): 'LL', (0, -2): 'L'}
moveset = [(-2, -1), (-2, 1), (0, 2), (2, 1), (2, -1), (0, -2)]

def printShortestPath(n, i_start, j_start, i_end, j_end):
	matrix = [[() for c in range(n)] for r in range(n)]
	queue = [(i_start, j_start)]
	while queue:
		(r_pos, c_pos) = queue.pop(0)
		moves = get_moves(r_pos, c_pos)
		for move in moves:
			(add_r, add_c) = move
			(new_r, new_c) = (r_pos + add_r, c_pos + add_c)
			if not matrix[new_r][new_c]:
				queue.append((new_r, new_c))
				matrix[new_r][new_c] = move
	to_prev = matrix[i_end][j_end]
	if not to_prev:
		print('Impossible')
	else:
		num_moves = 0
		path = ''
		r = i_end
		c = j_end
		while r != i_start or c != j_start:
			move = moveset_dict[to_prev]
			path = move + ' ' + path
			r -= to_prev[0]
			c -= to_prev[1]
			to_prev = matrix[r][c]
			num_moves += 1
		print(num_moves)
		print(path[:-1])

def get_moves(r_pos, c_pos):
	moves = []
	for move in moveset:
		if 0 <= r_pos + move[0] < n and 0 <= c_pos + move[1] < n:
			moves.append(move)
	return moves
n = int(input().strip())
(i_start, j_start, i_end, j_end) = input().strip().split(' ')
(i_start, j_start, i_end, j_end) = [int(i_start), int(j_start), int(i_end), int(j_end)]
printShortestPath(n, i_start, j_start, i_end, j_end)


import sys
move = []
my_own_order = ['UL', 'UR', 'R', 'LR', 'LL', 'L']
order = {key: i for (i, key) in enumerate(my_own_order)}

def printShortestPath(n, i_start, j_start, i_end, j_end):
	diff_i = i_end - i_start
	diff_j = j_end - j_start
	if diff_i == 0 and diff_j == 0:
		print(len(move))
		print(' '.join(sorted(move, key=lambda d: order[d])))
		return
	if diff_i % 2 != 0:
		print('Impossible')
		return
	elif diff_i < 0:
		if diff_j <= 0:
			move.append('UL')
			printShortestPath(n, i_start - 2, j_start - 1, i_end, j_end)
		if diff_j > 0:
			move.append('UR')
			printShortestPath(n, i_start - 2, j_start + 1, i_end, j_end)
	elif diff_i > 0:
		if diff_j < 0:
			move.append('LL')
			printShortestPath(n, i_start + 2, j_start - 1, i_end, j_end)
		if diff_j >= 0:
			move.append('LR')
			printShortestPath(n, i_start + 2, j_start + 1, i_end, j_end)
	elif diff_i == 0:
		if diff_j % 2 != 0:
			print('Impossible')
			return
		elif diff_j > 0:
			move.append('R')
			printShortestPath(n, i_start, j_start + 2, i_end, j_end)
		elif diff_j < 0:
			move.append('L')
			printShortestPath(n, i_start, j_start - 2, i_end, j_end)
n = int(input().strip())
(i_start, j_start, i_end, j_end) = input().strip().split(' ')
(i_start, j_start, i_end, j_end) = [int(i_start), int(j_start), int(i_end), int(j_end)]
printShortestPath(n, i_start, j_start, i_end, j_end)


import sys

def printShortestPath(n, i_start, j_start, i_end, j_end):
	x = j_end - j_start
	y = i_end - i_start
	steps = []
	if y % 2 == 1:
		print('Impossible')
		return
	while y != 0:
		if y < 0:
			y += 2
			if x <= 0:
				x += 1
				steps.append('UL')
			else:
				x -= 1
				steps.append('UR')
		else:
			y -= 2
			if x <= 0:
				x += 1
				steps.append('LL')
			else:
				x -= 1
				steps.append('LR')
	if x % 2 == 1:
		print('Impossible')
		return
	while x != 0:
		if x >= 0:
			x -= 2
			steps.append('R')
		else:
			x += 2
			steps.append('L')
	myorder = ['UL', 'UR', 'R', 'LR', 'LL', 'L']
	steps.sort(key=lambda v: myorder.index(v))
	print(len(steps))
	print(' '.join(steps))
n = int(input().strip())
(i_start, j_start, i_end, j_end) = input().strip().split(' ')
(i_start, j_start, i_end, j_end) = [int(i_start), int(j_start), int(i_end), int(j_end)]
printShortestPath(n, i_start, j_start, i_end, j_end)


import sys
arr = [[-1, 2], [1, 2], [2, 0], [1, -2], [-1, -2], [0, -2]]

def printShortestPath(n1, i_start, j_start, i_end, j_end):
	x = j_end - j_start
	y = i_end - i_start
	st = ''
	n = 0
	c1 = 0
	c2 = 0
	c3 = 0
	c4 = 0
	r = 0
	flag = 0
	while (x != 0 or y != 0) and flag == 0:
		while x > 0 and flag == 0:
			if y > 0:
				c1 = 1
				st += 'LR '
				y -= 2
				x -= 1
				j_start += 1
				i_start += 2
				if j_start >= n1 or i_start >= n1 or j_start < 0 or (i_start < 0):
					flag = 1
					break
				n += 1
				if y < 0 or y == 1:
					flag = 1
					break
				if x == 0 and y == 0:
					break
			elif y == 0:
				if x % 2 == 0:
					if c1 == 1:
						st = 'R ' + st
					else:
						st += 'R '
					x = x - 2
					j_start += 2
					if j_start >= n1 or i_start >= n1 or j_start < 0 or (i_start < 0):
						flag = 1
						break
					n += 1
				else:
					flag = 1
					break
			elif y + 2 > 0:
				flag = 1
				break
			else:
				y += 2
				x -= 1
				st += 'UR '
				r = 1
				n += 1
				j_start += 1
				i_start -= 2
				if j_start >= n1 or i_start >= n1 or j_start < 0 or (i_start < 0):
					flag = 1
					break
				if y > 0:
					flag = 1
					break
		while x < 0 and flag == 0:
			if y > 0:
				st += 'LL '
				y -= 2
				x += 1
				c2 = 1
				n += 1
				j_start -= 1
				i_start += 2
				if j_start >= n1 or i_start >= n1 or j_start < 0 or (i_start < 0):
					flag = 1
					break
				if y < 0:
					flag = 1
					break
				if x == 0 and y == 0:
					break
			elif y == 0:
				while x < 0 and abs(x) % 2 == 0:
					st += 'L '
					x = x + 2
					j_start -= 2
					if j_start >= n1 or i_start >= n1 or j_start < 0 or (i_start < 0):
						flag = 1
						break
					n += 1
				if x != 0:
					flag = 1
					break
			else:
				y += 2
				x += 1
				st += 'UL '
				n += 1
				j_start -= 1
				i_start -= 2
				if j_start >= n1 or i_start >= n1 or j_start < 0 or (i_start < 0):
					flag = 1
					break
				if y > 0:
					flag = 1
					break
		while x == 0 and flag == 0:
			if y > 0:
				if y % 4 == 0:
					y -= 4
					if c2 == 0 and c4 == 0:
						st += 'LR LL '
						c4 = 1
					elif c2 == 0 and c4 == 1:
						st = 'LR ' + st + 'LL '
					else:
						st = 'LR LL ' + st
					n += 2
					i_start += 4
					if j_start >= n1 or i_start >= n1 or j_start < 0 or (i_start < 0):
						flag = 1
						break
				else:
					flag = 1
					break
			elif y == 0:
				break
			elif abs(y) % 4 == 0:
				if r == 0 and c3 == 0:
					st += 'UL UR '
					c3 = 1
				elif r == 0 and c3 == 1:
					st = 'UL ' + st + 'UR '
				else:
					st = 'UL UR ' + st
				y += 4
				n += 2
				i_start -= 4
				if j_start >= n1 or i_start >= n1 or j_start < 0 or (i_start < 0):
					flag = 1
					break
				if y > 0:
					flag = 1
					break
			else:
				flag = 1
				break
	if flag == 0:
		print(n)
		l = st.strip().split(' ')
		order = {'UL': 1, 'UR': 2, 'R': 3, 'LR': 4, 'LL': 5, 'L': 6}
		order_rev = {1: 'UL', 2: 'UR', 3: 'R', 4: 'LR', 5: 'LL', 6: 'L'}
		st2 = []
		for i in l:
			st2.append(order[i])
		st2.sort()
		st3 = ''
		for i in st2:
			st3 += order_rev[i] + ' '
		print(st3.strip())
	else:
		print('Impossible')
n = int(input().strip())
(i_start, j_start, i_end, j_end) = input().strip().split(' ')
(i_start, j_start, i_end, j_end) = [int(i_start), int(j_start), int(i_end), int(j_end)]
printShortestPath(n, i_start, j_start, i_end, j_end)


import sys

def printShortestPath(n, i_start, j_start, i_end, j_end):
	dir_map = {'UL': (-1, -2), 'UR': (1, -2), 'R': (2, 0), 'LL': (-1, 2), 'LR': (1, 2), 'L': (-2, 0)}
	next_posd = lambda xy, d: (xy[0] + dir_map[d][0], xy[1] + dir_map[d][1], d)
	path_order = ['UL', 'UR', 'R', 'LR', 'LL', 'L']
	all_starts = [(j_start, i_start, d)[:2] for d in path_order]
	visited = set()
	goal = (j_end, i_end)
	q = [all_starts[0]]
	reached_goal = False
	goal_node = None
	reverse_path = {}
	while len(q) > 0:
		curd = q.pop(0)
		if reached_goal:
			break
		if (curd[0], curd[1]) == goal:
			goal_node = curd
			break
		for d in path_order:
			next_curd = next_posd(curd[:2], d)
			if next_curd[0] >= 0 and next_curd[0] < n and (next_curd[1] >= 0) and (next_curd[1] < n):
				if next_curd[:2] not in visited:
					q.append(next_curd)
					visited.add(next_curd[:2])
					reverse_path[next_curd] = curd
					if (next_curd[0], next_curd[1]) == goal:
						reached_goal = True
						goal_node = next_curd
						break
	if goal_node is None:
		print('Impossible')
		return
	cur = goal_node
	path = []
	while cur != all_starts[0]:
		path += [cur[2]]
		cur = reverse_path[cur]
	print(len(path))
	print(*path[::-1])
n = int(input().strip())
(i_start, j_start, i_end, j_end) = input().strip().split(' ')
(i_start, j_start, i_end, j_end) = [int(i_start), int(j_start), int(i_end), int(j_end)]
printShortestPath(n, i_start, j_start, i_end, j_end)


class Move(object):

	def __init__(self, i, j, move, prior):
		self.i = i
		self.j = j
		self.move = move
		self.prior = prior

def on_board(n, i, j):
	if i < 0 or i > n - 1:
		return False
	if j < 0 or j > n - 1:
		return False
	return True

def get_path(final_move):
	move_list = []
	last_move = final_move
	while last_move.prior:
		move_list.append(last_move.move)
		last_move = last_move.prior
	move_list.reverse()
	return move_list

def get_moves(previously_occupied, queue, i_end, j_end):
	moves = []
	while queue:
		move = queue.pop(0)
		i = move.i
		j = move.j
		if i == i_end and j == j_end:
			moves = get_path(move)
			break
		if on_board(n, i - 2, j - 1):
			if not previously_occupied[i - 2][j - 1]:
				queue.append(Move(i - 2, j - 1, 'UL', move))
				previously_occupied[i - 2][j - 1] = True
		if on_board(n, i - 2, j + 1):
			if not previously_occupied[i - 2][j + 1]:
				queue.append(Move(i - 2, j + 1, 'UR', move))
				previously_occupied[i - 2][j + 1] = True
		if on_board(n, i, j + 2):
			if not previously_occupied[i][j + 2]:
				queue.append(Move(i, j + 2, 'R', move))
				previously_occupied[i][j + 2] = True
		if on_board(n, i + 2, j + 1):
			if not previously_occupied[i + 2][j + 1]:
				queue.append(Move(i + 2, j + 1, 'LR', move))
				previously_occupied[i + 2][j + 1] = True
		if on_board(n, i + 2, j - 1):
			if not previously_occupied[i + 2][j - 1]:
				queue.append(Move(i + 2, j - 1, 'LL', move))
				previously_occupied[i + 2][j - 1] = True
		if on_board(n, i, j - 2):
			if not previously_occupied[i][j - 2]:
				queue.append(Move(i, j - 2, 'L', move))
				previously_occupied[i][j - 2] = True
	return moves

def printShortestPath(n, i_start, j_start, i_end, j_end):
	move_queue = [Move(i_start, j_start, None, None)]
	board = [[False] * n for _ in range(n)]
	moves = get_moves(board, move_queue, i_end, j_end)
	if not moves:
		print('Impossible')
	else:
		print(len(moves))
		print(' '.join(moves))
n = int(input().strip())
(i_start, j_start, i_end, j_end) = input().strip().split(' ')
(i_start, j_start, i_end, j_end) = [int(i_start), int(j_start), int(i_end), int(j_end)]
printShortestPath(n, i_start, j_start, i_end, j_end)


from operator import itemgetter
n = int(input())
(si, sj, ei, ej) = map(int, input().split())
ui = si
uj = sj
check = 0
path = []
if abs(si - ei) % 2 == 1:
	print('Impossible')
elif abs(sj - ej) % 2 == 1 and si == ei:
	print('Impossible')
else:
	while True:
		c = 0
		if uj == ej:
			c = 1
			for i in range(abs(ui - ei) // 4):
				if ei > ui:
					path.append('LR')
					path.append('LL')
					ui = ui + 4
				else:
					print('UR', end=' ')
					print('UL', end=' ')
					ui = ui - 4
		if ui == ei:
			c = 1
			for i in range(abs(uj - ej) // 2):
				if uj > ej:
					path.append('L')
					uj = uj - 2
				else:
					path.append('R')
					uj = uj + 2
		if c == 0:
			if ui < ei:
				if uj < ej:
					path.append('LR')
					uj += 1
					ui += 2
				else:
					path.append('LL')
					uj -= 1
					ui += 2
			elif uj < ej:
				path.append('UR')
				uj += 1
				ui -= 2
			else:
				path.append('UL')
				uj -= 1
				ui -= 2
		if abs(ui - ei) == 1 and abs(uj - ej) == 1:
			check = 1
		if abs(ui - ei) == 1 and abs(uj - ej) == 0:
			check = 1
		if abs(ui - ei) == 0 and abs(uj - ej) == 1:
			check = 1
		if abs(ui - ei) == 2 and abs(uj - ej) == 0:
			check = 1
		if ui >= n or uj >= n:
			check = 1
		if ui == ei and uj == ej:
			break
		if check == 1:
			break
p = 1
if check == 0:
	pr = []
	for i in path:
		if i == 'UL':
			pr.append(1)
		if i == 'UR':
			pr.append(2)
		if i == 'R':
			pr.append(3)
		if i == 'LR':
			pr.append(4)
		if i == 'LL':
			pr.append(5)
		if i == 'L':
			pr.append(6)
	spath = list(zip(pr, path))
	spath.sort(key=itemgetter(0))
	print(len(path) or '')
	for i in range(len(path)):
		print(spath[i][1], end=' ')
else:
	print('Impossible')


import sys
move = {'UL': (-2, -1, 0), 'UR': (-2, 1, 1), 'R': (0, 2, 2), 'LR': (2, 1, 3), 'LL': (2, -1, 4), 'L': (0, -2, 5)}

def reorder(moves):
	return sorted(moves, key=lambda x: move[x][2])

def printShortestPath(n, i_start, j_start, i_end, j_end):
	if abs(i_start - i_end) % 2:
		print('Impossible')
		return
	if (j_start - j_end) % 2 - (i_start - i_end) / 2 % 2 != 0:
		print('Impossible')
		return
	moves = []
	i_curr = i_start
	j_curr = j_start
	while i_curr < i_end:
		if j_curr <= j_end:
			key = 'LR'
		else:
			key = 'LL'
		moves += [key]
		i_curr += move[key][0]
		j_curr += move[key][1]
	while i_curr > i_end:
		if j_curr >= j_end:
			key = 'UL'
		else:
			key = 'UR'
		moves += [key]
		i_curr += move[key][0]
		j_curr += move[key][1]
	while j_curr > j_end:
		key = 'L'
		moves += [key]
		i_curr += move[key][0]
		j_curr += move[key][1]
	while j_curr < j_end:
		key = 'R'
		moves += [key]
		i_curr += move[key][0]
		j_curr += move[key][1]
	moves = reorder(moves)
	print(len(moves))
	print(' '.join(moves))
n = int(input().strip())
(i_start, j_start, i_end, j_end) = input().strip().split(' ')
(i_start, j_start, i_end, j_end) = [int(i_start), int(j_start), int(i_end), int(j_end)]
printShortestPath(n, i_start, j_start, i_end, j_end)


import sys

def printShortestPath(n, i_start, j_start, i_end, j_end):
	if i_start % 2 != i_end % 2 or abs((i_start - i_end) // 2) % 2 != abs(j_start - j_end) % 2:
		print('Impossible')
	else:
		ans = []
		while i_start > i_end:
			i_start -= 2
			if j_start + 1 < n and (j_start < j_end or abs(j_start + 1 - j_end) <= (i_start - i_end) // 2):
				j_start += 1
				ans.append('UR')
			else:
				j_start -= 1
				ans.append('UL')
		while j_start < j_end and abs(j_start - j_end) > (i_end - i_start) // 2:
			j_start += 2
			ans.append('R')
		while i_start < i_end:
			i_start += 2
			if j_start + 1 < n and (j_start < j_end or abs(j_start + 1 - j_end) <= (i_end - i_start) // 2):
				j_start += 1
				ans.append('LR')
			else:
				j_start -= 1
				ans.append('LL')
		while j_start > j_end:
			j_start -= 2
			ans.append('L')
		print(len(ans))
		print(' '.join(ans))
n = int(input().strip())
(i_start, j_start, i_end, j_end) = input().strip().split(' ')
(i_start, j_start, i_end, j_end) = [int(i_start), int(j_start), int(i_end), int(j_end)]
printShortestPath(n, i_start, j_start, i_end, j_end)


import sys
d = {1: 'UL', 2: 'UR', 3: 'R', 4: 'LR', 5: 'LL', 6: 'L'}

def printShortestPath(n, i_start, j_start, i_end, j_end):
	moves = []
	counter = 0
	if (i_start - i_end) % 2 == 1:
		print('Impossible')
	elif (i_start - i_end) % 4 == 2 and (j_start - j_end) % 2 == 0:
		print('Impossible')
	elif (i_start - i_end) % 4 == 0 and (j_start - j_end) % 2 == 1:
		print('Impossible')
	else:
		while abs(i_start - i_end) + abs(j_start - j_end) > 0:
			counter += 1
			if i_start == i_end:
				if j_start > j_end:
					moves.append(6)
					j_start -= 2
				else:
					moves.append(3)
					j_start += 2
			elif i_end > i_start:
				i_start += 2
				if j_start <= j_end and j_start != n - 1:
					moves.append(4)
					j_start += 1
				else:
					moves.append(5)
					j_start -= 1
			else:
				i_start -= 2
				if j_start >= j_end and j_start != 0:
					moves.append(1)
					j_start -= 1
				else:
					moves.append(2)
					j_start += 1
		moves = sorted(moves)
		print(counter)
		for m in moves:
			print(d[m], end=' ')
n = int(input().strip())
(i_start, j_start, i_end, j_end) = input().strip().split(' ')
(i_start, j_start, i_end, j_end) = [int(i_start), int(j_start), int(i_end), int(j_end)]
printShortestPath(n, i_start, j_start, i_end, j_end)


from collections import deque
import sys

def printShortestPath(n, i_start, j_start, i_end, j_end):
	(iDiff, jDiff) = (i_end - i_start, j_end - j_start)
	if iDiff % 2 == 1 or (iDiff / 2 - jDiff) % 2 == 1:
		print('Impossible')
	else:
		(actions, leftTemp) = (deque(), deque())
		while (iDiff, jDiff) != (0, 0):
			if iDiff == 0:
				for i in range(0, abs(jDiff), 2):
					if jDiff > 0:
						actions.append('R')
					else:
						actions.append('L')
				break
			elif iDiff < 0:
				while iDiff != 0 and jDiff != 0:
					if jDiff < 0:
						(iDiff, jDiff) = (iDiff + 2, jDiff + 1)
						actions.append('UL')
					else:
						(iDiff, jDiff) = (iDiff + 2, jDiff - 1)
						actions.append('UR')
				if jDiff == 0:
					for i in range(0, abs(iDiff), 4):
						actions.appendleft('UL')
						actions.append('UR')
			else:
				surplus = abs(jDiff) - int(abs(iDiff) / 2)
				for i in range(0, max(surplus, 0), 2):
					if jDiff > 0:
						jDiff -= 2
						actions.append('R')
					else:
						jDiff += 2
						leftTemp.append('L')
				for i in range(abs(jDiff)):
					if jDiff < 0:
						leftTemp.appendleft('LL')
					else:
						actions.append('LR')
				iDiff -= 2 * abs(jDiff)
				for i in range(0, abs(iDiff), 4):
					actions.append('LR')
				for i in range(0, abs(iDiff), 4):
					actions.append('LL')
				break
		actions = actions + leftTemp
		print(len(actions))
		print(' '.join(actions))
	return
n = int(input().strip())
(i_start, j_start, i_end, j_end) = input().strip().split(' ')
(i_start, j_start, i_end, j_end) = [int(i_start), int(j_start), int(i_end), int(j_end)]
printShortestPath(n, i_start, j_start, i_end, j_end)


n = int(input())
(u, v, x, y) = list(map(int, input().split()))
level = [[-1 for i in range(n)] for j in range(n)]
parent = [['' for i in range(n)] for j in range(n)]
parent2 = [[-1 for i in range(n)] for j in range(n)]
frontier = [(u, v)]
level[u][v] = 0
while len(frontier) > 0:
	new_frontier = []
	for f in frontier:
		i = f[0]
		j = f[1]
		if i - 2 >= 0 and j - 1 >= 0 and (level[i - 2][j - 1] == -1):
			level[i - 2][j - 1] = level[i][j] + 1
			parent[i - 2][j - 1] = 'UL'
			parent2[i - 2][j - 1] = (i, j)
			new_frontier.append((i - 2, j - 1))
		if i - 2 >= 0 and j + 1 < n and (level[i - 2][j + 1] == -1):
			level[i - 2][j + 1] = level[i][j] + 1
			parent[i - 2][j + 1] = 'UR'
			new_frontier.append((i - 2, j + 1))
			parent2[i - 2][j + 1] = (i, j)
		if j + 2 < n and level[i][j + 2] == -1:
			level[i][j + 2] = level[i][j] + 1
			parent[i][j + 2] = 'R'
			new_frontier.append((i, j + 2))
			parent2[i][j + 2] = (i, j)
		if i + 2 < n and j + 1 < n and (level[i + 2][j + 1] == -1):
			level[i + 2][j + 1] = level[i][j] + 1
			parent[i + 2][j + 1] = 'LR'
			new_frontier.append((i + 2, j + 1))
			parent2[i + 2][j + 1] = (i, j)
		if i + 2 < n and j - 1 >= 0 and (level[i + 2][j - 1] == -1):
			level[i + 2][j - 1] = level[i][j] + 1
			parent[i + 2][j - 1] = 'LL'
			parent2[i + 2][j - 1] = (i, j)
			new_frontier.append((i + 2, j - 1))
		if j - 2 >= 0 and level[i][j - 2] == -1:
			level[i][j - 2] = level[i][j] + 1
			parent[i][j - 2] = 'L'
			parent2[i][j - 2] = (i, j)
			new_frontier.append((i, j - 2))
	frontier = new_frontier
if level[x][y] == -1:
	print('Impossible')
else:
	print(level[x][y])
	ans = []
	while not (x == u and y == v):
		ans.append(parent[x][y])
		(x, y) = parent2[x][y]
	ans.reverse()
	print(' '.join((x for x in ans)))


from collections import deque
moves = [('UL', -2, -1), ('UR', -2, 1), ('R', 0, 2), ('LR', 2, 1), ('LL', 2, -1), ('L', 0, -2)]
n = int(input())
(si, sj, ti, tj) = map(int, input().split())
unvisited = set()
for i in range(n):
	for j in range(n):
		unvisited.add((i, j))
q = deque()
q.append(((si, sj), -1, None))
unvisited.remove((si, sj))
i = 0
while unvisited and i < len(q):
	(node, parent, parentMove) = q[i]
	if node == (ti, tj):
		break
	for (move, di, dj) in moves:
		newNode = (node[0] + di, node[1] + dj)
		if newNode in unvisited:
			unvisited.remove(newNode)
			q.append((newNode, i, move))
	i += 1
if i >= len(q):
	print('Impossible')
else:
	result = []
	(node, parent, parentMove) = q[i]
	while parent >= 0:
		result.append(parentMove)
		(node, parent, parentMove) = q[parent]
	result.reverse()
	print(len(result))
	print(' '.join(result))


import sys

def printShortestPath(n, i_start, j_start, i_end, j_end):
	movs = []
	if (i_end - i_start) % 2 != 0:
		print('Impossible')
		return
	v_hops = abs(i_end - i_start) // 2
	if v_hops % 2 == 0 and (j_end - j_start) % 2 != 0:
		print('Impossible')
		return
	if v_hops % 2 != 0 and (j_end - j_start) % 2 == 0:
		print('Impossible')
		return
	for i in range(v_hops):
		v_dir = i_end > i_start and 'L' or 'U'
		if j_start > j_end or j_start == n - 1:
			movs.append(v_dir + 'L')
			j_start -= 1
		else:
			movs.append(v_dir + 'R')
			j_start += 1
	if j_start != j_end:
		h_dir = j_end > j_start and 'R' or 'L'
		for i in range(abs(j_end - j_start) // 2):
			movs.append(h_dir)
	return movs

def find_move(movs, m):
	try:
		return movs.index(m)
	except ValueError:
		return -1
n = int(input().strip())
(i_start, j_start, i_end, j_end) = input().strip().split(' ')
(i_start, j_start, i_end, j_end) = [int(i_start), int(j_start), int(i_end), int(j_end)]
movs = printShortestPath(n, i_start, j_start, i_end, j_end)
if movs:
	print(len(movs))
	ord_movs = []
	while movs:
		idx = False
		for m in ['UL', 'UR', 'R', 'LR', 'LL', 'L']:
			idx = find_move(movs, m)
			if idx >= 0:
				break
		ord_movs.append(movs[idx])
		movs.remove(movs[idx])
	print(' '.join(ord_movs))


import sys

def printShortestPath(n, i_start, j_start, i_end, j_end):
	diff_i = i_end - i_start
	diff_j = j_end - j_start
	i = i_start
	j = j_start
	if diff_i % 2 == 1:
		print('Impossible')
		return
	if diff_i % 4 == 0 and diff_j % 2 == 1:
		print('Impossible')
		return
	if diff_i % 4 == 2 and diff_j % 2 == 0:
		print('Impossible')
		return
	moves = []
	while diff_i < 0 and diff_i // -2 > diff_j:
		if j == 0:
			diff_i += 2
			diff_j -= 1
			i -= 2
			j += 1
			moves.append('UR')
			continue
		diff_i += 2
		diff_j += 1
		i -= 2
		j -= 1
		moves.append('UL')
	while diff_i < 0:
		diff_i += 2
		diff_j -= 1
		i -= 2
		j += 1
		moves.append('UR')
	while diff_j > 0 and diff_j > diff_i // 2:
		moves.append('R')
		j += 2
		diff_j -= 2
	while diff_i > 0 and diff_i // -2 < diff_j:
		if j == n - 1:
			diff_i -= 2
			diff_j += 1
			i += 2
			j -= 1
			moves.append('LL')
			continue
		moves.append('LR')
		diff_i -= 2
		diff_j -= 1
		i += 2
		j += 1
	while diff_i > 0:
		diff_i -= 2
		diff_j += 1
		i += 2
		j -= 1
		moves.append('LL')
	if diff_i == 0:
		if diff_j > 0:
			move = diff_j // 2
			moves += ['R'] * move
		else:
			move = -diff_j // 2
			moves += ['L'] * move
	print(len(moves))
	print(' '.join(moves))
n = int(input().strip())
(i_start, j_start, i_end, j_end) = input().strip().split(' ')
(i_start, j_start, i_end, j_end) = [int(i_start), int(j_start), int(i_end), int(j_end)]
printShortestPath(n, i_start, j_start, i_end, j_end)


import sys

def printShortestPath(n, i_start, j_start, i_end, j_end):
	moves = 0
	n_ul = 0
	n_ur = 0
	n_r = 0
	n_l = 0
	n_ll = 0
	n_lr = 0
	i_diff = i_start - i_end
	j_diff = j_start - j_end
	if abs(i_diff) % 2 != 0 or (abs(j_diff) - abs(i_diff / 2)) % 2 != 0:
		print('Impossible')
	else:
		while i_diff != 0:
			if i_diff > 0 and j_diff >= 0:
				n_ul += 1
				moves += 1
				i_diff -= 2
				j_diff -= 1
			elif i_diff > 0 and j_diff < 0:
				n_ur += 1
				moves += 1
				i_diff -= 2
				j_diff += 1
			elif i_diff < 0 and j_diff > 0:
				n_ll += 1
				moves += 1
				i_diff += 2
				j_diff -= 1
			elif i_diff < 0 and j_diff <= 0:
				n_lr += 1
				moves += 1
				i_diff += 2
				j_diff += 1
		while j_diff != 0:
			if j_diff > 0:
				n_l += 1
				moves += 1
				j_diff -= 2
			else:
				n_r += 1
				moves += 1
				j_diff += 2
		print(moves)
		for x in range(n_ul):
			print('UL', end=' ')
		for x in range(n_ur):
			print('UR', end=' ')
		for x in range(n_r):
			print('R', end=' ')
		for x in range(n_lr):
			print('LR', end=' ')
		for x in range(n_ll):
			print('LL', end=' ')
		for x in range(n_l):
			print('L', end=' ')
n = int(input().strip())
(i_start, j_start, i_end, j_end) = input().strip().split(' ')
(i_start, j_start, i_end, j_end) = [int(i_start), int(j_start), int(i_end), int(j_end)]
printShortestPath(n, i_start, j_start, i_end, j_end)


import sys

def printShortestPath(n, i_start, j_start, i_end, j_end):
	visited = [[False for i in range(n)] for j in range(n)]
	parent = [[0 for i in range(n)] for j in range(n)]
	Q = [[i_start, j_start, 0]]
	sol = False
	while len(Q) > 0:
		curr = Q.pop(0)
		if curr[0] == i_end and curr[1] == j_end:
			sol = True
			break
		if visited[curr[0]][curr[1]] != False:
			continue
		visited[curr[0]][curr[1]] = True
		if curr[0] - 2 >= 0:
			if curr[1] - 1 >= 0:
				if visited[curr[0] - 2][curr[1] - 1] == False:
					Q.append([curr[0] - 2, curr[1] - 1, curr[2] + 1])
					if parent[curr[0] - 2][curr[1] - 1] == 0:
						parent[curr[0] - 2][curr[1] - 1] = 'UL'
			if curr[1] + 1 < n:
				if visited[curr[0] - 2][curr[1] + 1] == False:
					Q.append([curr[0] - 2, curr[1] + 1, curr[2] + 1])
					if parent[curr[0] - 2][curr[1] + 1] == 0:
						parent[curr[0] - 2][curr[1] + 1] = 'UR'
		if curr[1] + 2 < n:
			if visited[curr[0]][curr[1] + 2] == False:
				Q.append([curr[0], curr[1] + 2, curr[2] + 1])
				if parent[curr[0]][curr[1] + 2] == 0:
					parent[curr[0]][curr[1] + 2] = 'R'
		if curr[0] + 2 < n:
			if curr[1] + 1 < n:
				if visited[curr[0] + 2][curr[1] + 1] == False:
					Q.append([curr[0] + 2, curr[1] + 1, curr[2] + 1])
					if parent[curr[0] + 2][curr[1] + 1] == 0:
						parent[curr[0] + 2][curr[1] + 1] = 'LR'
			if curr[1] - 1 >= 0:
				if visited[curr[0] + 2][curr[1] - 1] == False:
					Q.append([curr[0] + 2, curr[1] - 1, curr[2] + 1])
					if parent[curr[0] + 2][curr[1] - 1] == 0:
						parent[curr[0] + 2][curr[1] - 1] = 'LL'
		if curr[1] - 2 >= 0:
			if visited[curr[0]][curr[1] - 2] == False:
				Q.append([curr[0], curr[1] - 2, curr[2] + 1])
				if parent[curr[0]][curr[1] - 2] == 0:
					parent[curr[0]][curr[1] - 2] = 'L'
	if sol:
		print(curr[2])
		path = []
		while i_end != i_start or j_end != j_start:
			parentletter = parent[i_end][j_end]
			path.append(parentletter)
			if parentletter == 'UR':
				i_end = i_end + 2
				j_end = j_end - 1
			if parentletter == 'R':
				i_end = i_end
				j_end = j_end - 2
			if parentletter == 'LR':
				i_end = i_end - 2
				j_end = j_end - 1
			if parentletter == 'LL':
				i_end = i_end - 2
				j_end = j_end + 1
			if parentletter == 'L':
				i_end = i_end
				j_end = j_end + 2
			if parentletter == 'UL':
				i_end = i_end + 2
				j_end = j_end + 1
		for qw in range(len(path)):
			print(path[-1 - qw], end=' ')
	else:
		print('Impossible')
n = int(input().strip())
(i_start, j_start, i_end, j_end) = input().strip().split(' ')
(i_start, j_start, i_end, j_end) = [int(i_start), int(j_start), int(i_end), int(j_end)]
printShortestPath(n, i_start, j_start, i_end, j_end)


import sys
moves = ['UL', 'UR', 'R', 'LR', 'LL', 'L']

def step(n, i_start, j_start, move, history):
	if move == 'UL' and i_start > 0 and (j_start > 1):
		return (i_start - 1, j_start - 2, move, history)
	if move == 'UR' and i_start < n - 1 and (j_start > 1):
		return (i_start + 1, j_start - 2, move, history)
	if move == 'R' and j_start < n - 2:
		return (i_start + 2, j_start, move, history)
	if move == 'LL' and i_start > 0 and (j_start < n - 2):
		return (i_start - 1, j_start + 2, move, history)
	if move == 'LR' and i_start < n - 1 and (j_start < n - 2):
		return (i_start + 1, j_start + 2, move, history)
	if move == 'L' and i_start > 1:
		return (i_start - 2, j_start, move, history)
	return None

def distance(i_start, j_start, i_end, j_end):
	return abs(i_end - i_start) + abs(j_end - j_start)

def printShortestPath(n, j_start, i_start, j_end, i_end):
	visited = [(i_start, j_start)]
	candidates = [(i_start, j_start, None, None)]
	dist = 9999
	found = False
	while not found:
		new_candidates = []
		for candidate in candidates:
			cur_dist = distance(candidate[0], candidate[1], i_end, j_end)
			if cur_dist == 0:
				found = True
				new_candidates.append(candidate)
				break
			for move in moves:
				next = step(n, candidate[0], candidate[1], move, candidate)
				if next != None:
					new_dist = distance(next[0], next[1], i_end, j_end)
					if new_dist < cur_dist and (next[0], next[1]) not in visited:
						new_candidates.append(next)
						visited.append((next[0], next[1]))
		if len(new_candidates) == 0:
			break
		candidates = new_candidates
	found = False
	for c in candidates:
		if c[0] == i_end and c[1] == j_end:
			found = True
			l = 0
			path = ''
			x = c
			while x[2] is not None:
				path = x[2] + ' ' + path
				x = x[3]
				l += 1
			print(l)
			print(path)
			break
	if not found:
		print('Impossible')
n = int(input().strip())
(i_start, j_start, i_end, j_end) = input().strip().split(' ')
(i_start, j_start, i_end, j_end) = [int(i_start), int(j_start), int(i_end), int(j_end)]
printShortestPath(n, i_start, j_start, i_end, j_end)


import sys

def printShortestPath(n, i_start, j_start, i_end, j_end):
	if 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):
		print('Impossible')
	else:
		moves = 0
		smoves = ''
		while i_start != i_end or j_start != j_end:
			moves += 1
			if i_start > i_end and j_start > j_end - (i_start - i_end) // 2 and (j_start > 0):
				smoves += 'UL '
				i_start -= 2
				j_start -= 1
			elif i_start > i_end:
				smoves += 'UR '
				i_start -= 2
				j_start += 1
			elif i_start <= i_end and j_start < j_end - (i_end - i_start) // 2:
				smoves += 'R '
				j_start += 2
			elif i_start < i_end and j_start < j_end + (i_end - i_start) // 2:
				smoves += 'LR '
				i_start += 2
				j_start += 1
			elif i_start < i_end and j_start >= j_end + (i_end - i_start) // 2:
				smoves += 'LL '
				i_start += 2
				j_start -= 1
			else:
				smoves += 'L '
				j_start -= 2
		print(moves)
		print(smoves[:len(smoves) - 1])
n = int(input().strip())
(i_start, j_start, i_end, j_end) = input().strip().split(' ')
(i_start, j_start, i_end, j_end) = [int(i_start), int(j_start), int(i_end), int(j_end)]
printShortestPath(n, i_start, j_start, i_end, j_end)


import sys

def printShortestPath(n, ist, jst, ien, jen):
	s = []
	i = 1
	count = 0
	flag = False
	d = abs(ist - ien) + abs(jst - jen)
	while d != 0 and i < 100000:
		k = [100000] * 6
		d1 = d
		if jst - 1 >= 0 and ist - 2 >= 0:
			k[0] = abs(jst - 1 - jen) + abs(ist - 2 - ien)
		if jst + 1 < n and ist - 2 >= 0:
			k[1] = abs(jst + 1 - jen) + abs(ist - 2 - ien)
		if jst + 2 < n:
			k[2] = abs(jst + 2 - jen) + abs(ist - ien)
		if jst + 1 < n and ist + 2 < n:
			k[3] = abs(jst + 1 - jen) + abs(ist + 2 - ien)
		if jst - 1 >= 0 and ist + 2 < n:
			k[4] = abs(jst - 1 - jen) + abs(ist + 2 - ien)
		if jst - 2 >= 0:
			k[5] = abs(jst - 2 - jen) + abs(ist - ien)
		l = min(k)
		if l == k[0]:
			count += 1
			jst = jst - 1
			ist = ist - 2
			s.append(0)
		elif l == k[1]:
			count += 1
			jst = jst + 1
			ist = ist - 2
			s.append(1)
		elif l == k[2]:
			count += 1
			jst = jst + 2
			s.append(2)
		elif l == k[3]:
			count += 1
			jst = jst + 1
			ist = ist + 2
			s.append(3)
		elif l == k[4]:
			count += 1
			jst = jst - 1
			ist = ist + 2
			s.append(4)
		elif l == k[5]:
			count += 1
			jst = jst - 2
			s.append(5)
		d = abs(ist - ien) + abs(jst - jen)
		i += 1
		if d1 < d:
			flag = True
			break
	s.sort()
	for i in range(len(s)):
		if s[i] == 0:
			s[i] = 'UL'
		elif s[i] == 1:
			s[i] = 'UR'
		elif s[i] == 2:
			s[i] = 'R'
		elif s[i] == 3:
			s[i] = 'LR'
		elif s[i] == 4:
			s[i] = 'LL'
		else:
			s[i] = 'L'
	if flag == True or d != 0:
		print('Impossible')
	elif d == 0:
		print(count)
		print(*s)
n = int(input().strip())
(i_start, j_start, i_end, j_end) = input().strip().split(' ')
(i_start, j_start, i_end, j_end) = [int(i_start), int(j_start), int(i_end), int(j_end)]
printShortestPath(n, i_start, j_start, i_end, j_end)


import sys
from collections import namedtuple
Cell = namedtuple('Cell', ['x', 'y'])
PRIORITY = ['UL', 'UR', 'R', 'LR', 'LL', 'L']

def convert_to_intlist(line):
	return [int(item) for item in line.split()]

def is_valid(point, gridsize):
	return 0 <= point.x < gridsize and 0 <= point.y < gridsize

def valid_neighbours_in_order(cell, gridsize):
	(x, y) = cell
	neighbours = [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)]
	return [point if is_valid(point, gridsize) else None for point in neighbours]

def neighbours_of_cells(cells, distances, next_level, backtrack, gridsize):
	unvisited_neighbours = []
	for cell in cells:
		neighbours = valid_neighbours_in_order(cell, gridsize)
		for (neighbour, direction) in zip(neighbours, PRIORITY):
			if neighbour is not None and neighbour not in distances:
				distances[neighbour] = next_level
				backtrack[neighbour] = (cell, direction)
				unvisited_neighbours.append(neighbour)
	return unvisited_neighbours

def get_complete_path(start, end, backtrack):
	path = []
	point = end
	while point != start:
		(point, direction) = backtrack[point]
		path.append(direction)
	return ' '.join(path[::-1])

def find_shortest_path(start, end, gridsize):
	distances = {start: 0}
	backtrack = {}
	next_level = 1
	neighbours = neighbours_of_cells([start], distances, next_level, backtrack, gridsize)
	while neighbours and end not in neighbours:
		next_level += 1
		neighbours = neighbours_of_cells(neighbours, distances, next_level, backtrack, gridsize)
	if end not in distances:
		return None
	return (distances[end], get_complete_path(start, end, backtrack))
data = sys.stdin.read().splitlines()
gridsize = int(data[0])
(start_y, start_x, end_y, end_x) = convert_to_intlist(data[1])
start = Cell(start_x, start_y)
end = Cell(end_x, end_y)
path = find_shortest_path(start, end, gridsize)
if path is None:
	print('Impossible')
else:
	print(path[0])
	print(path[1])