Mirko 在他祖父的阁楼上发现了一套可以追溯到第二次世界大战的 $N$ 辆玩具坦克。他立即叫他的朋友 Slavko 一起玩。他们制作了一个战场——一个由 $N$ 行 $N$ 列的正方形格子组成的木板。

在单次移动中，每辆坦克都可以移动到四个相邻格子之一。坦克可以射击同一行和同一列中的任何格子。我们称坦克正在守卫它所在的行和列。此外，在任何时候，任何两个坦克都不能处于同一个格子中。

在玩了几个小时并进行了两次尝试之后，Mirko 的妈妈又大声喊他们下楼吃午饭，于是他们决定重新排列坦克，使得每辆坦克守卫不同的行和列（这也意味着每行和每列都恰好包含一辆坦克）。

然而，他们希望用最少的移动步数来完成这一目标。

编写一个程序，求出重新排列坦克使每行和每列都恰好包含一辆坦克所需的最少移动步数，并输出其中一种最短的移动序列。

输入格式

第一行包含一个整数 $N$ ($5 \le N \le 500$)。

接下来的 $N$ 行，每行包含两个整数 $R$ 和 $C$ ($1 \le R, C \le N$)，表示在妈妈喊他们时，每辆坦克所在的行和列。没有两辆坦克在同一个格子中。

行和列的编号为 $1$ 到 $N$，从上到下、从左到右。

输出格式

第一行输出最少移动步数（记为 $K$）。

接下来的 $K$ 行，每行应包含被移动的坦克编号和移动方向，用单个空格分隔。

坦克按照输入中给出的顺序从 $1$ 到 $N$ 进行编号。

方向可以是以下四个大写字母之一：'L' 表示向左，'R' 表示向右，'U' 表示向上，'D' 表示向下。

注意：移动序列不唯一。

子任务

如果数量 $K$ 和移动序列均正确，您的程序将在该测试点获得满分。

如果您的程序输出了正确的数量 $K$ 但未输出移动序列，或者移动序列不正确，您将获得该测试点 60% 的分数。

样例

输入样例 1

5 
1 1 
1 2 
1 3 
1 4 
1 5

输出样例 1

10 
1 D 
2 D 
3 D 
4 D 
1 D 
2 D 
3 D 
1 D 
2 D 
1 D

输入样例 2

5 
2 3 
3 2 
3 3 
3 4 
4 3

输出样例 2

8 
1 R 
1 R 
2 U 
2 U 
4 D 
4 D 
5 L 
5 L

输入样例 3

6 
1 1 
1 2 
2 1 
5 6 
6 5 
6 6

输出样例 3

8 
2 R 
2 D 
3 D 
3 R 
4 U 
4 L 
5 L 
5 U