Trong một trò chơi điện tử mà An đang chơi, An có \(n\) con cá, con cá thứ \(i\) có kích cỡ \(a_i\).

Một con cá có kích cỡ lớn hơn có thể ăn con cá nhỏ hơn. Khi con cá có kích cỡ \(a_i\) ăn con cá có kích cỡ \(a_j\) (\(a_i > a_j\)), con cá 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 cá, có tồn tại cách chơi nào để nó trở thành con cá sống sót cuối cùng hay không.

Input

• Dòng đầu tiên chứa số nguyên \(n\), là số lượng con cá.
• Dòng thứ hai chứa \(n\) số nguyên dương \(a_i\) (\(a_i \le 10^9\)).

Output

• In ra một xâu độ dài \(n\). Kí tự thứ \(i\) là T nếu con cá thứ \(i\) có thể sống sót đến cuối, ngược lại là N.

Scoring

• Subtask \(1\) (\(40\%\) số điểm): \(1 \le n \le 1024\).
• Subtask \(2\) (\(60\%\) số điểm): \(1 \le n \le 5 \cdot 10^5\).

Example

3
5 4 4

TNN