D. Короткая и длинная НВП
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Гильдон недавно научился искать Наибольшую Возрастающую Подпоследовательность (НВП) за $$$O(n\log{n})$$$ для последовательности длины $$$n$$$. Он решил проверить себя, может ли он реализовать этот алгоритм корректно, но он не смог найти эту задачу ни в одном архиве (ни смотря на то, что на самом деле, она есть во многих). Так что вместо этого он решил загадать вам загадку на построение последовательности из $$$n$$$ различных целых чисел от $$$1$$$ до $$$n$$$, включительно, чтобы протестировать своим кодом ваш ответ.

Опишем загадку.

Гильдонг дает вам строку длины $$$n-1$$$, состоящую только из символов '<' и '>'. $$$i$$$-й (в 1-индексации) символ это результат сравнения $$$i$$$-го и $$$i+1$$$-го элемента последовательности. Если $$$i$$$-й символ строки это '<', тогда $$$i$$$-й элемент последовательности меньше чем $$$i+1$$$-й. Иначе, $$$i$$$-й символ строки '>', и $$$i$$$-й элемент последовательности больше чем $$$i+1$$$-й элемент.

Он просит вас найти два возможные последовательности (не обязательно различных) состоящих из $$$n$$$ различных целых чисел от $$$1$$$ до $$$n$$$, включительно, что обе последовательности удовлетворяют всем результатам сравнения, и длина НВП первой последовательности минимально возможная, а длина НВП второй последовательности максимально возможная.

Входные данные

Каждый тест состоит из одного или более тестовых случаев. В первой строке записано количество тестовых случаев $$$t$$$ ($$$1 \le t \le 10^4$$$).

Каждый тестовый случай состоит из ровно одной строки, состоящей из целого числа и строки, состоящей только из символов '<' и '>'. Целое число это $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$), длина перестановки, которую вам нужно найти. Строка это результаты сравнений, описанных в условии. Длина строки равна $$$n-1$$$.

Гарантируется, что сумма $$$n$$$ по всем тестовым случаям не превосходит $$$2 \cdot 10^5$$$.

Выходные данные

Для каждого тестового случая, выведите две строки, по $$$n$$$ целых чисел в каждой. Первая строка должна содержать последовательность с минимальной НВП, а вторая строка последовательность с максимальным НВП. Если есть несколько возможных ответов, вы можете вывести любой. Каждая последовательность должна содержать все целые числа от $$$1$$$ до $$$n$$$, включительно, и должна удовлетворять всем результатам сравнения.

Можно показать, что всегда найдется хотя бы один ответ.

Пример
Входные данные
3
3 <<
7 >><>><
5 >>><
Выходные данные
1 2 3
1 2 3
5 4 3 7 2 1 6
4 3 1 7 5 2 6
4 3 2 1 5
5 4 2 1 3
Примечание

В первом тестовом случае, $$$1$$$ $$$2$$$ $$$3$$$ это единственный возможный ответ.

Во втором тестовом случае, наименьшая длина НВП это $$$2$$$, а наибольшая это $$$3$$$. Для примера с наибольшей НВП, $$$4$$$ '$$$3$$$' $$$1$$$ $$$7$$$ '$$$5$$$' $$$2$$$ '$$$6$$$'может быть одной из возможных НВП.