Minh đang chơi Roller - một trò chơi nhỏ bên trong trò Fancade. Trò chơi như sau: Cho một nhân vật có dạng một khối hình 3D kích thước \(1 \times 2 \times 1\) nằm trong một bảng hình chữ nhật. Cần phải tìm cách di chuyển nhân vật này bằng cách lật, hoặc lăn nó, sao cho mọi ô trong hình chữ nhật đều được "tô điểm với nhiều sắc màu rực rỡ" bằng cách được đi qua ít nhất một lần.

Là một người yêu thích Tin học, Minh đã nhận ra đây là một bài toán có thể lập trình được. Cậu phát biểu lại nó như sau:
Có một bảng hình chữ nhật kích thước \(n\times m\), tức gồm \(n\) dòng và \(m\) cột. Các hàng của bảng được đánh số từ \(1\) tới \(n\) theo thứ tự từ trên xuống. Các cột được đánh số từ \(1\) tới \(m\) theo thứ tự từ trái sang. Cho khối 3D kích thước \(1 \times 2 \times 1\) ban đầu nằm trên ô \((x, y)\) của bảng này (ô ở dòng \(x\), cột \(y\)). Bảng này có \(k\) ô cấm, không đi vào được. Có thể di chuyển khối này theo phép lật/lăn trong không gian \(3\) chiều, theo \(4\) hướng: trên (U), dưới (D), trái (L), phải (R) (lưu ý các hướng này mang tính tương đối, khi ta giả sử đang nhìn từ trên xuống và đối diện với bảng hình chữ nhật hai chiều). Xem minh họa qua hình sau:

Trong mọi thời điểm, khối hình này không được nằm lên các ô cấm. Ngoài ra, toàn bộ khối hình phải nằm trọn vẹn trong bảng hình chữ nhật. Các ô được nằm lên sẽ được đánh dấu. Hỏi có thể đánh dấu được tất cả mọi ô (trừ ô cấm) hay không với giới hạn số nước đi là \(L\)?

Minh chỉ muốn tận hưởng thành quả - chương trình giải trò chơi tự động chứ không muốn trải qua công đoạn lập trình vất vả. Bạn ấy nhờ các thí sinh của LQDOJ CUP 2023 trợ giúp. Các bạn hãy giải quyết bài toán trên nhé.

Yêu cầu: Cho biết kích thước bảng, vị trí các ô cấm, vị trí ban đầu của khối hình. Hãy in ra một chuỗi các nước đi tương ứng. Nếu không tồn tại cách để đánh dấu toàn bộ ô (trừ ô cấm), hoặc không tồn tại chuỗi các bước đi dài không quá \(L\) bước thỏa mãn, in ra -1.

Input

• Dòng đầu tiên chứa bốn số nguyên \(n, m, k, L\) (\(1 \leq n, m \leq 500, 0 \leq k \leq n \times m, 1 \leq L \leq 15 \times 10^5\)) lần lượt là kích thước của bảng hình chữ nhật, số ô cấm và giới hạn số nước đi.
• Dòng tiếp theo chứa ba số nguyên \(x_0, y_0, d\) (\(1 \leq x_0 \leq n, 1 \leq y_0 \leq m\)) với ý nghĩa: tọa độ ban đầu của ô nằm ở phía trên cùng bên trái tiếp xúc với bảng hình chữ nhật của khối hình là \((x_0, y_0)\), còn \(d \in \{0, 1, 2\}\) tương ứng với hướng của khối hình: \(0\): hướng lên (\(1 \times 1\)), \(1\): nằm sang phải (\(1 \times 2\)), \(2\): nằm xuống dưới (\(2 \times 1\)).
• Trong \(k\) dòng tiếp theo, dòng thứ \(i\) chứa hai số nguyên \(x_i\) và \(y_i\) (\(1 \leq x_i \leq n, 1 \leq y_i \leq m\)) thể hiện tọa độ của một ô bị cấm.

Output

• Một dòng duy nhất chứa kết quả. In ra -1 hoặc một xâu chỉ gồm 4 kí tự UDLR tương ứng với các nước đi - lật theo hướng trên/dưới/trái/phải nếu nhìn từ trên xuống (theo bảng hình chữ nhật) (xem hình số 2 để hiểu rõ hơn).
• Có thể có nhiều cách đi hợp lệ khác nhau. Bạn chỉ cần đưa ra một phương án thỏa mãn các ràng buộc của đề bài thì sẽ được tính là đúng.

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(n \times m \leq 20, k = 0, L = 400\) và dữ liệu đảm bảo luôn tồn tại chuỗi nước đi thỏa mãn không quá \(13\) bước.
• Subtask \(2\) (\(30\%\) số điểm): \(n\) chia \(3\) dư \(1\), \((m + 1)\) không chia hết cho \(3\), \(k = 0, L = \left\lfloor \frac{2 \times n \times m}{3} \right \rfloor, x_0 = y_0 = 1, d = 0\).
• Subtask \(3\) (\(20\%\) số điểm): \(n, m \leq 50, L = 15 \times 10^5\).
• Subtask \(4\) (\(30\%\) số điểm): \(L \geq 6 \times n \times m\).

Example

Test 1

Input

3 3 1 54
3 3 0
1 3

Output

LUUDR

Note

Sau đây là ví dụ một chuỗi các nước đi thỏa mãn (tương ứng với xâu LUUDR):

Sau đây là góc nhìn từ trên xuống:

Ô màu đỏ là ô cấm. Ô màu vàng là ô mà khối hình đang nằm đè lên tại thời điểm đang xét (sau một nước đi). Ô màu xanh là những ô đã được đánh dấu trước đó.