Вам дана последовательность из \(n\) цифр \(d_1d_2 \dots d_{n}\). Вам нужно раскрасить все цифры в два цвета таким образом, чтобы:
- каждая цифра была покрашена либо в цвет \(1\), либо в цвет \(2\);
- если выписать подряд слева направо все цифры покрашенные в цвет \(1\), а затем следом все цифры, покрашенные в цвет \(2\), то полученная последовательность из \(n\) цифр будет неубывающей (то есть каждая следующая цифра будет больше или равна предыдущей цифры).
Например, для последовательности цифр \(d=914\) единственная корректная раскраска имеет вид \(211\) (в цвет \(1\) покрашены две последние цифры, в цвет \(2\) покрашена первая цифра). Обратите внимание, что \(122\) не соответствует требованиям (результат выписывания \(9\) и следом \(14\) не является неубывающей последовательностью).
Допустимо, что какой-либо из двух цветов не используется вообще. Цифры, покрашенные в один цвет, не обязаны располагаться в последовательности подряд.
Найдите любой из возможных способов раскрасить заданную последовательность цифр требуемым способом или определите, что это невозможно сделать.
Выходные данные
Выведите \(t\) строк — ответы на каждый из наборов входных данных в тесте.
В случае существования решения для набора соответствующая строка вывода должна содержать любую из допустимых раскрасок, записанную в виде строки из \(n\) цифр \(t_1t_2 \dots t_n\) (\(1 \le t_i \le 2\)), где \(t_i\) — это цвет, в который покрашена \(i\)-я цифра. Если допустимых решений несколько, выведите любую из них.
Если решения не существует, то в соответствующая строка вывода должна содержать единственный символ «-» (минус).
Примечание
В первом тестовом наборе \(d=040425524644\). Вывод \(t=121212211211\) является корректным, так как последовательность \(0022444\) (покрашена в \(1\)), сконкатенированная с \(44556\) (покрашена в \(2\)), равна последовательности \(002244444556\), которая является результатом сортировки всех заданных \(n\) цифр.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
12
040425524644
1
0
9
123456789
2
98
3
987
|
121212211211
1
222222222
21
-
|