Giải bài trực tuyến

LSM là cố vấn cao cấp của HAOI 2008 và được giao nhiệm vụ ra đề thi. Hạn nộp bài đang đến gần mà LSM không có một ý tưởng nào. Thư kí Lola thúc giục ngày đêm cộng thêm khoản tiền bồi thường nếu không hoàn thành công tác đúng hạn làm LSM hết sức lo lắng. Trong lúc tuyệt vọng, LSM vô tình gập đôi liên tiếp tờ tiền 100$ trước mặt. Khi mở tờ tiền ra, trong tay LSM là tờ giấy bạc có các vết gấp lên xuống. Đột nhiên, một ý tưởng lóe sáng: nếu có cách nào đó xác định được nếp gấp thứ p tính từ trái sang phải của tờ tiền tiền là lên hay xuống, thì đây sẽ là một bài toán hay cho các thí sinh của HAOI 2008. Hãy giúp LSM thoát khỏi tình thế khó khăn này nhé!

Tờ tiền có hình dạng chữ nhật và luôn được thực hiện sao cho mép trái được gập đè lên mép phải. LSM thực hiện gấp như vậy f lần. Tuy nhiên trong thực tế, tới một lúc nào đó đồng tiền sẽ không thể gấp được do quá dày, nhưng chúng ta bỏ qua thực tế này và tờ tiền vẫn được gấp đôi chính xác sau f lần.

Dữ liệu

• Gồm nhiều dòng mỗi dòng chứa đúng 2 số nguyên ngăn cách nhau bởi dấu cách f và p tương ứng là số lần gấp tờ tiền và vị trí nếp gấp cần xác định. (1 ≤ f ≤ 31. p thỏa mãn không vượt quá số lượng nếp gấp được tạo ra sau f lần gấp)
• Dữ liệu được kết thúc bởi 2 số 0 và không yêu cầu in ra kết quả cho 2 số này.

Kết quả

Với mỗi dòng tương ứng với dữ liệu vào, in ra một kí tự duy nhất ở mỗi dòng: U cho nếp gấp lên trên và D cho nếp gấp xuống dưới.

Ví dụ

Dữ liệu
2 1
2 2
2 3
0 0	

Kết quả
U
D
D