C. Раскрашивание цифр
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дана последовательность из $$$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$$$-я цифра. Если допустимых решений несколько, выведите любую из них.

Если решения не существует, то в соответствующая строка вывода должна содержать единственный символ «-» (минус).

Пример
Входные данные
5
12
040425524644
1
0
9
123456789
2
98
3
987
Выходные данные
121212211211
1
222222222
21
-
Примечание

В первом тестовом наборе $$$d=040425524644$$$. Вывод $$$t=121212211211$$$ является корректным, так как последовательность $$$0022444$$$ (покрашена в $$$1$$$), сконкатенированная с $$$44556$$$ (покрашена в $$$2$$$), равна последовательности $$$002244444556$$$, которая является результатом сортировки всех заданных $$$n$$$ цифр.