给你一个 $$$n$$$ 数字 $$$d_1d_2 \dots d_{n}$$$ 的序列。您需要用两种颜色绘制所有数字,以便:
- 每个数字都用 $$$1$$$ 颜色或 $$$2$$$ 颜色绘制;
- 如果从左到右将所有数字涂成 $$$1$$$ 颜色,然后将所有数字涂成 $$$2$$$ 颜色,则所得的 $$$n$$$ 数字序列将是非递减的(即,每个下一个数字将大于或等于前一个数字)。
例如,对于序列 $$$d=914$$$,唯一有效的颜色是 $$$211$$$(用颜色 $$$1$$$ 绘制最后两位数字,用颜色 $$$2$$$ 绘制第一个数字)。但 $$$122$$$ 不是有效的着色($$$9$$$ 与 $$$14$$$ 连接不是非递减序列)。
允许根本不使用两种颜色中的任何一种。用相同颜色绘制的数字不需要具有连续的位置。
找到任何有效的方法来绘制给定的数字序列或确定这是不可能的。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10000$$$) — 输入中测试用例的数量。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 2\cdot10^5$$$) — 给定数字序列的长度。
下一行包含 $$$n$$$ 数字序列 $$$d_1d_2 \dots d_{n}$$$ ($$$0 \le d_i \le 9$$$)。数字连续写入,没有空格或任何其他分隔符。该序列可以从 0 开始。
保证输入中所有测试用例的$$$n$$$的值之和不超过$$$2\cdot10^5$$$。
输出
打印 $$$t$$$ 行 — 输入中每个测试用例的答案。
如果测试用例有解决方案,则相应的输出行应包含以 $$$n$$$ 数字 $$$t_1t_2 \dots t_n$$$ ($$$1 \le t_i \le 2$$$) 字符串形式编写的任何有效颜色,其中 $$$t_i$$$ 是第 $$$i$$$ 位数字所绘制的颜色。如果有有几个可行的解决方案,打印其中任何一个。
如果没有解决方案,则相应的输出行应包含单个字符“-”(减号)。
示例
输入 #1
5 12 040425524644 1 0 9 123456789 2 98 3 987
输出 #1
121212211211 1 222222222 21 -
注意
在第一个测试用例中,$$$d=040425524644$$$。输出 $$$t=121212211211$$$ 是正确的,因为 $$$0022444$$$(用 $$$1$$$ 绘制)与 $$$44556$$$(用 $$$2$$$ 绘制)连接起来是 $$$002244444556$$$,它是 $$$n$$$ 给定数字的排序序列。