Trong một cuộc thi rô bốt, mỗi đội có hai rô bốt 1 và 2. Sân thi đấu là một hình vuông được chia thành N´N ô vuông đơn vị. Các dòng ô vuông đánh số từ 1 đến N từ trên xuống, các cột ô vuông đánh số từ 1 đến N từ trái. Các ô vuông chia thành hai loại: tự do và cấm. Rô bốt chỉ được di chuyển từ một ô đến ô trống kề cạnh thuộc sân. Mỗi bước di chuyển của rô bốt từ một ô đến ô kề cạnh được thể hiện bởi một trong bốn chữ cái hoa U, D, L, R tương ứng với hướng di chuyển là Lên, Xuống, Trái, Phải. Như vậy hành trình của rô bốt có thể được thể hiện bằng một xâu chỉ gồm các ký tự U, D, L, R. Luật thi như sau:

- Ban đầu, hai rô bốt được đặt vào hai ô tự do khác nhau trên sân. Sau đó, hai rô bốt đồng thời di chuyển. Mỗi bước di chuyển của hai rô bốt đều kéo dài trong một đơn vị thời gian.

- Cần điều khiển hai rô bốt đi theo hành trình sao cho các điều kiện sau được thỏa mãn:

+ Hành trình của mỗi rô bốt gồm các ô khác nhau.

+ Ô cuối cùng của hai hành trình trùng nhau.

+ Độ dài của hai hành trình (số ô trên hành trình) của hai rô bốt là bằng nhau và nhỏ nhất có thể được.

Dữ liệu vào:

- Dòng thứ nhất ghi số N, M (1 ≤ N ≤ 200) là kích thước bảng và số lượng các vật cản.

- Dòng thứ hai ghi hai số U, V là chỉ số dòng và chỉ số cột của ô ban đầu của rô bốt 1.

- Dòng thứ ba ghi hai số X, Y là chỉ số dòng và chỉ số cột của ô ban đầu của rô bốt 2.

- M dòng tiếp theo, mỗi dòng ghi hai số Z, T với ý nghĩa ô (Z, T) là ô cấm.

Kết quả ra:

- Dòng thứ nhất ghi xâu thể hiện hành trình của rô bốt 1.

- Dòng thứ hai ghi xâu thể hiện hành trình của rô bốt 2.