Đây là một bài tập interactive!

Một trận động đất đã xảy ra tại nhà khiemkrkt, tuy vậy thì con robot hút bụi của anh ấy vẫn còn sống. Con Robot xuất phát tại một điểm nào đó ở trong mê cung hình chữ nhật ~n \times m~ nhưng chúng ta không biết ở tọa độ nào.

Yêu cầu: Vì không muốn tốn tiền nên anh ấy muốn nhờ bạn lập trình con Robot đi mò đường cho đến khi gặp được ô có lối ra.

Interaction

• Robot gửi thông tin của bốn bức tưởng xung quanh bằng một dãy nhị phân phân gồm ~4~ ký tự thể hiện hướng lên-trái-xuống-phải:
  • 1 nếu bạn có thể đi về hướng đó;
  • 0 nếu ở đó có bức tường.
• Sau đó chọn một trong bốn hướng để di chuyển UP, LEFT, DOWN, RIGHT rồi cứ thế tiếp tục.
• Đến cuối lượt tương tác sẽ xảy ra ~2~ trường hợp:
  • Khi gặp lối ra, robot gửi thông tin OK cho bạn, bạn nhận được verdict AC.
  • Nếu bạn đụng tường, robot sẽ bị hỏng và bạn nhận được verdict WA.

Limitations

• ~2 \le n, m \le 100~
• Subtask 1 [~30\%~]: Robot luôn bắt đầu ở vị trí trái trên của bảng và lối ra luôn ở ô phải dưới của bảng.
• Subtask 2 [~70\%~]: Không có giới hạn gì thêm.

Sample Series Of Interactions

Explanation

Hình 1. Mô phỏng trực quan / Giải thích cho ví dụ