Problem Description

On an $n \times n$ chessboard, there are $n$ tanks, each capable of attacking all squares in its row and column.

A child was happily playing a game of "World War II" in his mind, but his mother suddenly called him for dinner.

He is very reluctant to stop and plans to move the tanks several times, each time moving one tank one square in any of the four directions: up, down, left, or right.

He now asks you to determine the minimum number of moves required to ensure that the $n$ tanks cannot attack each other. Additionally, to avoid thinking and hurry to dinner, you need to provide one of the corresponding solutions.

Input Format

The first line of input contains an integer $n$, representing the side length of the chessboard and the number of tanks.

The next $n$ lines each contain two integers $r$ and $c$, indicating that the tank is located at the $r$-th row and $c$-th column when his mother called him for dinner.

Rows and columns are numbered from 1 to $n$ from top to bottom and from left to right, respectively, and it is guaranteed that no two tanks are in the same position.

Output Format

The first line of output contains an integer $k$, representing the minimum number of moves.

The next $k$ lines each contain an integer followed by a character, where the integer indicates the tank to be moved and the character is one of L (left), R (right), U (up), or D (down), indicating the direction of movement.

A correct sequence of moves may not be unique; any valid sequence will be accepted, as this problem uses a special judge.

Sample Input and Output

Sample Input #1

5
1 1
1 2
1 3
1 4
1 5

Sample Output #1

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

Sample Input #2

5
2 3
3 2
3 3
3 4
4 3

Sample Output #2

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

Sample Input #3

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

Sample Output #3

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

Notes

Data Size and Constraints

For $100\%$ of the data, it is guaranteed that $5 \le n \le 500$ and $1 \le r, c \le n$.

Notes

This problem is translated from COCI2006-2007 CONTEST #3 T4 TENKICI

见题面 Input 部分

见题面 Output 部分