Mirko phát hiện ra một bộ sưu tập ~N~ xe tăng đồ từ Thế chiến thứ hai trên mái nhà của ông nội. Anh ấy ngay lập tức gọi cho bạn Slavko để chơi cùng. Họ đã tạo ra một trận địa - một tấm bảng gỗ gồm các ô trong ~N~ hàng và ~N~ cột.

Mỗi xe tăng có thể di chuyển đến một trong bốn ô xung quanh trong một lần di chuyển. Một xe tăng có thể bắn vào bất kỳ ô nào trong cùng một hàng hoặc cột. Xe tăng được coi là bảo vệ hàng và cột mà nó đang ở.

Ngoài ra, không có hai xe tăng nào có thể ở trong cùng một ô vào bất kỳ thời điểm nào. Sau nhiều giờ chơi và hai lần thử trước đó, mẹ của Mirko la lớn họ xuống ăn trưa lần nữa, và họ quyết định sắp xếp lại các xe tăng sao cho mỗi xe tăng bảo vệ một hàng và một cột khác nhau (nghĩa là mỗi hàng và mỗi cột đều chỉ chứa một xe tăng). Tuy nhiên, họ muốn làm điều này bằng số lần di chuyển tối thiểu.

Viết chương trình tìm số lần di chuyển tối thiểu cần thiết để sắp xếp lại các xe tăng sao cho mỗi hàng và mỗi cột đều chứa một xe tăng duy nhất, và một chuỗi di chuyển ngắn nhất như vậy.

Input

Dòng đầu tiên gồm một số tự nhiên ~N~ (~5 <= N <= 500~).

~N~ dòng tiếp theo, mỗi dòng gồm 2 số tự nhiên ~R~ và ~C~ (~1 <= R, C <= N~), vị trí ban đầu của mỗi xe tăng khi mà mẹ gọi. Không có 2 xe tăng trên cùng một ô.

Output

In ra số lượt đi nhỏ nhất (gọi là ~K~) trên một dòng.

Mỗi trong ~K~ dòng tiếp theo chứa thông tin về xe tăng được di chuyển và hướng mà nó được di chuyển, được phân tách bởi một dấu cách duy nhất.

Các xe tăng được đánh số từ 1 đến ~N~, theo thứ tự chúng được cung cấp trong đầu vào.

Hướng có thể là một trong bốn chữ cái in hoa: 'L' cho trái, 'R' cho phải, 'U' cho lên và 'D' cho xuống.

Chú ý: Chuỗi không cần phải là duy nhất.

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 2

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