一个铁路侧线由两条（死胡同式）侧轨 1 和 2 组成。侧线由轨道 A 进入，并由轨道 B 离开（见下图）。

轨道 A 上有 $n$ 节车厢，编号为 $1$ 到 $n$。它们的排列顺序使得它们按 $a_1, a_2, \dots, a_n$ 的顺序进入侧线。这些车厢需要被转移到侧线，以便它们按 $1, 2, \dots, n$ 的顺序从轨道 B 离开。每节车厢必须从轨道 A 转移到侧轨 1 或 2 中的某一条一次，随后（可能在剩余车厢进行一些转移操作后）再从该侧轨转移到轨道 B 一次。侧轨足够长，可以容纳最长的列车，因此无需担心其容量限制。

输入格式

第一行包含一个整数 $n$ ($1 \le n \le 100\,000$)，表示需要转移的车厢数量。第二行包含数字 $a_1, a_2, \dots, a_n$，它们是 $1, 2, \dots, n$ 的一个排列（即每个 $a_i$ 都属于 $\{1, 2, \dots, n\}$，且所有数字互不相同），数字之间由空格分隔。

输出格式

如果存在一种转移车厢的方法，使得它们按 $1, 2, \dots, n$ 的顺序进入轨道 B，则第一行输出单词 TAK（波兰语中的“是”），否则输出单词 NIE（波兰语中的“否”）。如果答案为 TAK，则第二行应输出对应的侧轨编号（1 或 2），表示车厢 $a_1, a_2, \dots, a_n$ 依次被移动到的侧轨。如果存在多种转移方式，任选一种即可。

样例

输入 1

4
1 3 4 2

输出 1

TAK
1 1 2 1

输入 2

4
2 3 4 1

输出 2

NIE

说明

在第一个样例中，我们首先将车厢 1 移动到第一条侧轨，并立即将其移动到轨道 B。然后将车厢 3 移动到第一条侧轨，将车厢 4 移动到另一条侧轨。最后，将车厢 2 移动到第一条侧轨，之后车厢 2 和 3 从该侧轨离开进入轨道 B，随后是车厢 4，它从第二条侧轨进入轨道 B。