Spiderman's Workout

Source: Kattis

Version: Phuoc Hung OJ Extended

Problem Statement

There are $M$ stages with distances $d_1,\ldots,d_M$. At each stage move up or down exactly $d_i$ meters. Start and finish at height 0 and never go below 0. Among legal schedules, minimize the maximum height reached and output one optimal U/D string. Print IMPOSSIBLE if none exists.

Input

Line 1 contains $M$. Line 2 contains $M$ positive integers $d_1,\ldots,d_M$.

Output

Print an optimal string of U and D, or IMPOSSIBLE if no legal schedule exists.

Subtasks

• Subtask 1 — 20 points: M <= 12; sum(d_i) <= 100.
• Subtask 2 — 30 points: M <= 25; sum(d_i) <= 500.
• Subtask 3 — 50 points: 1 <= M <= 40; d_i > 0; sum(d_i) <= 1000.

Examples

Input

4
20 20 20 20

Output

UDUD

Explanation

UDUD gives heights $20,0,20,0$, so the maximum reached height is 20, which is optimal.