Bài tập của Người Nhện (Spiderman's Workout)

Nguồn: Kattis

Phiên bản: Phước Hưng OJ Extended

Đề bài

Có $M$ chặng với độ dài $d_1,\ldots,d_M$. Ở mỗi chặng phải đi lên hoặc đi xuống đúng $d_i$ mét, bắt đầu và kết thúc ở độ cao 0, không bao giờ xuống dưới 0. Trong các lịch hợp lệ, hãy tối thiểu hóa độ cao lớn nhất đạt tới và in một chuỗi U/D mô tả một lịch tối ưu. Nếu không tồn tại, in IMPOSSIBLE.

Input

Dòng 1 chứa $M$. Dòng 2 chứa $M$ số nguyên dương $d_1,\ldots,d_M$.

Output

In một chuỗi tối ưu gồm U và D, hoặc IMPOSSIBLE nếu không có lịch hợp lệ.

Subtask

• Subtask 1 — 20 điểm: M <= 12; sum(d_i) <= 100. Mức này dành cho cách trực tiếp hoặc đệ quy nhỏ.
• Subtask 2 — 30 điểm: M <= 25; sum(d_i) <= 500. Mức này yêu cầu nhận ra trạng thái DP và loại bỏ tính toán lặp.
• Subtask 3 — 50 điểm: 1 <= M <= 40; d_i > 0; sum(d_i) <= 1000. Đây là toàn bộ giới hạn của bài.

Ví dụ

Input

4
20 20 20 20

Output

UDUD

Giải thích

UDUD lần lượt tạo các độ cao $20,0,20,0$, nên độ cao lớn nhất là 20 và là tối ưu.