Spiderman's Workout

Staying fit is important for every super hero, and Spiderman is no exception. Every day he undertakes a climbing exercise in which he climbs a certain distance, rests for a minute, then climbs again, rests again, and so on. The exercise is described by a sequence of distances $d_1, d_2,\ldots , d_ m$ telling how many meters he is to climb before the first first break, before the second break, and so on. From an exercise perspective it does not really matter if he climbs up or down at the $i$:th climbing stage, but it is practical to sometimes climb up and sometimes climb down so that he both starts and finishes at street level. Obviously, he can never be below street level. Also, he would like to use as low a building as possible (he does not like to admit it, but he is actually afraid of heights). The building must be at least 2 meters higher than the highest point his feet reach during the workout.




The first line of the input contains an integer $N$ giving the number of test scenarios, $1 \le N \le 101$. The following $2N$ lines specify the test scenarios, two lines per scenario: the first line gives a positive integer $M \leq 40$ which is the number of distances, and the following line contains the $M$ positive integer distances. For any scenario, the total distance climbed (the sum of the distances in that scenario) is at most 1000.


For each input scenario a single line should be output. This line should either be the string “IMPOSSIBLE” if no legal solution exists, or it should be a string of length $M$ containing only the characters “U” and “D”, where the $i$:th character indicates if Spiderman should climb up or down at the $i$:th stage. If there are several different legal and optimal solutions, output one of them (it does not matter which one as long as it is optimal).

Sample Input 1 Sample Output 1
20 20 20 20
3 2 5 3 1 2
3 4 2 1 6 4 5