Kinesis đang thám hiểm Đảo Chu Chu để tiêu diệt Phù thủy Đen thì bắt gặp Muto đói bụng. Simia, người hàng ngày vẫn cho Muto ăn, đã nhờ Kinesis giúp làm một chiếc bánh pizza khổng lồ cho Muto đang càu nhàu vì đói. Vì Muto to lớn đang chặn đường đến chỗ Phù thủy Đen, Kinesis không còn cách nào khác là phải giúp Simia.
Chiếc bánh pizza mà Muto muốn có dạng lưới kích thước $N \times N$, trong đó ô trên cùng bên trái là hàng $1$ cột $1$, và ô dưới cùng bên phải là hàng $N$ cột $N$. Công thức của Simia vẽ ra cách bố trí các viên thịt cần đặt lên bánh, và Kinesis phải đặt các viên thịt theo đúng công thức đó. Ban đầu, có một viên thịt đã được Simia đặt sẵn tại hàng $R$ cột $C$ của bánh. Hình dạng của viên thịt khớp chính xác với một ô trong lưới và không thể có nhiều hơn một viên thịt trong một ô.
Trạng thái của bánh pizza khi $N=5, R=3, C=2$ và các vị trí có thể sử dụng năng lực tâm linh từ bên ngoài bánh
Vì việc giẫm lên bánh sẽ làm nó không thể ăn được, Kinesis phải sử dụng năng lực tâm linh từ bên ngoài bánh để hoàn thành chiếc bánh. Quá trình sử dụng năng lực tâm linh $1$ lần như sau:
- Chọn vị trí để sử dụng năng lực tâm linh. Các vị trí khả thi là phía trên, phía dưới, bên trái hoặc bên phải của bánh. Năng lực tâm linh bắt đầu từ vị trí của Kinesis; nếu ở phía trên thì hướng tác động là tăng dần theo hàng, nếu ở phía dưới thì giảm dần theo hàng, nếu ở bên trái thì tăng dần theo cột, và nếu ở bên phải thì giảm dần theo cột.
- Chọn số thứ tự của hàng hoặc cột để sử dụng năng lực tâm linh. Năng lực tâm linh phải được sử dụng song song với hàng hoặc cột, và không thể tác động lên nhiều hơn một hàng hoặc cột cùng lúc.
- Sử dụng năng lực tâm linh. Có hai loại năng lực tâm linh có thể sử dụng:
- Đẩy (push): Đẩy viên thịt vào và đặt nó vào ô ngay trước viên thịt đầu tiên mà nó va chạm. Nếu có viên thịt ở ô đầu tiên theo hướng sử dụng năng lực trước khi đẩy, hoặc nếu không có viên thịt nào theo hướng đó khiến viên thịt bị đẩy không thể nằm trong bánh, thì viên thịt bị đẩy sẽ biến mất.
- Kéo (pull): Lấy viên thịt đầu tiên va chạm với năng lực tâm linh ra khỏi bánh. Nếu không có viên thịt nào theo hướng sử dụng năng lực, sẽ không có gì xảy ra.
Hình ảnh sử dụng năng lực tâm linh Đẩy (push) và Kéo (pull)
Nếu hoàn thành chiếc bánh theo công thức của Simia, Muto sẽ ăn ngon lành và mở đường cho Kinesis đi đến khu vực tiếp theo. Tuy nhiên, vì không biết khi nào Phù thủy Đen sẽ hủy diệt thế giới, Kinesis không thể lãng phí thời gian làm bánh.
Hãy in ra một trong những cách để hoàn thành chiếc bánh bằng cách sử dụng năng lực tâm linh không quá $2N^2$ lần.
Dữ liệu vào
Dòng đầu tiên chứa kích thước của bánh pizza $N$. ($3 \leq N \leq 50$)
Dòng thứ hai chứa hai số nguyên $R$ và $C$ cách nhau bởi dấu cách, biểu thị hàng và cột của viên thịt mà Simia đã đặt ban đầu. ($1 \leq R, C \leq N$)
Tiếp theo là $N$ dòng chứa cách bố trí các viên thịt theo công thức của Simia. Mỗi dòng chứa một chuỗi có độ dài $N$. Ký tự thứ $j$ trong dòng thứ $i$ của công thức biểu thị sự hiện diện của viên thịt tại hàng $i$ cột $j$, trong đó . là ô trống và # là ô có đặt viên thịt.
Dữ liệu ra
Nếu có thể hoàn thành chiếc bánh bằng cách sử dụng năng lực tâm linh không quá $2N^2$ lần, hãy in ra số lần Kinesis đã sử dụng năng lực tâm linh $M$ ở dòng đầu tiên. Lưu ý rằng $M$ không nhất thiết phải là số lần tối thiểu. ($0 \leq M \leq 2N^2$)
Nếu $M \geq 1$, từ dòng thứ hai trở đi, hãy in ra các hành động mà Kinesis đã thực hiện, mỗi hành động trên một dòng. Mỗi dòng chứa vị trí sử dụng năng lực tâm linh (phía trên: U, phía dưới: D, bên trái: L, bên phải: R), số thứ tự hàng hoặc cột $X$ ($1 \leq X \leq N$), và loại năng lực tâm linh (push cho đẩy, pull cho kéo), cách nhau bởi dấu cách.
Nếu không thể hoàn thành chiếc bánh bằng cách sử dụng năng lực tâm linh không quá $2N^2$ lần, hãy in ra -1 ở dòng đầu tiên.
Ví dụ
Dữ liệu vào 1
3 2 2 .#. ##. ...
Dữ liệu ra 1
2 U 2 push L 2 push
Dữ liệu vào 2
3 1 2 ... #.# .#.
Dữ liệu ra 2
6 D 2 push D 2 push L 2 push R 2 push U 2 pull U 2 pull
Dữ liệu vào 3
4 1 1 .... .... .... ....
Dữ liệu ra 3
1 L 1 pull