Robot và Đường đi Ngắn nhất

Một con robot di chuyển trên một bàn cờ vuông vô hạn, trong đó mỗi ô có thể trống hoặc chứa vật cản. Robot không bao giờ đi vào ô có vật cản. Trong một bước, robot di chuyển sang một ô kề cạnh (4 hướng).

Robot đã ghi lại toàn bộ lộ trình của mình bằng một chuỗi gồm các ký tự L, R, U, D tương ứng với di chuyển sang trái, phải, lên trên và xuống dưới.

Hãy xác định xem có tồn tại hay không một bản đồ (cách bố trí vật cản và chọn ô xuất phát) sao cho lộ trình đã ghi là một đường đi ngắn nhất từ ô xuất phát đến ô kết thúc trên bản đồ đó. Ô xuất phát phải là ô trống, và robot không được đi vào ô có vật cản trong suốt lộ trình.

In ra OK nếu có một bản đồ như vậy, ngược lại in ra BUG.

Dữ liệu vào

Một dòng duy nhất chứa chuỗi $s$ gồm các ký tự thuộc tập $\{L,R,U,D\}$, mô tả lộ trình của robot.

Dữ liệu ra

In ra OK nếu tồn tại một bản đồ hợp lệ để lộ trình là đường đi ngắn nhất, ngược lại in ra BUG.

Ràng buộc

• $1\le |s|\le 100$
• $s$ chỉ chứa các ký tự L, R, U, D.

Ví dụ