Nash designed an interesting yet simple board game where a player is simply required to follow instructions written on the cell where the player currently stands. 

This board game is played on the n× n board. Rows and columns of this board are numbered from 1 to n. The cell on the intersection of the r-th row and c-th column is denoted by (r, c).

Some cells on the board are called blocked zones. On each cell of the board, there is written one of the following 5 characters — U, D, L, R or X — instructions for the player. Suppose that the current cell is (r, c). If the character is R, the player should move to the right cell (r, c+1), for L the player should move to the left cell (r, c-1), for U the player should move to the top cell (r-1, c), for D the player should move to the bottom cell (r+1, c). Finally, if the character in the cell is X, then this cell is the blocked zone. The player should remain in this cell (the game for him isn't very interesting from now on).

It is guaranteed that the characters are written in a way that the player will never have to step outside of the board, no matter at which cell he starts.

As a player starts from a cell, he moves according to the character in the current cell. The player keeps moving until he lands in a blocked zone. It is also possible that the player will keep moving infinitely long.

For every of the n^2 cells of the board Alice, your friend, wants to know, how will the game go, if the player starts in this cell. For each starting cell of the board, she writes down the cell that the player stops at, or that the player never stops at all. She gives you the information she has written: for each cell (r, c) she wrote: 

  * a pair (x,y), meaning if a player had started at (r, c), he would end up at cell (x,y). 
  * or a pair (-1,-1), meaning if a player had started at (r, c), he would keep moving infinitely long and would never enter the blocked zone. 



It might be possible that Alice is trying to fool you and there's no possible grid that satisfies all the constraints Alice gave you. For the given information Alice provided you, you are required to decipher a possible board, or to determine that such a board doesn't exist. If there exist several different boards that satisfy the provided information, you can find any of them.

Input

The first line of the input contains a single integer n (1 ≤ n ≤ 10^{3}) — the side of the board.

The i-th of the next n lines of the input contains 2n integers x_1, y_1, x_2, y_2, ..., x_n, y_n, where (x_j, y_j) (1 ≤ x_j ≤ n, 1 ≤ y_j ≤ n, or (x_j,y_j)=(-1,-1)) is the pair written by Alice for the cell (i, j). 

Output

If there doesn't exist a board satisfying the information that Alice gave you, print a single line containing INVALID. 

Otherwise, in the first line print VALID. In the i-th of the next n lines, print the string of n characters, corresponding to the characters in the i-th row of the suitable board you found. Each character of a string can either be U, D, L, R or X. If there exist several different boards that satisfy the provided information, you can find any of them.

Examples

Input


2
1 1 1 1
2 2 2 2


Output


VALID
XL
RX


Input


3
-1 -1 -1 -1 -1 -1
-1 -1 2 2 -1 -1
-1 -1 -1 -1 -1 -1


Output


VALID
RRD
UXD
ULL

Note

For the sample test 1 :

The given grid in output is a valid one. 

  * If the player starts at (1,1), he doesn't move any further following X and stops there. 
  * If the player starts at (1,2), he moves to left following L and stops at (1,1). 
  * If the player starts at (2,1), he moves to right following R and stops at (2,2). 
  * If the player starts at (2,2), he doesn't move any further following X and stops there. 



The simulation can be seen below : 

<image>

For the sample test 2 : 

The given grid in output is a valid one, as a player starting at any cell other than the one at center (2,2), keeps moving in an infinitely long cycle and never stops. Had he started at (2,2), he wouldn't have moved further following instruction X .

The simulation can be seen below : 

<image>

Difficulty: HARD
Tags: Graph algorithms

Graph traversal

Implementation

Constructive algorithms

Starter code:

Solutions:
from collections import deque
import sys

def input():
	return sys.stdin.buffer.readline()[:-1]

def main():
	n = int(input())
	res = [[''] * n for _ in range(n)]
	data = [[None] * n for _ in range(n)]
	q = deque()
	for i in range(n):
		row = [int(x) - 1 for x in input().split()]
		for j in range(n):
			data[i][j] = (row[j * 2], row[j * 2 + 1])
			if (i, j) == data[i][j]:
				q.append((i, j))
				res[i][j] = 'X'
	while q:
		(i, j) = q.popleft()
		if 0 <= i + 1 < n and 0 <= j < n and (data[i + 1][j] == data[i][j]) and (not res[i + 1][j]):
			res[i + 1][j] = 'U'
			q.append((i + 1, j))
		if 0 <= i - 1 < n and 0 <= j < n and (data[i - 1][j] == data[i][j]) and (not res[i - 1][j]):
			res[i - 1][j] = 'D'
			q.append((i - 1, j))
		if 0 <= i < n and 0 <= j + 1 < n and (data[i][j + 1] == data[i][j]) and (not res[i][j + 1]):
			res[i][j + 1] = 'L'
			q.append((i, j + 1))
		if 0 <= i < n and 0 <= j - 1 < n and (data[i][j - 1] == data[i][j]) and (not res[i][j - 1]):
			res[i][j - 1] = 'R'
			q.append((i, j - 1))
	for i in range(n):
		for j in range(n):
			if data[i][j] == (-2, -2):
				if 0 <= i + 1 < n and 0 <= j < n and (data[i + 1][j] == (-2, -2)):
					res[i][j] = 'D'
				elif 0 <= i - 1 < n and 0 <= j < n and (data[i - 1][j] == (-2, -2)):
					res[i][j] = 'U'
				elif 0 <= i < n and 0 <= j + 1 < n and (data[i][j + 1] == (-2, -2)):
					res[i][j] = 'R'
				elif 0 <= i < n and 0 <= j - 1 < n and (data[i][j - 1] == (-2, -2)):
					res[i][j] = 'L'
				else:
					print('INVALID')
					exit()
	total = []
	for e in res:
		if '' in e:
			print('INVALID')
			exit()
		total.append(''.join(e))
	print('VALID')
	print('\n'.join(total), flush=True)
main()


import sys
from collections import Counter

def input():
	return sys.stdin.readline().strip()

def list2d(a, b, c):
	return [[c] * b for i in range(a)]

def list3d(a, b, c, d):
	return [[[d] * c for j in range(b)] for i in range(a)]

def list4d(a, b, c, d, e):
	return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]

