Gildong recently learned how to find the longest increasing subsequence (LIS) in $O(n\log{n})$ time for a sequence of length $n$. He wants to test himself if he can implement it correctly, but he couldn't find any online judges that would do it (even though there are actually many of them). So instead he's going to make a quiz for you about making permutations of $n$ distinct integers between $1$ and $n$, inclusive, to test his code with your output.

The quiz is as follows.

Gildong provides a string of length $n-1$, consisting of characters '<' and '>' only. The $i$-th (1-indexed) character is the comparison result between the $i$-th element and the $i+1$-st element of the sequence. If the $i$-th character of the string is '<', then the $i$-th element of the sequence is less than the $i+1$-st element. If the $i$-th character of the string is '>', then the $i$-th element of the sequence is greater than the $i+1$-st element.

He wants you to find two possible sequences (not necessarily distinct) consisting of $n$ distinct integers between $1$ and $n$, inclusive, each satisfying the comparison results, where the length of the LIS of the first sequence is minimum possible, and the length of the LIS of the second sequence is maximum possible.


-----Input-----

Each test contains one or more test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$).

Each test case contains exactly one line, consisting of an integer and a string consisting of characters '<' and '>' only. The integer is $n$ ($2 \le n \le 2 \cdot 10^5$), the length of the permutation you need to find. The string is the comparison results explained in the description. The length of the string is $n-1$.

It is guaranteed that the sum of all $n$ in all test cases doesn't exceed $2 \cdot 10^5$.


-----Output-----

For each test case, print two lines with $n$ integers each. The first line is the sequence with the minimum length of the LIS, and the second line is the sequence with the maximum length of the LIS. If there are multiple answers, print any one of them. Each sequence should contain all integers between $1$ and $n$, inclusive, and should satisfy the comparison results.

It can be shown that at least one answer always exists.


-----Example-----
Input
3
3 <<
7 >><>><
5 >>><

Output
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



-----Note-----

In the first case, $1$ $2$ $3$ is the only possible answer.

In the second case, the shortest length of the LIS is $2$, and the longest length of the LIS is $3$. In the example of the maximum LIS sequence, $4$ '$3$' $1$ $7$ '$5$' $2$ '$6$' can be one of the possible LIS.

Difficulty: interview

Starter code:

Solutions:
import sys
input = sys.stdin.readline


def compress(array):
    array2 = sorted(set(array))
    memo = {value : index for index, value in enumerate(array2)}
    for i in range(len(array)):
        array[i] = memo[array[i]] + 1
    return array


t = int(input())
base = 10 ** 6
for _ in range(t):
    n, b = list(map(str, input().split()))
    n = int(n)
    ans = [0] * n
    
    now = base
    ans[0] = base
    for i in range(n - 1):
        if b[i] == ">":
            now -= base
            ans[i + 1] = now
        else:
            now += 1
            ans[i + 1] = now
    print(*compress(ans))

    now = base
    ans[0] = base
    for i in range(n - 1):
        if b[i] == ">":
            now -= 1
            ans[i + 1] = now
        else:
            now += base
            ans[i + 1] = now
    print(*compress(ans))


def main():
    import sys
    input = sys.stdin.readline

    for _ in range(int(input())):
        line = list(input().split())
        N = int(line[0])
        S = line[1]

        inc_num = S.count('<')
        ans = [0] * N
        inc = N
        dec = N - inc_num
        for i in range(N - 1):
            if ans[i+1]:
                continue
            if S[i] == '<':
                j = i+1
                cnt = 1
                while True:
                    if j == N-1:
                        break
                    if S[j] == '<':
                       cnt += 1
                    else:
                        break
                    j += 1
                #print(cnt)
                for j in range(i+cnt-1, i-1, -1):
                    #print(j)
                    ans[j+1] = inc
                    inc -= 1
        for i in range(N):
            if ans[i] == 0:
                ans[i] = dec
                dec -= 1
        print(*ans)

        ans = [0] * N
        inc = N - inc_num + 1
        dec = N - inc_num
        for i in range(N - 1):
            if S[i] == '<':
                ans[i + 1] = inc
                inc += 1
        for i in range(N):
            if ans[i] == 0:
                ans[i] = dec
                dec -= 1
        print(*ans)


def __starting_point():
    main()

__starting_point()

from sys import stdin,stderr
def rl():
    return [int(w) for w in stdin.readline().split()]

def p1(n, s, le):
    r = []
    b = i = 0
    while i < n:
        try:
            ni = s.index(le, i) + 1
        except ValueError:
            ni = n
        r += list(range(ni, i, -1))
        i = ni
    return r

t, = rl()
for _ in range(t):
    n,s = stdin.readline().split()
    n = int(n)
    print(*(n - x + 1 for x in p1(n, s, '>')))
    print(*p1(n, s, '<'))


import sys

Q = int(sys.stdin.readline().strip())
for q in range (0, Q):
    n, s = sys.stdin.readline().strip().split()
    n = int(n)
    U = [1]
    D = [1]
    for i in range (0, n-1):
        if s[i] == "<":
            U[-1] = U[-1] + 1
            D.append(1)
        else:
            D[-1] = D[-1] + 1
            U.append(1)
    m = n
    i = 0
    A = []
    while m > 0:
        for j in range (0, U[i]):
            A.append(str(m-U[i]+j+1))
        m = m - U[i]
        i = i + 1
    print(" ".join(A))
    m = 0
    i = 0
    A = []
    while i < len(D):
        for j in range (0, D[i]):
            A.append(str(m+D[i]-j))
        m = m + D[i]
        i = i + 1
    print(" ".join(A))



