Gildong 最近学习了如何在 $$$O(n\log{n})$$$ 时间内找到长度为 $$$n$$$ 的序列的最长递增子序列 (LIS)。他想测试一下自己是否能正确实现,但他找不到任何在线评委可以做到这一点(尽管实际上有很多评委)。因此,他将为您做一个关于在 $$$1$$$ 和 $$$n$$$(含)之间对 $$$n$$$ 不同整数进行排列的测验,以用您的输出测试他的代码。
测验如下。
Gildong 提供了一个长度为$$$n-1$$$ 的字符串,仅包含字符“<”和“>”。第 $$$i$$$(索引为 1)字符是序列中第 $$$i$$$ 元素与第 $$$i+1$$$-st 元素之间的比较结果。如果字符串的第 $$$i$$$ 个字符是“<”,则序列的第 $$$i$$$ 个元素小于 $$$i+1$$$-st 元素。如果字符串的第 $$$i$$$ 个字符是“>”,则序列的第 $$$i$$$ 个元素大于第 $$$i+1$$$ 个元素。
他希望你找到两个可能的序列(不一定不同),由 $$$1$$$ 和 $$$n$$$(含)之间的 $$$n$$$ 不同整数组成,每个序列都满足比较结果,其中第一个序列的 LIS 长度尽可能最小,第二个序列的 LIS 长度尽可能最大。
输入
每个测试包含一个或多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。
每个测试用例仅包含一行,由一个整数和一个仅由字符“<”和“>”组成的字符串组成。整数是 $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$),您需要找到的排列的长度。该字符串是描述中解释的比较结果。字符串的长度为$$$n-1$$$。
保证所有测试用例中所有$$$n$$$的总和不超过$$$2 \cdot 10^5$$$。
输出
对于每个测试用例,打印两行,每行包含 $$$n$$$ 整数。第一行是LIS长度最小的序列,第二行是LIS长度最大的序列。如果有多个答案,请打印其中之一。每个序列应包含 $$$1$$$ 和 $$$n$$$(含)之间的所有整数,并且应满足比较结果。
可以证明,至少有一个答案总是存在。
示例
输入 #1
3 3 << 7 >><>>< 5 >>><
输出 #1
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$$$ 是唯一可能的答案。
在第二种情况下,LIS的最短长度是$$$2$$$,LIS的最长长度是$$$3$$$。在最大 LIS 序列的示例中,$$$4$$$ '$$$3$$$' $$$1$$$ $$$7$$$ '$$$5$$$' $$$2$$$ '$$$6$$$' 可以是可能的 LIS 之一。