LIS ngắn nhất và dài nhất

Cho một xâu $s$ độ dài $n-1$ chỉ gồm các ký tự < và >. Xâu này mô tả quan hệ giữa các phần tử liên tiếp của một dãy $a_1,a_2,\dots ,a_n$:

• Nếu $s_i$ là < thì $a_i<a_{i+1}$.
• Nếu $s_i$ là > thì $a_i>a_{i+1}$.

Hãy tìm hai dãy, mỗi dãy là một hoán vị của $1,2,\dots ,n$ và đều thỏa mãn mọi quan hệ mà $s$ mô tả, sao cho:

• Dãy thứ nhất có độ dài dãy con tăng dài nhất (LIS) nhỏ nhất có thể.
• Dãy thứ hai có độ dài dãy con tăng dài nhất lớn nhất có thể.

Hai dãy không nhất thiết phải khác nhau. Nếu có nhiều đáp án, in ra một đáp án bất kỳ. Luôn tồn tại ít nhất một đáp án.

Dữ liệu vào

• Dòng đầu chứa số nguyên $t$ là số lượng bộ dữ liệu.
• Mỗi bộ dữ liệu nằm trên một dòng, gồm số nguyên $n$ và xâu $s$ độ dài $n-1$, cách nhau bởi một dấu cách.

Dữ liệu ra

Với mỗi bộ dữ liệu, in ra hai dòng, mỗi dòng gồm $n$ số nguyên. Dòng thứ nhất là dãy có LIS nhỏ nhất, dòng thứ hai là dãy có LIS lớn nhất.

Ràng buộc

• $1\le t\le {10}^4$
• $2\le n\le 2·{10}^5$
• Xâu $s$ chỉ gồm các ký tự < và >, độ dài đúng bằng $n-1$.
• Tổng của tất cả $n$ trong một file dữ liệu không vượt quá $2·{10}^5$.

Ví dụ