def makeRepeat(s):
    repeat = [[s[0], 0]]
    for ch in s:
        if ch == repeat[-1][0]:
            repeat[-1][1] += 1
        else:
            repeat.append([ch, 1])
    return repeat


def solve(N, S):
    assert len(S) == N - 1
    curr = 0
    repeat = makeRepeat(S)
    longest = list(range(1, N + 1))
    shortest = list(reversed(list(range(1, N + 1))))
    for ch, count in repeat:
        if ch == ">":
            longest[curr : curr + count + 1] = reversed(
                longest[curr : curr + count + 1]
            )
        else:
            assert ch == "<"
            shortest[curr : curr + count + 1] = reversed(
                shortest[curr : curr + count + 1]
            )
        curr += count

    # print(" " + " ".join(S))
    return " ".join(map(str, shortest)) + "\n" + " ".join(map(str, longest))


def __starting_point():
    T, = list(map(int, input().split()))
    for t in range(T):
        N, S = input().split()
        N = int(N)
        ans = solve(N, S)
        print(ans)

__starting_point()

def solve1(n, comps):
    ans = []
    rng = iter(list(range(1, n + 1)))
    for comp in [len(comp) + 1 for comp in comps.split(">")][::-1]:
        ans.append([ansi for (_, ansi) in zip(list(range(comp)), rng)])
    fin_ans = []
    ans.reverse()
    for ansi in ans:
        fin_ans.extend(ansi)
    return fin_ans


def solve2(n, comps):
    ans = []
    rng = iter(list(range(1, n + 1)))
    for comp in [len(comp) + 1 for comp in comps.split("<")]:
        ans.extend([ansi for (_, ansi) in zip(list(range(comp)), rng)][::-1])
    return ans


def main():
    for _ in range(int(input())):
        n, comps = input().split()
        n = int(n)
        print(*solve1(n, comps))
        print(*solve2(n, comps))


main()


import sys
input = sys.stdin.readline

T = int(input())
for _ in range(T):
    n, S = input().split()
    n = int(n)
    max_ans = [0] * n
    i = j = 0
    cur = 1
    for s in S + '<':
        if s == '>':
            j += 1
        elif s == '<':
            for k in range(j, i - 1, -1):
                max_ans[k] = cur
                cur += 1
            j += 1
            i = j


    min_ans = [0] * n
    i = j = 0
    cur = 1
    for s in S[::-1] + '>':
        if s == '<':
            j += 1
        elif s == '>':
            for k in range(j, i - 1, -1):
                min_ans[k] = cur
                cur += 1
            j += 1
            i = j
    print(*min_ans[::-1])
    print(*max_ans)



def getInput():
	line = input().split()
	return int(line[0]), line[1]

def sLIS(n, s):
	ans = list(range(n, 0, -1))
	
	rev = []
	i = 0
	while i < n-1:
		if s[i] == '<':
			j = i+1
			while j < n-1 and s[j] == '<':
				j += 1
			
			rev.append((i, j))
			i = j+1
		else:
			i += 1

	for r in rev:
		i, j = r
		while i <= j:
			ans[i], ans[j] = ans[j], ans[i]
			i += 1
			j -= 1
	
	return ans

def lLIS(n, s):
	ans = list(range(1, n+1))
	
	rev = []
	i = 0
	while i < n-1:
		if s[i] == '>':
			j = i+1
			while j < n-1 and s[j] == '>':
				j += 1
			
			rev.append((i, j))
			i = j+1
		else:
			i += 1

	for r in rev:
		i, j = r
		while i <= j:
			ans[i], ans[j] = ans[j], ans[i]
			i += 1
			j -= 1
	
	return ans

for _ in range(int(input())):
	n, s = getInput()

	"""
		p = []
		c = +1 if s[0] == '<' else -1
		for e in s[1:]:
			if c > 0 and e == '>':
				p.append(c)
				c = -1
			elif c < 0 and e == '<':
				p.append(c)
				c = +1
			else:
				c += +1 if e == '<' else -1
		p.append(c)
	"""
	print(*sLIS(n, s))
	print(*lLIS(n, s))


Q = int(input())


total = []
for _ in range(Q):
    n, s = input().split()
    n=int(n)

    seq = []
    curlen = 1
    for i in range(len(s)):
        if s[i]=='<':
            curlen+=1
        else:
            seq.append(curlen)
            curlen=1
    seq.append(curlen)
    curr = n
    ans =[]
    for sq in seq:
        ans.extend(range(curr-sq+1,curr+1))
        curr-=sq
    total.append(' '.join(map(str,ans)))

    curr = n
    ans = ['']*n
    for i in range(len(s)-1,-1,-1):
        if s[i]=='<':
            ans[i+1]=str(curr)
            curr-=1
    for i in range(n):
        if not ans[i]:
            ans[i]=str(curr)
            curr-=1
    total.append(' '.join(ans))


print(*total, sep='\n')