def ceil(x, y=1):
	return int(-(-x // y))

def INT():
	return int(input())

def MAP():
	return map(int, input().split())

def LIST(N=None):
	return list(MAP()) if N is None else [INT() for i in range(N)]

def Yes():
	print('Yes')

def No():
	print('No')

def YES():
	print('YES')

def NO():
	print('NO')
INF = 10 ** 18
MOD = 10 ** 9 + 7

def bfs(grid, grid2):
	from collections import deque
	que = deque()
	for i in range(1, N + 1):
		for j in range(1, N + 1):
			if grid2[i][j] == '':
				if grid[i][j] == (i, j):
					que.append(((i, j), (i, j)))
					grid2[i][j] = 'X'
	directions = ((1, 0), (-1, 0), (0, 1), (0, -1))
	chara = ('U', 'D', 'L', 'R')
	while que:
		(hw, tgt) = que.popleft()
		(h, w) = hw
		for (i, (dh, dw)) in enumerate(directions):
			h2 = h + dh
			w2 = w + dw
			if grid[h2][w2] == tgt and grid2[h2][w2] == '':
				grid2[h2][w2] = chara[i]
				que.append(((h2, w2), tgt))
N = INT()
grid = list2d(N + 2, N + 2, ())
for i in range(N):
	row = LIST()
	for j in range(N):
		grid[i + 1][j + 1] = (row[j * 2], row[j * 2 + 1])
grid2 = list2d(N + 2, N + 2, '')
bfs(grid, grid2)
directions = ((1, 0), (-1, 0), (0, 1), (0, -1))
chara = ('D', 'U', 'R', 'L')
for h in range(1, N + 1):
	for w in range(1, N + 1):
		if grid2[h][w] == '' and grid[h][w] == (-1, -1):
			for (i, (dh, dw)) in enumerate(directions):
				h2 = h + dh
				w2 = w + dw
				if grid[h2][w2] == (-1, -1):
					grid2[h][w] = chara[i]
					break
			else:
				print('INVALID')
				exit()
for i in range(1, N + 1):
	if grid2[i][1:-1].count(''):
		print('INVALID')
		exit()
print('VALID')
for i in range(1, N + 1):
	print(''.join(grid2[i][1:-1]))


n = int(input())
d = [[0] * n for _ in range(n)]
for r in range(n):
	nums = list(map(int, input().split()))
	i = 0
	while i + 1 < 2 * n:
		d[r][i // 2] = (nums[i], nums[i + 1])
		i += 2
result = [[None] * n for _ in range(n)]
moves = [(0, 1, 'L', 'R'), (0, -1, 'R', 'L'), (1, 0, 'U', 'D'), (-1, 0, 'D', 'U')]

def consider(r, c, v):
	if not 0 <= r < n or not 0 <= c < n:
		return False
	if result[r][c] is not None:
		return False
	if d[r][c] != v:
		return False
	return True

def bfs(rs, cs, val):
	q = [(rs, cs)]
	while q:
		(r, c) = q.pop()
		for (dr, dc, dir, _) in moves:
			(r2, c2) = (r + dr, c + dc)
			if not consider(r2, c2, val):
				continue
			result[r2][c2] = dir
			q.append((r2, c2))
for r in range(n):
	for c in range(n):
		if result[r][c] is not None:
			continue
		if d[r][c] == (r + 1, c + 1):
			result[r][c] = 'X'
			bfs(r, c, d[r][c])
		elif d[r][c] == (-1, -1):
			for (dr, dc, dir, opp) in moves:
				(r2, c2) = (r + dr, c + dc)
				if not consider(r2, c2, d[r][c]):
					continue
				result[r2][c2] = dir
				result[r][c] = opp
				bfs(r2, c2, (-1, -1))
				bfs(r, c, (-1, -1))
				break
			else:
				print('INVALID')
				exit(0)
for r in range(n):
	for c in range(n):
		if result[r][c] is None:
			print('INVALID')
			exit(0)
print('VALID')
for r in result:
	print(''.join(r))


def main():
	n = int(input())
	board = []
	told = []
	blocked = []
	for r in range(1, n + 1):
		endings = list(map(int, input().split()))
		board.append([])
		told.append([])
		for i in range(0, 2 * n, 2):
			(x, y) = endings[i:i + 2]
			told[-1].append((x, y))
			if x == r and y == i // 2 + 1:
				board[-1].append('X')
				blocked.append((x - 1, y - 1))
			else:
				board[-1].append('')
	unvisited = []
	for (bx, by) in blocked:
		one_idx = (bx + 1, by + 1)
		if bx and told[bx - 1][by] == one_idx:
			board[bx - 1][by] = 'D'
			unvisited.append((bx - 1, by))
		if bx < n - 1 and told[bx + 1][by] == one_idx:
			board[bx + 1][by] = 'U'
			unvisited.append((bx + 1, by))
		if by and told[bx][by - 1] == one_idx:
			board[bx][by - 1] = 'R'
			unvisited.append((bx, by - 1))
		if by < n - 1 and told[bx][by + 1] == one_idx:
			board[bx][by + 1] = 'L'
			unvisited.append((bx, by + 1))
	z = 0
	while z < len(unvisited):
		(x, y) = unvisited[z]
		if x and board[x - 1][y] == '' and (told[x - 1][y] == told[x][y]):
			unvisited.append((x - 1, y))
			board[x - 1][y] = 'D'
		if x < n - 1 and board[x + 1][y] == '' and (told[x + 1][y] == told[x][y]):
			unvisited.append((x + 1, y))
			board[x + 1][y] = 'U'
		if y and board[x][y - 1] == '' and (told[x][y - 1] == told[x][y]):
			unvisited.append((x, y - 1))
			board[x][y - 1] = 'R'
		if y < n - 1 and board[x][y + 1] == '' and (told[x][y + 1] == told[x][y]):
			unvisited.append((x, y + 1))
			board[x][y + 1] = 'L'
		z += 1
	for i in range(n):
		for j in range(n):
			if board[i][j] == '':
				if told[i][j] != (-1, -1):
					print('INVALID')
					return
				if i and told[i - 1][j] == (-1, -1):
					board[i][j] = 'U'
					continue
				if i < n - 1 and told[i + 1][j] == (-1, -1):
					board[i][j] = 'D'
					continue
				if j and told[i][j - 1] == (-1, -1):
					board[i][j] = 'L'
					continue
				if j < n - 1 and told[i][j + 1] == (-1, -1):
					board[i][j] = 'R'
					continue
				print('INVALID')
				return
	print('VALID')
	for k in range(n):
		print(''.join(board[k]))
main()


from collections import deque
n = int(input())
b = [None] * (n * n)
m = [None] * (n * n)
x = 0
for r in range(n):
	pq = list(map(int, input().split()))
	for c in range(n):
		rr = pq[2 * c] - 1
		rc = pq[2 * c + 1] - 1
		if rr != -2:
			x += 1
			b[r * n + c] = (rr, rc)

def bfs(sr, sc):
	global x
	m[sr * n + sc] = 'X'
	x -= 1
	q = deque()
	q.append((sr, sc))
	while len(q) != 0 and x != 0:
		(r, c) = q.popleft()
		ne = [((r - 1, c), 'D'), ((r + 1, c), 'U'), ((r, c - 1), 'R'), ((r, c + 1), 'L')]
		for (el, co) in ne:
			(r, c) = el
			if r not in {-1, n} and c not in {-1, n} and (b[r * n + c] == (sr, sc)) and (m[r * n + c] is None):
				m[r * n + c] = co
				x -= 1
				q.append(el)
for r in range(n):
	for c in range(n):
		be = b[r * n + c]
		if be == (r, c):
			bfs(r, c)
			continue
		if be is not None:
			continue
		if r > 0 and b[(r - 1) * n + c] is None:
			m[r * n + c] = 'U'
		elif r < n - 1 and b[(r + 1) * n + c] is None:
			m[r * n + c] = 'D'
		elif c > 0 and b[r * n + c - 1] is None:
			m[r * n + c] = 'L'
		elif c < n - 1 and b[r * n + c + 1] is None:
			m[r * n + c] = 'R'
		else:
			print('INVALID')
			exit()
if x != 0:
	print('INVALID')
	exit()
print('VALID')
for r in range(n):
	print(''.join(m[r * n:r * n + n]))


from sys import stdin, gettrace
from collections import deque

def input():
	return stdin.buffer.readline()

def main():
	n = int(input())
	grid = [[None] * (n + 2) for _ in range(n + 2)]
	res = [[''] * (n + 2) for _ in range(n + 2)]
	for i in range(1, n + 1):
		line = (int(a) for a in input().split())
		for j in range(1, n + 1):
			x = next(line)
			y = next(line)
			if i == x and j == y:
				res[i][j] = 'X'
				grid[i][j] = (-2, -2)
			else:
				grid[i][j] = (x, y)
	filled = 0
	for i in range(1, n + 1):
		for j in range(1, n + 1):
			if res[i][j] == 'X':
				filled += 1
				q = deque()
				q.append((i, j))
				while q:
					(x, y) = q.pop()
					if grid[x - 1][y] == (i, j):
						res[x - 1][y] = 'D'
						q.append((x - 1, y))
						grid[x - 1][y] = (-2, -2)
						filled += 1
					if grid[x + 1][y] == (i, j):
						res[x + 1][y] = 'U'
						q.append((x + 1, y))
						grid[x + 1][y] = (-2, -2)
						filled += 1
					if grid[x][y - 1] == (i, j):
						res[x][y - 1] = 'R'
						q.append((x, y - 1))
						grid[x][y - 1] = (-2, -2)
						filled += 1
					if grid[x][y + 1] == (i, j):
						res[x][y + 1] = 'L'
						q.append((x, y + 1))
						grid[x][y + 1] = (-2, -2)
						filled += 1
			if grid[i][j] == (-1, -1):
				filled += 1
				if grid[i - 1][j] == (-1, -1):
					res[i][j] = 'U'
				elif grid[i + 1][j] == (-1, -1):
					res[i][j] = 'D'
				elif grid[i][j - 1] == (-1, -1):
					res[i][j] = 'L'
				elif grid[i][j + 1] == (-1, -1):
					res[i][j] = 'R'
				else:
					print('INVALID')
					return
	if filled != n * n:
		print('INVALID')
		return
	print('VALID')
	for i in range(1, n + 1):
		print(''.join(res[i][1:n + 1]))
main()


import math
import collections
import bisect
import heapq
import time
import random
import itertools
import sys
from typing import List

def check(x, y, N):
	return 1 <= x <= N and 1 <= y <= N

def dfs(x, y, d, marks, X, Y, N):
	if not check(x, y, N) or marks[x][y] != '':
		return
	marks[x][y] = d
	if x + 1 <= N and X[x][y] == X[x + 1][y] and (Y[x][y] == Y[x + 1][y]):
		dfs(x + 1, y, 'U', marks, X, Y, N)
	if x - 1 > 0 and X[x][y] == X[x - 1][y] and (Y[x][y] == Y[x - 1][y]):
		dfs(x - 1, y, 'D', marks, X, Y, N)
	if y + 1 <= N and X[x][y] == X[x][y + 1] and (Y[x][y] == Y[x][y + 1]):
		dfs(x, y + 1, 'L', marks, X, Y, N)
	if y - 1 > 0 and X[x][y] == X[x][y - 1] and (Y[x][y] == Y[x][y - 1]):
		dfs(x, y - 1, 'R', marks, X, Y, N)

def dfs2(x, y, d, marks, X, Y, N):
	marks[x][y] = d
	q = [(x, y)]
	(vx, vy) = (X[x][y], Y[x][y])
	while q:
		(x, y) = q.pop()
		for (nx, ny, nd) in [(x + 1, y, 'U'), (x - 1, y, 'D'), (x, y + 1, 'L'), (x, y - 1, 'R')]:
			if check(nx, ny, N) and X[nx][ny] == vx and (Y[nx][ny] == vy) and (marks[nx][ny] == ''):
				marks[nx][ny] = nd
				q.append((nx, ny))

def connect(x1, y1, x2, y2, d1, d2, marks, X, Y, N):
	if not check(x1, y1, N) or not check(x2, y2, N):
		return False
	if X[x2][y2] == -1:
		marks[x1][y1] = d1
		if marks[x2][y2] == '':
			marks[x2][y2] = d2
		return True
	return False

def solve(N, X, Y):
	marks = [['' for _ in range(N + 2)] for _ in range(N + 2)]
	for r in range(N + 2):
		marks[r][0] = '#'
		marks[r][N + 1] = '#'
		marks[0][r] = '#'
		marks[N + 1][r] = '#'
	for r in range(1, N + 1):
		for c in range(1, N + 1):
			if X[r][c] == -1:
				res = marks[r][c] != ''
				if not res:
					res = connect(r, c, r + 1, c, 'D', 'U', marks, X, Y, N)
				if not res:
					res = connect(r, c, r, c + 1, 'R', 'L', marks, X, Y, N)
				if not res:
					res = connect(r, c, r - 1, c, 'U', 'D', marks, X, Y, N)
				if not res:
					res = connect(r, c, r, c - 1, 'L', 'R', marks, X, Y, N)
				if not res:
					return 'INVALID'
			elif X[r][c] == r and Y[r][c] == c:
				dfs2(r, c, 'X', marks, X, Y, N)
	for r in range(1, N + 1):
		for c in range(1, N + 1):
			if marks[r][c] == '':
				return 'INVALID'
	ans = ['VALID']
	for r in range(1, N + 1):
		row = ''.join([marks[r][c] for c in range(1, N + 1)])
		ans.append(row)
	return '\n'.join(ans)

def test():
	N = 1000
	X = [[1000 for _ in range(N + 2)] for _ in range(N + 2)]
	Y = [[1000 for _ in range(N + 2)] for _ in range(N + 2)]
	solve(N, X, Y)
N = int(input())
X = [[0 for _ in range(N + 2)] for _ in range(N + 2)]
Y = [[0 for _ in range(N + 2)] for _ in range(N + 2)]
for r in range(1, N + 1):
	cs = [int(x) for x in input().split()]
	for c in range(1, N + 1):
		X[r][c] = cs[(c - 1) * 2]
		Y[r][c] = cs[(c - 1) * 2 + 1]
print(solve(N, X, Y))


import io
import os
from collections import deque
drdc = [(-1, 0), (0, -1), (0, 1), (1, 0)]
drdcToChar = dict(zip(drdc, 'ULRD'))
DEBUG = False

def neighbor4(R, C):

	def getNbr(node):
		(r, c) = node
		for (dr, dc) in drdc:
			(nr, nc) = (r + dr, c + dc)
			if 0 <= nr < R and 0 <= nc < C:
				yield (nr, nc)
	return getNbr

def gridToString(grid):
	return '\n'.join((''.join(row) for row in grid))

def solve(N, board):
	CYCLE_CELL = (-2, -2)
	R = N
	C = N
	sol = [['?' for c in range(C)] for r in range(R)]
	getNbr = neighbor4(R, C)

	def flood(initNodes, val):
		if DEBUG:
			print('flooding', initNodes)
		q = deque(initNodes)
		while q:
			if DEBUG:
				print(gridToString(sol) + '\n')
			(r, c) = q.popleft()
			for (nr, nc) in getNbr((r, c)):
				if sol[nr][nc] == '?' and board[nr][nc] == val:
					sol[nr][nc] = drdcToChar[r - nr, c - nc]
					q.append((nr, nc))
	for r in range(R):
		for c in range(C):
			if sol[r][c] == '?' and board[r][c] == (r, c):
				sink = [(r, c)]
				sol[r][c] = 'X'
				flood(sink, (r, c))
	for r in range(R):
		for c in range(C):
			if sol[r][c] == '?':
				if DEBUG:
					print(gridToString(sol) + '\n')
				if board[r][c] != CYCLE_CELL:
					return 'INVALID'
				cycle = [(r, c)]
				for (nr, nc) in getNbr((r, c)):
					if sol[nr][nc] == '?' and board[nr][nc] == CYCLE_CELL:
						cycle.append((nr, nc))
						break
				if len(cycle) != 2:
					return 'INVALID'
				if DEBUG:
					for (rr, cc) in cycle:
						sol[rr][cc] = 'C'
					print(gridToString(sol) + '\n')
				for (i, (rr, cc)) in enumerate(cycle):
					(rrr, ccc) = cycle[(i - 1) % len(cycle)]
					sol[rr][cc] = drdcToChar[rrr - rr, ccc - cc]
				flood(cycle, CYCLE_CELL)
	return 'VALID\n' + gridToString(sol)
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
(N,) = list(map(int, input().split()))
board = []
for i in range(N):
	line = [int(x) - 1 for x in input().split()]
	board.append(list(zip(line[::2], line[1::2])))
assert len(board) == len(board[0]) == N
ans = solve(N, board)
print(ans)


import sys

def input():
	return sys.stdin.buffer.readline()[:-1]

def print(*values, end='\n'):
	sys.stdout.write(' '.join([str(x) for x in values]) + end)
from collections import deque

def main():
	n = int(input())
	res = [[''] * n for _ in range(n)]
	data = [[None] * n for _ in range(n)]
	q = deque()
	cnt = 0
	for i in range(n):
		row = [int(x) - 1 for x in input().split()]
		for j in range(n):
			data[i][j] = (row[j * 2], row[j * 2 + 1])
			if (i, j) == data[i][j]:
				q.append((i, j))
				res[i][j] = 'X'
	while q:
		cnt += 1
		(i, j) = q.popleft()
		if 0 <= i + 1 < n and 0 <= j < n and (data[i + 1][j] == data[i][j]) and (not res[i + 1][j]):
			res[i + 1][j] = 'U'
			q.append((i + 1, j))
		if 0 <= i - 1 < n and 0 <= j < n and (data[i - 1][j] == data[i][j]) and (not res[i - 1][j]):
			res[i - 1][j] = 'D'
			q.append((i - 1, j))
		if 0 <= i < n and 0 <= j + 1 < n and (data[i][j + 1] == data[i][j]) and (not res[i][j + 1]):
			res[i][j + 1] = 'L'
			q.append((i, j + 1))
		if 0 <= i < n and 0 <= j - 1 < n and (data[i][j - 1] == data[i][j]) and (not res[i][j - 1]):
			res[i][j - 1] = 'R'
			q.append((i, j - 1))
	for i in range(n):
		for j in range(n):
			if data[i][j] == (-2, -2):
				cnt += 1
				if 0 <= i + 1 < n and 0 <= j < n and (data[i + 1][j] == (-2, -2)):
					res[i][j] = 'D'
				elif 0 <= i - 1 < n and 0 <= j < n and (data[i - 1][j] == (-2, -2)):
					res[i][j] = 'U'
				elif 0 <= i < n and 0 <= j + 1 < n and (data[i][j + 1] == (-2, -2)):
					res[i][j] = 'R'
				elif 0 <= i < n and 0 <= j - 1 < n and (data[i][j - 1] == (-2, -2)):
					res[i][j] = 'L'
				else:
					print('INVALID')
					exit()
	if cnt != n * n:
		print('INVALID')
		exit()
	print('VALID')
	for e in res:
		print(''.join(e))
main()


INF = 10 ** 10

def main():
	print = out.append
	n = get_int()
	mat = [[] for _ in range(n)]
	res = [['A' for _ in range(n)] for _ in range(n)]
	for j in range(n):
		li = get_list()
		for i in range(0, 2 * n, 2):
			(x, y) = (li[i] - 1, li[i + 1] - 1)
			mat[j].append([x, y])

	def nbrs(i, j):
		res = []
		if i > 0:
			res.append([i - 1, j, 'U', 'D'])
		if i < n - 1:
			res.append([i + 1, j, 'D', 'U'])
		if j > 0:
			res.append([i, j - 1, 'L', 'R'])
		if j < n - 1:
			res.append([i, j + 1, 'R', 'L'])
		return res
	for i in range(n):
		for j in range(n):
			(x, y) = mat[i][j]
			if x < 0:
				for (x1, y1, loc, _) in nbrs(i, j):
					if mat[x1][y1][0] < 0:
						res[i][j] = loc
						break
			elif x == i and y == j:
				queue = [[x, y]]
				res[x][y] = 'X'
				while len(queue) > 0:
					new_q = []
					for (qx1, qx2) in queue:
						for (nx1, nx2, _, loc) in nbrs(qx1, qx2):
							if res[nx1][nx2] == 'A' and mat[qx1][qx2] == mat[nx1][nx2]:
								res[nx1][nx2] = loc
								new_q.append([nx1, nx2])
					queue = new_q
	for i in range(n):
		for j in range(n):
			if res[i][j] == 'A':
				print('INVALID')
				return
	print('VALID')
	for li in res:
		print(''.join(li))
import sys
from collections import defaultdict, Counter, deque
input = iter(sys.stdin.buffer.read().decode().splitlines()).__next__
out = []
get_int = lambda : int(input())
get_list = lambda : list(map(int, input().split()))
main()
print(*out, sep='\n')


from sys import stdin

def input():
	return stdin.buffer.readline()
n = int(input())
a = []
b = []
for _ in range(n):
	s = map(int, input().split())
	s = list(s)
	i = 0
	a.append([])
	b.append([])
	while i != len(s):
		if s[i] != -1:
			s[i] -= 1
			s[i + 1] -= 1
		a[-1].append(s[i])
		b[-1].append(s[i + 1])
		i += 2
ans = {}
dir = [[0, 1], [1, 0], [0, -1], [-1, 0]]
c = 'LURD'
pa = pb = None

def f(A, B):
	stack = [(A, B)]
	while len(stack) != 0:
		(A, B) = stack.pop()
		for i in range(4):
			[ga, gb] = dir[i]
			ga += A
			gb += B
			if (ga, gb) not in ans and 0 <= ga < n and (0 <= gb < n) and (a[ga][gb] == pa) and (b[ga][gb] == pb):
				ans[ga, gb] = c[i]
				stack.append((ga, gb))
for i in range(n):
	for j in range(n):
		if (i, j) not in ans:
			if a[i][j] == i and b[i][j] == j:
				pa = i
				pb = j
				ans[i, j] = 'X'
				f(i, j)
			if a[i][j] == -1:
				pa = pb = -1
				for k in range(4):
					[ga, gb] = dir[k]
					ga += i
					gb += j
					if 0 <= ga < n and 0 <= gb < n and (a[ga][gb] == -1):
						ans[i, j] = c[(k + 2) % 4]
						f(i, j)
						break
for i in range(n):
	for j in range(n):
		if (i, j) not in ans:
			print('INVALID')
			exit()
print('VALID')
for i in range(n):
	print(''.join([ans[i, j] for j in range(n)]))


import sys
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep='\n')

def II():
	return int(sys.stdin.readline())

def MI():
	return map(int, sys.stdin.readline().split())

def LI():
	return list(map(int, sys.stdin.readline().split()))

def LLI(rows_number):
	return [LI() for _ in range(rows_number)]

def SI():
	return sys.stdin.readline()[:-1]
dij = [(1, 0), (0, 1), (-1, 0), (0, -1)]
dirtoc = ['D', 'R', 'U', 'L']

def main():

	def dfs(i, j):
		stack = [(i, j)]
		while stack:
			(i, j) = stack.pop()
			for (dir, (di, dj)) in enumerate(dij):
				(ni, nj) = (i + di, j + dj)
				if ni < 0 or nj < 0 or ni >= n or (nj >= n):
					continue
				if ans[ni][nj]:
					continue
				if t[i][j] != t[ni][nj]:
					continue
				ans[ni][nj] = dirtoc[dir - 2]
				stack.append((ni, nj))
	n = II()
	t = [[0] * n for _ in range(n)]
	ans = [[''] * n for _ in range(n)]
	for i in range(n):
		row = LI()
		for j in range(n):
			t[i][j] = (row[j * 2] - 1, row[j * 2 + 1] - 1)
	for i in range(n):
		for j in range(n):
			if ans[i][j]:
				continue
			if t[i][j] == (i, j):
				ans[i][j] = 'X'
				dfs(i, j)
			if t[i][j] == (-2, -2):
				for (dir, (di, dj)) in enumerate(dij):
					(ni, nj) = (i + di, j + dj)
					if ni < 0 or nj < 0 or ni >= n or (nj >= n):
						continue
					if t[ni][nj] == (-2, -2):
						ans[i][j] = dirtoc[dir]
						break
				else:
					print('INVALID')
					exit()
	for i in range(n):
		for j in range(n):
			if ans[i][j] == '':
				print('INVALID')
				exit()
	print('VALID')
	for row in ans:
		print(*row, sep='')
main()


from heapq import heappush, heappop, heapify
from collections import deque, defaultdict, Counter
import itertools
from functools import *
from itertools import permutations, combinations, groupby
import sys
import bisect
import string
import math
import time
import random

def Golf():
	(*a,) = map(int, open(0))

def S_():
	return input()

def IS():
	return input().split()

def LS():
	return [i for i in input().split()]

def I():
	return int(input())

def MI():
	return map(int, input().split())

def LI():
	return [int(i) for i in input().split()]

def LI_():
	return [int(i) - 1 for i in input().split()]

def NI(n):
	return [int(input()) for i in range(n)]

def NI_(n):
	return [int(input()) - 1 for i in range(n)]

def StoI():
	return [ord(i) - 97 for i in input()]

def ItoS(nn):
	return chr(nn + 97)

def LtoS(ls):
	return ''.join([chr(i + 97) for i in ls])

def GI(V, E, Directed=False, index=0):
	org_inp = []
	g = [[] for i in range(n)]
	for i in range(E):
		inp = LI()
		org_inp.append(inp)
		if index == 0:
			inp[0] -= 1
			inp[1] -= 1
		if len(inp) == 2:
			(a, b) = inp
			g[a].append(b)
			if not Directed:
				g[b].append(a)
		elif len(inp) == 3:
			(a, b, c) = inp
			aa = (inp[0], inp[2])
			bb = (inp[1], inp[2])
			g[a].append(bb)
			if not Directed:
				g[b].append(aa)
	return (g, org_inp)

def GGI(h, w, search=None, replacement_of_found='.', mp_def={'#': 1, '.': 0}):
	mp = [1] * (w + 2)
	found = {}
	for i in range(h):
		s = input()
		for char in search:
			if char in s:
				found[char] = (i + 1) * (w + 2) + s.index(char) + 1
				mp_def[char] = mp_def[replacement_of_found]
		mp += [1] + [mp_def[j] for j in s] + [1]
	mp += [1] * (w + 2)
	return (h + 2, w + 2, mp, found)

def TI(n):
	return GI(n, n - 1)

def bit_combination(k, n=2):
	rt = []
	for tb in range(n ** k):
		s = [tb // n ** bt % n for bt in range(k)]
		rt += [s]
	return rt

def show(*inp, end='\n'):
	if show_flg:
		print(*inp, end=end)
YN = ['YES', 'NO']
Yn = ['Yes', 'No']
mo = 10 ** 9 + 7
inf = float('inf')
l_alp = string.ascii_lowercase
input = lambda : sys.stdin.readline().rstrip()

def ran_input():
	import random
	n = random.randint(4, 16)
	(rmin, rmax) = (1, 10)
	a = [random.randint(rmin, rmax) for _ in range(n)]
	return (n, a)
show_flg = False
show_flg = True
n = I()
h = n + 2
mp = [[-2] * h] + [[-2] + [None] * n + [-2] for i in range(n)] + [[-2] * h]
ch = [[None] * h for i in range(h)]
gl = []
fv = []
for i in range(n):
	a = LI()
	for j in range(n):
		(r, c) = a[2 * j:2 * j + 2]
		if (r, c) == (-1, -1):
			mp[i + 1][j + 1] = -1
			fv.append((i + 1) * h + (j + 1))
		else:
			mp[i + 1][j + 1] = r * h + c
			if (i + 1) * h + (j + 1) == mp[i + 1][j + 1]:
				ch[i + 1][j + 1] = 'X'
				gl.append(mp[i + 1][j + 1])
dc = {-1: 'R', 1: 'L', -h: 'D', h: 'U'}
while gl:
	Q = [gl.pop()]
	while Q:
		q = Q.pop()
		(r, c) = (q // h, q % h)
		for i in [+1, -1, +h, -h]:
			(nr, nc) = ((q + i) // h, (q + i) % h)
			if mp[nr][nc] == mp[r][c] and ch[nr][nc] == None:
				ch[nr][nc] = dc[i]
				Q.append(q + i)
while fv:
	Q = [fv.pop()]
	while Q:
		q = Q.pop()
		(r, c) = (q // h, q % h)
		for i in [+1, -1, +h, -h]:
			(nr, nc) = ((q + i) // h, (q + i) % h)
			if mp[nr][nc] == mp[r][c] and ch[nr][nc] == None:
				ch[nr][nc] = dc[i]
				if ch[r][c] == None:
					ch[r][c] = dc[-i]
				Q.append(q + i)
for i in mp:
	0
for i in range(1, n + 1):
	for j in range(1, n + 1):
		if ch[i][j] == None:
			print('INVALID')
			exit()
print('VALID')
for i in range(1, n + 1):
	show(''.join(ch[i][1:n + 1]))


n = int(input())
board = [[None] * n for _ in range(n)]
for i in range(n):
	row = list(map(lambda x: int(x) - 1, input().split()))
	for j in range(n):
		board[i][j] = (row[2 * j], row[2 * j + 1])
		if board[i][j] == (i, j):
			board[i][j] = 'X'
valid = True
stk = []
for i in range(n):
	for j in range(n):
		if board[i][j] == 'X':
			stk.append((i, j, i, j, 'X'))
while len(stk) != 0:
	(i, j, x, y, mv) = stk.pop()
	board[i][j] = mv
	if i - 1 >= 0 and board[i - 1][j] == (x, y):
		stk.append((i - 1, j, x, y, 'D'))
	if i + 1 < n and board[i + 1][j] == (x, y):
		stk.append((i + 1, j, x, y, 'U'))
	if j + 1 < n and board[i][j + 1] == (x, y):
		stk.append((i, j + 1, x, y, 'L'))
	if j - 1 >= 0 and board[i][j - 1] == (x, y):
		stk.append((i, j - 1, x, y, 'R'))
for i in range(n):
	for j in range(n):
		if board[i][j] == (-2, -2):
			ok = False
			if i - 1 >= 0 and board[i - 1][j] == (-2, -2):
				(board[i][j], ok) = ('U', True)
				stk.append((i - 1, j, 'D'))
			if i + 1 < n and board[i + 1][j] == (-2, -2):
				(board[i][j], ok) = ('D', True)
				stk.append((i + 1, j, 'U'))
			if j + 1 < n and board[i][j + 1] == (-2, -2):
				(board[i][j], ok) = ('R', True)
				stk.append((i, j + 1, 'L'))
			if j - 1 >= 0 and board[i][j - 1] == (-2, -2):
				(board[i][j], ok) = ('L', True)
				stk.append((i, j - 1, 'R'))
			if not ok:
				valid = False
			while len(stk) > 0:
				(x, y, mv) = stk.pop()
				board[x][y] = mv
				if x - 1 >= 0 and board[x - 1][y] == (-2, -2):
					stk.append((x - 1, y, 'D'))
				if x + 1 < n and board[x + 1][y] == (-2, -2):
					stk.append((x + 1, y, 'U'))
				if y + 1 < n and board[x][y + 1] == (-2, -2):
					stk.append((x, y + 1, 'L'))
				if y - 1 >= 0 and board[x][y - 1] == (-2, -2):
					stk.append((x, y - 1, 'R'))
for i in range(n):
	for j in range(n):
		if isinstance(board[i][j], tuple):
			valid = False
			break
if valid:
	print('VALID')
	for i in range(n):
		print(''.join(board[i]))
else:
	print('INVALID')


import sys
input = iter(sys.stdin.readlines()).__next__
n = int(input())
plans = [[None] * (n + 2) for _ in range(n + 2)]
blocked = set()
for r in range(1, n + 1):
	line_iter = map(int, input().split())
	for c in range(1, n + 1):
		x = next(line_iter)
		y = next(line_iter)
		if (x, y) == (-1, -1):
			plans[r][c] = -1
		else:
			plans[r][c] = (x, y)
			if (x, y) == (r, c):
				blocked.add((x, y))

def build(plans, blocked):
	board = [[None] * n for _ in range(n)]
	D_PAD = {'D': (1, 0), 'U': (-1, 0), 'R': (0, 1), 'L': (0, -1)}
	for r in range(1, n + 1):
		for c in range(1, n + 1):
			if plans[r][c] == -1:
				for (char, d) in D_PAD.items():
					if plans[r + d[0]][c + d[1]] == -1:
						board[r - 1][c - 1] = char
						break
				else:
					return None
	for (sx, sy) in blocked:
		queue = [(sx, sy, 'X')]
		visited = set([(sx, sy)])
		while queue:
			(ux, uy, char) = queue.pop()
			board[ux - 1][uy - 1] = char
			for (char, d) in D_PAD.items():
				v = (ux - d[0], uy - d[1])
				if v not in visited:
					visited.add(v)
					if plans[v[0]][v[1]] == (sx, sy):
						queue.append((v[0], v[1], char))
	for row in board:
		if any((x is None for x in row)):
			return None
	return board
board = build(plans, blocked)
if board:
	print('VALID')
	print(*(''.join(row) for row in board), sep='\n')
else:
	print('INVALID')


import collections

def f():
	n = int(input())
	ends = [[None for i in range(n)] for j in range(n)]
	tags = [['' for i in range(n)] for j in range(n)]
	for i in range(n):
		row = [int(s) - 1 for s in input().split()]
		for j in range(n):
			x = row[2 * j]
			if x != -2:
				y = row[2 * j + 1]
				ends[i][j] = (x, y)
				tags[x][y] = 'X'
	gos = {'U': (-1, 0), 'D': (1, 0), 'L': (0, -1), 'R': (0, 1)}

	def checkValid(x, y):
		if 0 <= x and x < n and (0 <= y) and (y < n):
			return True
		return False

	def goToInfNb(i, j):
		for dir in gos:
			(x, y) = gos[dir]
			if checkValid(i + x, j + y) and (not ends[i + x][j + y]):
				return dir
		return None
	for i in range(n):
		for j in range(n):
			if not ends[i][j] and (not tags[i][j]):
				dr = goToInfNb(i, j)
				if not dr:
					print('INVALID')
					return
				tags[i][j] = dr
	backs = {'D': (-1, 0), 'U': (1, 0), 'R': (0, -1), 'L': (0, 1)}

	def bfs(root):
		q = collections.deque()
		q.append(root)
		while q:
			(i, j) = q.popleft()
			for dir in backs:
				(x, y) = backs[dir]
				(ni, nj) = (i + x, j + y)
				if checkValid(ni, nj):
					if not tags[ni][nj] and ends[ni][nj] == root:
						tags[ni][nj] = dir
						q.append((ni, nj))
	for i in range(n):
		for j in range(n):
			if tags[i][j] == 'X':
				if ends[i][j] != (i, j):
					print('INVALID')
					return
				bfs((i, j))
	for i in range(n):
		for j in range(n):
			if tags[i][j] == '':
				print('INVALID')
				return
	print('VALID')
	for i in range(n):
		print(''.join(tags[i]))
f()


from collections import deque
n = int(input())
d = [[0] * n for _ in range(n)]
for r in range(n):
	nums = list(map(int, input().split()))
	i = 0
	while i + 1 < 2 * n:
		d[r][i // 2] = (nums[i], nums[i + 1])
		i += 2
result = [[None] * n for _ in range(n)]

def bfs(rs, cs, val):
	queue = deque([(rs, cs)])
	while queue:
		(r, c) = queue.popleft()
		for (dr, dc, dir) in [(0, 1, 'L'), (0, -1, 'R'), (1, 0, 'U'), (-1, 0, 'D')]:
			(r2, c2) = (r + dr, c + dc)
			if not 0 <= r2 < n or not 0 <= c2 < n:
				continue
			if result[r2][c2] is not None:
				continue
			if d[r2][c2] != val:
				continue
			result[r2][c2] = dir
			queue.append((r2, c2))
for r in range(n):
	for c in range(n):
		if result[r][c] is not None:
			continue
		if d[r][c] == (r + 1, c + 1):
			result[r][c] = 'X'
			bfs(r, c, d[r][c])
		elif d[r][c] == (-1, -1):
			for (dr, dc, dir, opp) in [(0, 1, 'L', 'R'), (0, -1, 'R', 'L'), (1, 0, 'U', 'D'), (-1, 0, 'D', 'U')]:
				(r2, c2) = (r + dr, c + dc)
				if not 0 <= r2 < n or not 0 <= c2 < n:
					continue
				if result[r2][c2] is not None:
					continue
				if d[r2][c2] != (-1, -1):
					continue
				result[r2][c2] = dir
				result[r][c] = opp
				bfs(r2, c2, (-1, -1))
				bfs(r, c, (-1, -1))
				break
			else:
				print('INVALID')
				exit(0)
for r in range(n):
	for c in range(n):
		if result[r][c] is None:
			print('INVALID')
			exit(0)
print('VALID')
for r in result:
	print(''.join(r))


n = int(input())
N = n
lis = [[] for i in range(n)]
ans = [[None] * n for i in range(n)]
vail = [[False] * n for i in range(n)]
plis = []
vlis = []
for i in range(n):
	a = list(map(int, input().split()))
	for j in range(0, 2 * n - 1, 2):
		lis[i].append([a[j] - 1, a[j + 1] - 1])
		if a[j] - 1 == i and a[j + 1] - 1 == j // 2:
			ans[i][j // 2] = 'X'
			plis.append([i, j // 2])
		elif a[j] == -1:
			ans[i][j // 2] = 'V'
			vail[i][j // 2] = True
			vlis.append([i, j // 2])
from collections import deque
tl = [[-1, 0, 'D'], [1, 0, 'U'], [0, -1, 'R'], [0, 1, 'L']]
for (px, py) in plis:
	q = deque([[px, py]])
	while len(q) > 0:
		(x, y) = q.popleft()
		for (sx, sy, d) in tl:
			if 0 <= x + sx < N and 0 <= y + sy < N and (ans[x + sx][y + sy] == None) and (lis[x + sx][y + sy][0] == px) and (lis[x + sx][y + sy][1] == py):
				ans[x + sx][y + sy] = d
				q.append([x + sx, y + sy])
tl = [[-1, 0, 'D', 'U'], [1, 0, 'U', 'D'], [0, -1, 'R', 'L'], [0, 1, 'L', 'R']]
for (x, y) in vlis:
	for (sx, sy, d, nd) in tl:
		if 0 <= x + sx < N and 0 <= y + sy < N and vail[x + sx][y + sy]:
			ans[x][y] = nd
import sys
for i in range(N):
	for j in range(N):
		if ans[i][j] == None or ans[i][j] == 'V':
			print('INVALID')
			sys.exit()
print('VALID')
for i in ans:
	print(''.join(i))


import sys
input = sys.stdin.readline
n = int(input())
iii = [list(map(int, input().split())) for i in range(n)]
a = [[0 for i in range(n)] for j in range(n)]
ans = [[0 for i in range(n)] for j in range(n)]
for i in range(n):
	for j in range(n):
		a[i][j] = (iii[i][2 * j], iii[i][2 * j + 1])
for i in range(n):
	for j in range(n):
		if a[i][j] == (i + 1, j + 1):
			ans[i][j] = 'X'
		elif a[i][j][0] < 0:
			flg = 0
			for (ni, nj) in ((i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1)):
				if 0 <= ni <= n - 1 and 0 <= nj <= n - 1 and (a[i][j] == a[ni][nj]):
					flg = 1
					if ni == i + 1 and nj == j:
						ans[i][j] = 'D'
					elif ni == i - 1 and nj == j:
						ans[i][j] = 'U'
					elif ni == i and nj == j + 1:
						ans[i][j] = 'R'
					elif ni == i and nj == j - 1:
						ans[i][j] = 'L'
			if not flg:
				print('INVALID')
				exit()
for i in range(n):
	for j in range(n):
		if ans[i][j] == 'X':
			stack = [(i, j)]
			while stack:
				(x, y) = stack.pop()
				for (nx, ny) in ((x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)):
					if 0 <= nx <= n - 1 and 0 <= ny <= n - 1 and (a[x][y] == a[nx][ny]) and (ans[nx][ny] == 0):
						if nx == x + 1 and ny == y:
							ans[nx][ny] = 'U'
							stack.append((nx, ny))
						elif nx == x - 1 and ny == y:
							ans[nx][ny] = 'D'
							stack.append((nx, ny))
						elif nx == x and ny == y + 1:
							ans[nx][ny] = 'L'
							stack.append((nx, ny))
						elif nx == x and ny == y - 1:
							ans[nx][ny] = 'R'
							stack.append((nx, ny))
for i in range(n):
	if ans[i].count(0) >= 1:
		print('INVALID')
		exit()
print('VALID')
for arr in ans:
	print(*arr, sep='')


from collections import deque

def problem(m):

	def bfs(i, j):
		q = deque([(i, j)])
		while len(q):
			(i, j) = q.popleft()
			for (a, b, d) in [(i - 1, j, 'D'), (i + 1, j, 'U'), (i, j - 1, 'R'), (i, j + 1, 'L')]:
				if a == -1 or a == n or b == -1 or (b == n) or v[a][b]:
					continue
				if m[i][j] == m[a][b]:
					v[a][b] = d
					q.append((a, b))
	for i in range(n):
		for j in range(n):
			if m[i][j] == (i, j):
				v[i][j] = 'X'
				bfs(i, j)
			if m[i][j] == (-2, -2):
				for (a, b, nxt, prv) in [(i + 1, j, 'D', 'U'), (i - 1, j, 'U', 'D'), (i, j + 1, 'R', 'L'), (i, j - 1, 'L', 'R')]:
					if a == -1 or a == n or b == -1 or (b == n):
						continue
					if m[a][b] == (-2, -2):
						(v[i][j], v[a][b]) = (nxt, prv)
						break
				else:
					return 'INVALID'
	for i in range(n):
		for j in range(n):
			if not v[i][j]:
				return 'INVALID'
	return 'VALID\n' + '\n'.join([''.join(x) for x in v])
n = int(input())
m = [[None] * n for _ in range(n)]
v = [[False] * n for _ in range(n)]
for i in range(n):
	r = list(map(int, input().split()))
	for j in range(n):
		(a, b) = (r[2 * j] - 1, r[2 * j + 1] - 1)
		m[i][j] = (a, b)
print(problem(m))


d4i = [0, -1, 0, 1]
d4j = [-1, 0, 1, 0]
direction = ['L', 'U', 'R', 'D']
back = ['R', 'D', 'L', 'U']

def main():
	n = int(input())
	finalState = [[] for _ in range(n)]
	ans = [[None for _ in range(n)] for __ in range(n)]
	for i in range(n):
		temp = readIntArr()
		for j in range(n):
			finalState[i].append([temp[2 * j] - 1, temp[2 * j + 1] - 1])
	endPoints = []
	cyclePoints = set()
	for i in range(n):
		for j in range(n):
			(x, y) = finalState[i][j]
			if x == i and y == j:
				ans[i][j] = 'X'
				endPoints.append([x, y])
			elif x == -2:
				ans[i][j] = 'c'
				cyclePoints.add((i, j))
	for (endX, endY) in endPoints:
		stack = [[endX, endY]]
		while stack:
			(i, j) = stack.pop()
			for z in range(4):
				ii = i + d4i[z]
				if not 0 <= ii < n:
					continue
				jj = j + d4j[z]
				if not 0 <= jj < n:
					continue
				if ans[ii][jj] == None and finalState[ii][jj] == [endX, endY]:
					ans[ii][jj] = back[z]
					stack.append([ii, jj])
	for (ci, cj) in cyclePoints:
		for z in range(4):
			ii = ci + d4i[z]
			jj = cj + d4j[z]
			if (ii, jj) in cyclePoints:
				ans[ci][cj] = direction[z]
				break
	ok = True
	outcomes = {'U', 'D', 'R', 'L', 'X'}
	for i in range(n):
		for j in range(n):
			if ans[i][j] not in outcomes:
				ok = False
	if ok:
		print('VALID')
		multiLineArrayOfArraysPrint(ans)
	else:
		print('INVALID')
	return
import sys
input = sys.stdin.buffer.readline

def oneLineArrayPrint(arr):
	print(' '.join([str(x) for x in arr]))

def multiLineArrayPrint(arr):
	print('\n'.join([str(x) for x in arr]))

def multiLineArrayOfArraysPrint(arr):
	print('\n'.join([''.join([str(x) for x in y]) for y in arr]))

def readIntArr():
	return [int(x) for x in input().split()]
inf = float('inf')
MOD = 10 ** 9 + 7
for _ in range(1):
	main()


from collections import deque

def bfs(i, j):
	q = deque([(i, j)])
	while q:
		(i, j) = q.popleft()
		for (a, b, d) in [(i + 1, j, 'U'), (i - 1, j, 'D'), (i, j + 1, 'L'), (i, j - 1, 'R')]:
			if a == -1 or a == n or b == -1 or (b == n) or v[a][b]:
				continue
			if m[a][b] == m[i][j]:
				v[a][b] = d
				q.append((a, b))
n = int(input())
m = [[None] * n for _ in range(n)]
v = [[False] * n for _ in range(n)]
for i in range(n):
	r = [int(i) for i in input().split()]
	for j in range(n):
		(a, b) = (r[2 * j] - 1, r[2 * j + 1] - 1)
		m[i][j] = (a, b)
for i in range(n):
	for j in range(n):
		if m[i][j] == (i, j):
			v[i][j] = 'X'
			bfs(i, j)
		if m[i][j] == (-2, -2):
			for (a, b, nxt, prev) in [(i + 1, j, 'D', 'U'), (i - 1, j, 'U', 'D'), (i, j + 1, 'R', 'L'), (i, j - 1, 'L', 'R')]:
				if a == -1 or a == n or b == -1 or (b == n):
					continue
				if m[a][b] == (-2, -2):
					(v[i][j], v[a][b]) = (nxt, prev)
					break
			else:
				print('INVALID')
				exit()
for i in range(n):
	for j in range(n):
		if v[i][j] == False:
			print('INVALID')
			exit()
print('VALID')
print('\n'.join([''.join(x) for x in v]))


import itertools as it
from collections import deque
n = int(input())
bd = [[] for _ in range(n)]
for i in range(n):
	lt = list(map(int, input().split()))
	for j in range(n):
		bd[i].append((lt[j * 2] - 1, lt[j * 2 + 1] - 1))

def rpath(tr, tc, r, c):
	q = deque([(r, c)])
	while q:
		(i, j) = q.popleft()
		edge = [(i - 1, j, 'D'), (i + 1, j, 'U'), (i, j - 1, 'R'), (i, j + 1, 'L')]
		for (a, b, d) in edge:
			if a < 0 or a >= n or b < 0 or (b >= n):
				continue
			if bd[a][b] != (tr, tc) or res[a][b]:
				continue
			res[a][b] = d
			q.append((a, b))
ok = 1
res = [[None] * n for _ in range(n)]
for (i, j) in it.product(range(n), range(n)):
	if bd[i][j] == (i, j):
		res[i][j] = 'X'
		rpath(i, j, i, j)
	elif bd[i][j] == (-2, -2):
		edge = [(i - 1, j, 'U', 'D'), (i + 1, j, 'D', 'U'), (i, j - 1, 'L', 'R'), (i, j + 1, 'R', 'L')]
		for (a, b, cur, next) in edge:
			if a < 0 or a >= n or b < 0 or (b >= n):
				continue
			if bd[a][b] != (-2, -2):
				continue
			(res[i][j], res[a][b]) = (cur, next)
			break
		else:
			ok = 0
			break
if not all((res[i][j] for (i, j) in it.product(range(n), range(n)))):
	ok = 0
print('VALID' if ok else 'INVALID')
if ok:
	print('\n'.join([''.join(u) for u in res]))


import sys
from collections import defaultdict
input = sys.stdin.readline
INF = 2 ** 62 - 1

def read_int():
	return int(input())

def read_int_n():
	return list(map(int, input().split()))

def slv(N, G):
	ans = [['.'] * N for _ in range(N)]
	inf = (-2, -2)
	goals = set()
	for i in range(N):
		for j in range(N):
			if G[i][j] != inf:
				(x, y) = G[i][j]
				if G[x][y] != (x, y):
					return 'INVALID'
				ans[x][y] = 'X'
				goals.add((x, y))

	def f(g, s):
		stack = [s]
		g[s] = s
		while stack:
			(x, y) = stack.pop()
			for (i, j) in ((-1, 0), (1, 0), (0, -1), (0, 1)):
				nx = x + i
				ny = y + j
				if 0 <= nx < N and 0 <= ny < N:
					if G[nx][ny] == s and (nx, ny) not in g:
						g[nx, ny] = (x, y)
						stack.append((nx, ny))
		return g
	g = {}
	while goals:
		g = f(g, goals.pop())
	for x in range(N):
		for y in range(N):
			if G[x][y][0] >= 0:
				continue
			if (x, y) in g:
				continue
			for (i, j) in ((-1, 0), (1, 0), (0, -1), (0, 1)):
				nx = x + i
				ny = y + j
				if 0 <= nx < N and 0 <= ny < N:
					if G[nx][ny][0] < 0:
						g[x, y] = (nx, ny)
						if (nx, ny) not in g:
							g[nx, ny] = (x, y)
						break
	for (u, v) in g.items():
		(x, y) = u
		if u[0] > v[0]:
			ans[x][y] = 'U'
		elif u[0] < v[0]:
			ans[x][y] = 'D'
		elif u[1] > v[1]:
			ans[x][y] = 'L'
		elif u[1] < v[1]:
			ans[x][y] = 'R'
	for i in range(N):
		for j in range(N):
			if ans[i][j] == '.':
				return 'INVALID'
	return 'VALID\n' + '\n'.join([''.join(r) for r in ans])

def main():
	N = read_int()
	GRID = [read_int_n() for _ in range(N)]
	GRID = [[(r[2 * i] - 1, r[2 * i + 1] - 1) for i in range(N)] for r in GRID]
	print(slv(N, GRID))
main()


import sys
reader = (s.rstrip() for s in sys.stdin)
input = reader.__next__
n = int(input())
board = [[-1] * n for i in range(n)]
black = dict()
cnt = 0
for i in range(n):
	xy = list(map(int, input().split()))
	for j in range(n):
		x = xy[2 * j] - 1
		y = xy[2 * j + 1] - 1
		if x >= 0:
			if (x, y) not in black:
				black[x, y] = cnt
				cnt += 1
			board[i][j] = black[x, y]
for ((x, y), col) in black.items():
	if board[x][y] != col:
		print('INVALID')
		exit()
ans = [[''] * n for i in range(n)]
from collections import deque
dxdy = [(0, 1, 'L'), (1, 0, 'U'), (0, -1, 'R'), (-1, 0, 'D')]

def bfs(x, y, col, s):
	q = deque()
	q.append((x, y, s))
	start = True
	while q:
		(x, y, c) = q.pop()
		if not start and ans[x][y] != '':
			continue
		start = False
		ans[x][y] = c
		for (dx, dy, c) in dxdy:
			nx = x + dx
			ny = y + dy
			if 0 <= nx < n and 0 <= ny < n and (board[nx][ny] == col) and (ans[nx][ny] == ''):
				q.append((nx, ny, c))
for ((x, y), col) in black.items():
	bfs(x, y, col, 'X')
for i in range(n):
	for j in range(n - 1):
		if board[i][j] == board[i][j + 1] == -1 and ans[i][j] == ans[i][j + 1] == '':
			bfs(i, j, -1, 'R')
for i in range(n - 1):
	for j in range(n):
		if board[i][j] == board[i + 1][j] == -1 and ans[i][j] == ans[i + 1][j] == '':
			bfs(i, j, -1, 'D')
for i in range(n):
	if any((j == '' for j in ans[i])):
		print('INVALID')
		exit()
print('VALID')
for i in range(n):
	print(''.join(ans[i]))


import sys
input = sys.stdin.readline
n = int(input())
MAP = [list(map(int, input().split())) for i in range(n)]
for i in range(n):
	MAP[i] = [(MAP[i][j * 2], MAP[i][j * 2 + 1]) for j in range(n)]
ANS = [['N'] * n for i in range(n)]
from collections import deque
Q = deque()
for i in range(n):
	for j in range(n):
		(x, y) = (MAP[i][j][0], MAP[i][j][1])
		if x - 1 == i and y - 1 == j:
			ANS[x - 1][y - 1] = 'X'
			Q.append((x - 1, y - 1))
while Q:
	(x, y) = Q.pop()
	if 0 <= x - 1 < n and ANS[x - 1][y] == 'N':
		if MAP[x - 1][y] == MAP[x][y]:
			ANS[x - 1][y] = 'D'
			Q.append((x - 1, y))
	if 0 <= x + 1 < n and ANS[x + 1][y] == 'N':
		if MAP[x + 1][y] == MAP[x][y]:
			ANS[x + 1][y] = 'U'
			Q.append((x + 1, y))
	if 0 <= y - 1 < n and ANS[x][y - 1] == 'N':
		if MAP[x][y - 1] == MAP[x][y]:
			ANS[x][y - 1] = 'R'
			Q.append((x, y - 1))
	if 0 <= y + 1 < n and ANS[x][y + 1] == 'N':
		if MAP[x][y + 1] == MAP[x][y]:
			ANS[x][y + 1] = 'L'
			Q.append((x, y + 1))
for x in range(n):
	for y in range(n):
		if MAP[x][y] == (-1, -1):
			if 0 <= x - 1 < n and 0 <= y < n and (MAP[x - 1][y] == (-1, -1)):
				ANS[x][y] = 'U'
				continue
			if 0 <= x + 1 < n and 0 <= y < n and (MAP[x + 1][y] == (-1, -1)):
				ANS[x][y] = 'D'
				continue
			if 0 <= y - 1 < n and 0 <= x < n and (MAP[x][y - 1] == (-1, -1)):
				ANS[x][y] = 'L'
				continue
			if 0 <= y + 1 < n and 0 <= x < n and (MAP[x][y + 1] == (-1, -1)):
				ANS[x][y] = 'R'
				continue
for i in range(n):
	for j in range(n):
		if ANS[i][j] == 'N':
			print('INVALID')
			sys.exit()
print('VALID')
for i in range(n):
	print(''.join(ANS[i]))


from collections import deque
import sys
imput = sys.stdin.readline
n = int(input())
li = [list(map(int, input().split())) for i in range(n)]
to_char = {0: 'L', 1: 'D', 2: 'R', 3: 'U'}

def goal(i, j):
	return (li[i][j * 2], li[i][j * 2 + 1])

def dfs(i, j):
	q = deque([(i, j)])
	for (nxt_i, nxt_j, ind) in [(i + 1, j, 1), (i, j + 1, 2), (i - 1, j, 3), (i, j - 1, 0)]:
		if not (0 <= nxt_i < n and 0 <= nxt_j < n):
			continue
		if goal(nxt_i, nxt_j) != (-1, -1) or ans[nxt_i][nxt_j] != 0:
			continue
		ans[i][j] = to_char[ind]
	while q:
		(i, j) = q.pop()
		for (nxt_i, nxt_j, ind) in [(i + 1, j, 3), (i, j + 1, 0), (i - 1, j, 1), (i, j - 1, 2)]:
			if not (0 <= nxt_i < n and 0 <= nxt_j < n):
				continue
			if goal(nxt_i, nxt_j) != (-1, -1) or ans[nxt_i][nxt_j] != 0:
				continue
			ans[nxt_i][nxt_j] = to_char[ind]
			q.append((nxt_i, nxt_j))

def dfs2(i, j, ii, jj):
	q = deque([(i, j)])
	while q:
		(i, j) = q.pop()
		for (nxt_i, nxt_j, ind) in [(i + 1, j, 3), (i, j + 1, 0), (i - 1, j, 1), (i, j - 1, 2)]:
			if not (0 <= nxt_i < n and 0 <= nxt_j < n):
				continue
			if goal(nxt_i, nxt_j) != (ii, jj) or ans[nxt_i][nxt_j] != 0:
				continue
			ans[nxt_i][nxt_j] = to_char[ind]
			q.append((nxt_i, nxt_j))
ans = [[0] * n for _ in range(n)]
for i in range(n):
	for j in range(n):
		if li[i][j * 2] == -1 and ans[i][j] == 0:
			dfs(i, j)
			if ans[i][j] == 0:
				print('INVALID')
				exit()
for i in range(n):
	for j in range(n):
		(ii, jj) = goal(i, j)
		if ii == i + 1 and jj == j + 1:
			ans[i][j] = 'X'
			dfs2(i, j, ii, jj)
for i in range(n):
	for j in range(n):
		if ans[i][j] == 0:
			print('INVALID')
			exit()
print('VALID')
for i in ans:
	print(''.join(i))


import sys

def input():
	return sys.stdin.buffer.readline()[:-1]
n = int(input())
stops = [[-1 for _ in range(n)] for _ in range(n)]
ans = [[None for _ in range(n)] for _ in range(n)]
for i in range(n):
	t = list(map(int, input().split()))
	for j in range(n):
		stops[i][j] = n * (t[2 * j] - 1) + t[2 * j + 1] - 1
		if stops[i][j] == n * i + j:
			ans[i][j] = 'X'
(DX, DY, DIR, DIR2) = ([1, -1, 0, 0], [0, 0, 1, -1], ['U', 'D', 'L', 'R'], ['D', 'U', 'R', 'L'])

def dfs(start_list, block):
	stack = start_list
	while stack:
		(x, y) = stack.pop()
		for (dx, dy, di) in zip(DX, DY, DIR):
			if not (0 <= x + dx < n and 0 <= y + dy < n):
				continue
			if ans[x + dx][y + dy] is not None:
				continue
			if stops[x + dx][y + dy] == block:
				ans[x + dx][y + dy] = di
				stack.append((x + dx, y + dy))
	return
for i in range(n):
	for j in range(n):
		if ans[i][j] == 'X':
			dfs([(i, j)], stops[i][j])
		elif stops[i][j] < 0 and ans[i][j] is None:
			for (di, dj, dir1, dir2) in zip(DX, DY, DIR, DIR2):
				if not (0 <= i + di < n and 0 <= j + dj < n):
					continue
				if stops[i + di][j + dj] < 0:
					ans[i][j] = dir2
					ans[i + di][j + dj] = dir1
					dfs([(i, j), (i + di, j + dj)], stops[i][j])
					break
			else:
				print('INVALID')
				sys.exit()
for i in range(n):
	for j in range(n):
		if ans[i][j] is None:
			print('INVALID')
			sys.exit()
print('VALID')
for a in ans:
	print(''.join(a))


def fill(r, c, result, mapa):
	n = len(result)
	que = [(r, c)]
	for (rr, cc, com, comr) in [(r - 1, c, 'D', 'U'), (r + 1, c, 'U', 'D'), (r, c - 1, 'R', 'L'), (r, c + 1, 'L', 'R')]:
		if 0 <= rr < n and 0 <= cc < n and (result[rr][cc] is None) and (mapa[rr][cc] == -1):
			result[rr][cc] = com
			result[r][c] = comr
			que.append((rr, cc))
			break
	else:
		return False
	index = 0
	while index < len(que):
		(r, c) = que[index]
		for (rr, cc, com) in [(r - 1, c, 'D'), (r + 1, c, 'U'), (r, c - 1, 'R'), (r, c + 1, 'L')]:
			if 0 <= rr < n and 0 <= cc < n and (result[rr][cc] is None) and (mapa[rr][cc] == -1):
				result[rr][cc] = com
				que.append((rr, cc))
		index += 1
	return True

def go():
	n = int(input())
	result = [[None] * n for _ in range(n)]
	que = []
	mapa = [[0] * n for _ in range(n)]
	infinites = 0
	count = 0
	for r in range(n):
		vals = list(map(lambda s: int(s) - 1, input().split()))
		(y, x) = (vals[::2], vals[1::2])
		for c in range(n):
			if x[c] == c and y[c] == r:
				result[r][c] = 'X'
				que.append((r, c))
				count += 1
			mapa[r][c] = -1 if x[c] < 0 else y[c] * n + x[c]
			infinites += x[c] < 0
	index = 0
	while index < len(que):
		(r, c) = que[index]
		for (rr, cc, com) in [(r - 1, c, 'D'), (r + 1, c, 'U'), (r, c - 1, 'R'), (r, c + 1, 'L')]:
			if 0 <= rr < n and 0 <= cc < n and (result[rr][cc] is None) and (mapa[rr][cc] == mapa[r][c]):
				result[rr][cc] = com
				count += 1
				que.append((rr, cc))
		index += 1
	if count + infinites != n * n:
		print('INVALID')
		return
	for r in range(n):
		for c in range(n):
			if result[r][c] is None:
				if mapa[r][c] != -1 or not fill(r, c, result, mapa):
					print('INVALID')
					return
	print('VALID')
	print('\n'.join((''.join(r) for r in result)))
go()


from collections import deque
N = int(input())
m = [[None] * N for i in range(N)]
v = [[False] * N for i in range(N)]
for i in range(N):
	r = list(map(int, input().split()))
	for j in range(N):
		(x, y) = (r[2 * j] - 1, r[2 * j + 1] - 1)
		m[i][j] = (x, y)

def bfs(x, y):
	q = deque()
	q.append((x, y))
	while len(q):
		(x, y) = q.popleft()
		for (i, j, d) in [(x - 1, y, 'D'), (x + 1, y, 'U'), (x, y - 1, 'R'), (x, y + 1, 'L')]:
			if i != -1 and i != N and (j != -1) and (j != N):
				if m[i][j] != m[x][y]:
					continue
				if not v[i][j]:
					v[i][j] = d
					q.append((i, j))
for i in range(N):
	for j in range(N):
		if m[i][j] == (i, j):
			v[i][j] = 'X'
			bfs(i, j)
		elif m[i][j] == (-2, -2):
			for (a, b, nxt, prev) in [(i - 1, j, 'U', 'D'), (i + 1, j, 'D', 'U'), (i, j - 1, 'L', 'R'), (i, j + 1, 'R', 'L')]:
				if a != -1 and a != N and (b != -1) and (b != N):
					if m[i][j] != m[a][b]:
						continue
					else:
						v[i][j] = nxt
						v[a][b] = prev
						break
for i in range(N):
	for j in range(N):
		if not v[i][j]:
			print('INVALID')
			exit()
print('VALID')
print('\n'.join([''.join(r) for r in v]))


from math import sqrt
import sys
from functools import reduce
from collections import deque
import io
import os

def input():
	return sys.stdin.readline().strip()

def iinput():
	return int(input())

def tinput():
	return input().split()

def rinput():
	return map(int, tinput())

def rlinput():
	return list(rinput())
mod = int(1000000000.0) + 7

def factors(n):
	return set(reduce(list.__add__, ([i, n // i] for i in range(1, int(n ** 0.5) + 1) if n % i == 0)))
n = iinput()
mat = [[[-1, -1] for i in range(n)] for i in range(n)]
ans = [['' for i in range(n)] for i in range(n)]
stack = deque()
for i in range(n):
	temp = rlinput()
	for j in range(n):
		mat[i][j][0] = temp[2 * j]
		mat[i][j][1] = temp[2 * j + 1]
		if (temp[2 * j], temp[2 * j + 1]) == (i + 1, j + 1):
			ans[i][j] = 'X'
			stack.append((i, j))
while stack:
	state = stack.pop()
	(i, j) = state
	if i < n - 1 and ans[i + 1][j] == '':
		if mat[i + 1][j] == mat[i][j]:
			ans[i + 1][j] = 'U'
			stack.append((i + 1, j))
	if j < n - 1 and ans[i][j + 1] == '':
		if mat[i][j + 1] == mat[i][j]:
			ans[i][j + 1] = 'L'
			stack.append((i, j + 1))
	if i > 0 and ans[i - 1][j] == '':
		if mat[i - 1][j] == mat[i][j]:
			ans[i - 1][j] = 'D'
			stack.append((i - 1, j))
	if j > 0 and ans[i][j - 1] == '':
		if mat[i][j - 1] == mat[i][j]:
			ans[i][j - 1] = 'R'
			stack.append((i, j - 1))
for i in range(n):
	for j in range(n):
		if mat[i][j] == [-1, -1]:
			if i < n - 1 and mat[i + 1][j] == [-1, -1]:
				ans[i][j] = 'D'
				continue
			if j < n - 1 and mat[i][j + 1] == [-1, -1]:
				ans[i][j] = 'R'
				continue
			if i > 0 and mat[i - 1][j] == [-1, -1]:
				ans[i][j] = 'U'
				continue
			if j > 0 and mat[i][j - 1] == [-1, -1]:
				ans[i][j] = 'L'
				continue
flag = True
for i in ans:
	for j in i:
		if j == '':
			print('INVALID')
			sys.exit()
print('VALID')
for i in ans:
	print(''.join(i))