Marisa 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 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?

Dữ liệu

• 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)~.

Kết quả

• 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'.

Subtask

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

Sample Input

3
5 4 4

Sample Output

TNN