CF1209C.Paint the Digits

You are given a sequence of $n$ digits $d_1d_2 \dots d_{n}$. You need to paint all the digits in two colors so that:

• each digit is painted either in the color $1$ or in the color $2$;
• if you write in a row from left to right all the digits painted in the color $1$, and then after them all the digits painted in the color $2$, then the resulting sequence of $n$ digits will be non-decreasing (that is, each next digit will be greater than or equal to the previous digit).

For example, for the sequence $d=914$ the only valid coloring is $211$ (paint in the color $1$ two last digits, paint in the color $2$ the first digit). But $122$ is not a valid coloring ($9$ concatenated with $14$ is not a non-decreasing sequence).

It is allowed that either of the two colors is not used at all. Digits painted in the same color are not required to have consecutive positions.

Find any of the valid ways to paint the given sequence of digits or determine that it is impossible to do.

给你一个由 $n$ 个数字组成的序列 $d_1d_2 \dots d_{n}$。你需要将所有数字涂上两种颜色之一，使得：

• 每个数字被涂成颜色 $1$ 或颜色 $2$；
• 若将所有涂成颜色 $1$ 的数字从左到右依次写出，紧接着再将所有涂成颜色 $2$ 的数字从左到右依次写出，则得到的 $n$ 位数字序列是非递减的（即每个后续数字均大于或等于前一个数字）。

例如，对于序列 $d=914$，唯一有效的涂色方案是 $211$（将后两个数字涂成颜色 $1$，第一个数字涂成颜色 $2$）。但 $122$ 不是有效方案（将 $9$ 与 $14$ 拼接得到 $914$，该序列不是非递减的）。

允许其中一种颜色完全不使用。涂成同一种颜色的数字不要求位置连续。

请找出任意一种满足条件的涂色方案，或判定该问题无解。

The first line contains a single integer $t$ ($1 \le t \le 10000$) — the number of test cases in the input.

The first line of each test case contains an integer $n$ ($1 \le n \le 2\cdot10^5$) — the length of a given sequence of digits.

The next line contains a sequence of $n$ digits $d_1d_2 \dots d_{n}$ ($0 \le d_i \le 9$). The digits are written in a row without spaces or any other separators. The sequence can start with 0.

It is guaranteed that the sum of the values of $n$ for all test cases in the input does not exceed $2\cdot10^5$.

第一行包含一个整数 $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$。

Print $t$ lines — the answers to each of the test cases in the input.

If there is a solution for a test case, the corresponding output line should contain any of the valid colorings written as a string of $n$ digits $t_1t_2 \dots t_n$ ($1 \le t_i \le 2$), where $t_i$ is the color the $i$-th digit is painted in. If there are several feasible solutions, print any of them.

If there is no solution, then the corresponding output line should contain a single character '-' (the minus sign).

输出 $t$ 行——对应输入中每个测试用例的答案。

若某个测试用例存在解，则对应的输出行应包含任意一个有效的染色方案，表示为一个长度为 $n$ 的数字字符串 $t_1t_2 \dots t_n$（其中 $1 \le t_i \le 2$），$t_i$ 表示第 $i$ 个数字所染的颜色。若存在多个可行解，输出任意一个即可。

若不存在解，则对应的输出行应仅包含一个字符 \-（减号）。

In the first test case, $d=040425524644$. The output $t=121212211211$ is correct because $0022444$ (painted in $1$) concatenated with $44556$ (painted in $2$) is $002244444556$ which is a sorted sequence of $n$ given digits.

在第一个测试用例中，$d=040425524644$。输出 $t=121212211211$ 是正确的，因为将数字 $0022444$（涂成 $1$）与 $44556$（涂成 $2$）拼接得到 $002244444556$，这恰好是给定的 $n$ 个数字的升序排列。