描述

保持健康对每个超级英雄都很重要，蜘蛛侠也不例外。他每天都会进行一次攀岩练习，爬到高楼的一定高度，休息一分钟，然后再爬，再休息，依此类推。该练习由一系列高度 $d1、d2、d3、... 、dm$ 描述他在第一次休息之前、第二次休息之前要爬多少米，依此类推。从锻炼的角度来看，他在第 $i$ 个攀岩阶段是爬上还是爬下并不重要，但有时爬上有时爬下是实际的，这样他既在街道上开始又结束。显然，他永远不可能低于街道水平！此外，他想爬得越短越好（他不愿意承认，但他实际上是恐高的）。建筑物必须比他的脚在锻炼期间到达的最高点至少高 $2$ 米。

他希望你帮忙决定他什么时候应该上去，什么时候应该下楼。答案必须是合法的：它必须在街道水平（离地面 $0$ 米）开始和结束，并且它永远不会低于街道水平。在法律解决方案中，他希望有一个能够将所需建筑高度降至最低的解决方案。在寻找解决方案时，您不得对距离进行重新排序。

如果距离是 $20$ $20$ $20$ $20$，他可以向上、向上、向下、向下或向上、向下、向上、向下。两者都是合法的，但第二个更好（实际上是最佳），因为它只需要高度为 $22$ 的建筑物，而第一个需要高度为 $42$ 的建筑物。如果距离是 $3$ $2$ $5$ $3$ $1$ $2$，则最佳合法解决方案是向上、向上、向下、向上、向下、向下。请注意，对于某些距离序列，根本没有合法的解决方案（例如，对于 $3$ $4$ $2$ $1$ $6$ $4$ $5$）。

输入

输入的第一行包含一个整数 $N$，给出测试用例的数量。以下 $2N$ 行指定测试用例，每个测试用例两行：第一行给出一个正整数 $M$，即高度数，接下来的行包含 $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