Giữ thân hình cân đối là rất quan trọng đối với những siêu anh hùng, người nhện siêu đẳng của chúng ta cũng vậy. Hàng ngày, anh ta tập thể dục bằng cách leo trèo trên một tòa nhà cao tầng. Anh ta sẽ leo lên một độ cao nhất định, rồi nghỉ một chút, rồi leo tiếp, rồi lại nghỉ, ... Để mô tả trực quan cách tập thể dục của người nhện, ta sẽ dùng một dãy số ~d_1, d_2, d_3, \dots , d_n~, giá trị ~d_i~ cho biết người nhện leo được bao nhiêu mét trong lần leo thứ ~i~ của anh ta.

Việc leo lên hay xuống ~d_i~ mét bình thường sẽ không quan trọng. Tuy nhiên, ở thực tế anh ta cần phải tìm cách leo lên và xuống một cách hợp lí sao cho anh đều bắt đầu và kết thúc buổi tập ở mặt đường, tức độ cao ~0~. Dĩ nhiên, người nhện không thể ở độ cao ~< 0~ (ở phía dưới mặt đường). Hơn nữa, người nhện muốn độ cao cao nhất mà anh ta leo đến trong ~n~ lần leo phải nhỏ nhất (hơi khó nói nhưng thật ra anh ta sợ độ cao).

Người nhện muốn bạn giúp anh ấy quyết định xem khi nào sẽ leo lên, khi nào sẽ leo xuống, sao cho:

• Người nhện bắt đầu và kết thúc buổi tập ở độ cao ~0~ (mặt đường).
• Người nhện không được ở độ cao ~< 0~ (ở dưới mặt đường).
• Trong các phương án thỏa mãn hai điều kiện trên, tìm phương án có độ cao tối đa là nhỏ nhất (Bạn được ~70\%~ điểm cho mỗi test nếu đáp án của bạn thỏa hai điều kiện trên nhưng không thỏa điều kiện này).

Dữ liệu vào

• Dòng đầu tiên chứa số nguyên ~n~ - số lần leo của người nhện.
• Dòng thứ hai chứa ~n~ số nguyên dương ~d_1, d_2, d_3, \dots, d_n~ - khoảng cách trong các lần leo của người nhện. Dữ liệu vào đảm bảo tổng các khoảng cách ~D = d_1+d_2+ \dots + d_n \le 2000~.

Dữ liệu ra

• Nếu người nhện không có cách leo thỏa mãn điều kiện, in ra IMPOSSIBLE.
• Ngược lại, in ra một chuỗi độ dài ~n~ chỉ chứa kí tự U và D mô tả cách leo của người nhện. Kí tự thứ ~i~ là U nếu ở người nhện leo lên ở lần leo thứ ~i~, là D nếu người nhện leo xuống ở lần leo thứ ~i~. Nếu tồn tại nhiều đáp án tối ưu, hãy in ra một đáp án tối ưu bất kì.

Giới hạn

• ~50\%~ số điểm đầu tiên có ~1 \le n \le 16~.
• ~50\%~ số điểm còn lại có ~17 \le n \le 100~.
• Bạn được ~70\%~ số điểm cho mỗi test nếu tìm được phương án hợp lệ nhưng không tối ưu.

Ví dụ 1

Dữ liệu vào

4
20 20 20 20

Dữ liệu ra

UDUD

Giải thích

• Người nhện có thể leo (lên, lên, xuống, xuống) hoặc (lên, xuống, lên, xuống). Hai phương án này đều hợp lệ, tuy nhiên phương án thứ hai có độ cao tối đa là ~20~ (tối ưu nhất), còn phương án đầu tiên có độ cao tối đa là ~40~.
• Nếu bạn in ra phương án ~1~, bạn được ~70\%~ điểm của test. Nếu bạn in ra phương án ~2~, bạn được ~100\%~ số điểm.
• Phương án (xuống, lên, xuống, lên) không hợp lệ vì thỏa điều kiện đầu tiên nhưng không thỏa điều kiện thứ hai.

Ví dụ 2

Dữ liệu vào

6
3 2 5 3 1 2

Dữ liệu ra

UUDUDD

Giải thích

Một cách leo hợp lệ là (lên, lên, xuống, lên, xuống, xuống).

Ví dụ 3

Dữ liệu vào

7
3 4 2 1 6 4 5

Dữ liệu ra

IMPOSSIBLE

Giải thích

Không tồn tại cách leo hợp lệ, vì vậy ta in ra IMPOSSIBLE.