Godsent có nuôi ~n~ con sâu, con sâu thứ ~i~ có kích cỡ ~a_i~. Một con sâu có kích thước lớn hơn có thể ăn thịt con sâu nhỏ hơn. Nếu con sâu có kích cỡ ~a_i~ ăn thịt con sâu kích cỡ ~a_j~, con sâu lớn hơn sẽ có kích cỡ mới là ~a_i+a_j~. Hãy giúp Godsent xác định xem với mỗi con sâu, có tồn tại trường hợp mà nó có thể trở thành con sâu sống sót cuối cùng không?

Input

• Dòng đầu tiên là số nguyên ~n~, số lượng con sâu.
• Dòng thứ hai gồm n số nguyên dương ~a_i~ (~a_i≤10^9~).

Output

In một xâu độ dài n, vị trí thứ ~i~ là 'T' nếu con sâu thứ ~i~ có thể sống sót đến cuối, ngược lại in ra 'N'.

Sample input

3
5 4 4

Sample output

TNN

Subtask

• Subtask 1 (40% số điểm): ~1 ≤n ≤1024.~
• Subtask 2 (60% số điểm): ~1≤n≤5×10^5.~