题目描述

保持健康对每位超级英雄都很重要，蜘蛛侠也不例外。每天他都会进行一项攀爬训练：先爬一段距离，休息一分钟，再爬一段距离，再休息，依此类推。训练由一系列距离$d_1, d_2, \ldots, d_m$描述，分别表示他在第一次休息前、第二次休息前……要攀爬的米数。从锻炼的角度来看，他在第$i$次攀爬阶段是向上还是向下并不重要，但为了实际方便，他有时会向上爬，有时会向下爬，以便训练开始和结束时都处于街道水平（地面$0$米处）。显然，他的位置不能低于街道水平。此外，他希望尽可能使用较低的建筑物（他不愿承认，但实际上他恐高）。建筑物的高度必须至少比他训练期间脚部到达的最高点高出$2$米。

他希望你能帮助他决定何时向上爬，何时向下爬。答案必须合法：必须从街道水平开始和结束（地面$0$米处），并且训练过程中不能低于街道水平。在所有合法解中，他想要一个使得所需建筑物高度最小的解。在寻找解时，不能重新排列距离的顺序。

如果距离是$20\ 20\ 20\ 20$，他可以选择向上、向上、向下、向下（UU DD），或者向上、向下、向上、向下（UD UD）。两者都合法，但第二种更优（实际上是最优的），因为它只需要一栋高度为$22$米的建筑物，而第一种需要$42$米。如果距离是$3\ 2\ 5\ 3\ 1\ 2$，一个最优的合法解是向上、向上、向下、向上、向下、向下（UU D U D D）。注意，某些距离序列可能根本没有合法解（例如$3\ 4\ 2\ 1\ 6\ 4\ 5$）。

输入格式

第一行输入一个整数$N$，表示测试用例的数量。接下来的$2N$行描述测试用例，每个用例占两行：第一行是一个正整数$M \leq 40$，表示距离的数量；第二行包含$M$个正整数，表示距离。对于任何用例，攀爬的总距离（该用例中所有距离的总和）不超过$1000$。

输出格式

对于每个测试用例，输出一行。如果没有合法解，输出"IMPOSSIBLE"；否则输出一个长度为$M$的字符串，仅包含字符"U"和"D"，其中第$i$个字符表示蜘蛛侠在第$i$个阶段应该向上还是向下爬。如果有多个合法且最优的解，输出其中任意一个即可（只要是最优解，具体是哪一个无关紧要）。

输入样例 1

3
4
20 20 20 20
6
3 2 5 3 1 2
7
3 4 2 1 6 4 5

输出样例 1

UDUD
UUDUDD
IMPOSSIBLE

题目来源

$2003$年瑞典/挪威编程锦标赛