Bajtockie 海以其多种在世界其他水域中罕见的鱼类而闻名。它最出名的是居住在那里的 Bajtockie 鲶鱼，有些个体甚至重达数吨！

Bajtockie 鲶鱼的饮食习惯也非常独特：当冬天来临时，它们只吃水域中的其他鲶鱼！

Algolina 是 Bajtockie 大学的一名博士生，她的研究项目是调查鲶鱼的这种行为。她已经捕获了 Bajtockie 海中的所有鲶鱼，称重后又将它们放回了水中。每条鲶鱼的质量（以克为单位）都是一个正整数。此外，Algolina 观察到，一条鲶鱼只有在比另一条鲶鱼重的情况下才能吃掉它。换句话说，鲶鱼只能以质量严格小于自己的鲶鱼为食。当一条鲶鱼吃掉另一条较小的鲶鱼时，它的质量会增加到两条鲶鱼质量之和，而被吃掉的鲶鱼则会从海中消失。

现在是分析研究结果的时候了。Algolina 想知道，Bajtockie 海中是否可能最终只剩下一条鲶鱼。更准确地说，如果经过上述鲶鱼进食过程后，海中恰好只剩下一条鲶鱼，那么这条鱼就成为了 Bajtockie 海的国王。因此，一个自然而然的问题是：哪些鱼可以成为 Bajtockie 海的国王？

输入格式

输入的第一行包含一个整数 $n$ ($2 \le n \le 500\,000$)，表示 Bajtockie 海中鲶鱼的数量。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^9$)，描述了海中各条鲶鱼的质量，$a_i$ 表示第 $i$ 条鲶鱼的质量（以克为单位）。

输出格式

在唯一的一行输出中，打印一个长度为 $n$ 的字符串；如果第 $i$ 条鲶鱼可以成为 Bajtockie 海的国王，则第 $i$ 个字符应为 T，否则为 N。

样例

输入 1

6
2 7 1 8 2 8

输出 1

NTNTNT

输入 2

3
5 4 4

输出 2

TNN

说明

考虑第一个样例。以下描述展示了一个场景，其中第二条鲶鱼（重 7 克）成为了 Bajtockie 海的国王：

可以证明，第一条鲶鱼（初始质量为 2 克）无法成为国王。

请注意，在第二个样例中，第二条鲶鱼（重 4 克）无法吃掉任何其他鲶鱼，因此它不能成为国王。