纳什设计了一款有趣而简单的棋盘游戏,玩家只需遵循玩家当前所在的单元格上写的说明即可。
该棋盘游戏在 $$$n\times n$$$ 棋盘上进行。该板的行和列从 $$$1$$$ 到 $$$n$$$ 进行编号。第 $$$r$$$ 行和第 $$$c$$$ 列交叉处的单元格由 $$$(r, c)$$$ 表示。
棋盘上的一些单元格称为封锁区域。棋盘的每个单元格上都写有以下 $$$5$$$ 字符之一 - $$$U$$$、$$$D$$$、$$$L$$$、$$$R$$$ 或 $$$X$$$ - 玩家说明。假设当前单元格是$$$(r, c)$$$。如果角色是$$$R$$$,玩家应该移动到右侧单元格$$$(r, c+1)$$$,对于$$$L$$$,玩家应该移动到左侧单元格$$$(r, c-1)$$$,对于$$$U$$$,玩家应该移动到顶部单元格$$$(r-1, c)$$$,对于$$$D$$$,玩家应该移动到底部单元格$$$(r+1,c)$$$。最后,如果单元格中的字符是$$$X$$$,那么这个单元格就是封锁区域。玩家应该留在这个牢房里(从现在开始游戏对他来说不再那么有趣)。
保证角色的书写方式使得玩家永远不必走出棋盘,无论他从哪个单元格开始。
当玩家从一个单元格开始时,他会根据当前单元格中的角色移动。玩家不断移动,直到落在封锁区域内。玩家也有可能无限长时间地继续移动。
对于棋盘上的每个 $$$n^2$$$ 单元格,您的朋友 Alice 想知道,如果玩家从该单元格开始,游戏将如何进行。对于棋盘上的每个起始单元格,她写下玩家停止的单元格,或者玩家根本不会停止的单元格。她向您提供了她所写的信息:对于每个单元格 $$$(r, c)$$$ 她写了:
- 一对 ($$$x$$$,$$$y$$$),这意味着如果玩家从 $$$(r, c)$$$ 开始,他最终会在单元格 ($$$x$$$,$$$y$$$) 处。
- 或一对 ($$$-1$$$,$$$-1$$$),这意味着如果玩家从 $$$(r, c)$$$ 开始,他将继续无限长时间移动,并且永远不会进入封锁区域。
Alice 可能试图欺骗你,并且没有可能的网格可以满足 Alice 给你的所有约束。对于 Alice 向您提供的给定信息,您需要破译一个可能的棋盘,或者确定这样的棋盘不存在。如果存在多个满足所提供信息的不同板,您可以找到其中任何一个。
输入
输入的第一行包含一个整数 $$$n$$$ ($$$1 \leq n \leq 10^{3}$$$) — 棋盘的一侧。
输入的接下来的 $$$n$$$ 行中的第 $$$i$$$ 包含 $$$2n$$$ 整数 $$$x_1, y_1, x_2, y_2, \dots, x_n, y_n$$$,其中 $$$(x_j, y_j)$$$ ($$$1 \leq x_j \leq n, 1 \leq y_j \leq n$$$ 或 $$$(x_j,y_j)=(-1,-1)$$$) 是 Alice 为单元格 $$$(i, j)$$$ 编写的对。
输出
如果不存在满足 Alice 给您的信息的板,则打印包含 INVALID 的单行。
否则,在第一行打印 VALID。在接下来的 $$$n$$$ 行的第 $$$i$$$ 行中,打印 $$$n$$$ 字符的字符串,对应于您找到的合适板的第 $$$i$$$ 行中的字符。字符串的每个字符可以是 $$$U$$$、$$$D$$$、$$$L$$$、$$$R$$$ 或 $$$X$$$。如果存在多个满足所提供信息的不同板,您可以找到其中任何一个。
示例
输入 #1
2 1 1 1 1 2 2 2 2
输出 #1
VALID XL RX
输入 #2
3 -1 -1 -1 -1 -1 -1 -1 -1 2 2 -1 -1 -1 -1 -1 -1 -1 -1
输出 #2
VALID RRD UXD ULL
注意
对于样本测试 1:
输出中给定的网格是有效的。
- 如果玩家从$$$(1,1)$$$开始,他不会在$$$X$$$之后进一步移动并停在那里。
- 如果玩家从 $$$(1,2)$$$ 开始,他会跟随 $$$L$$$ 向左移动,并在 $$$(1,1)$$$ 处停止。
- 如果玩家从 $$$(2,1)$$$ 开始,他会在 $$$R$$$ 之后向右移动,并在 $$$(2,2)$$$ 处停止。
- 如果玩家从 $$$(2,2)$$$ 开始,他不会在 $$$X$$$ 之后进一步移动并停在那里。
模拟如下:
对于样本测试 2:
输出中给定的网格是有效的,因为玩家从除中心 $$$(2,2)$$$ 之外的任何单元格开始,在无限长的循环中保持移动并且永不停止。如果他从 $$$(2,2)$$$ 开始,他就不会按照指示 $$$X$$$ 进一步移动。
模拟如下: