Bajtazar 送给他的儿子 Bajtek 一副牌。这副牌由 $n$ 张牌组成，编号从 1 到 $n$。

Bajtek 对这份礼物非常高兴。整个晚上他都坐在自己的房间里玩，用这副牌洗牌。经过不断练习，他已经达到了每次洗牌结果都一样的地步，也就是说，在洗牌时，原来在位置 $k$ 的牌（$1 \le k \le n$）每次都会移到位置 $a_{k}$ （当然 $1 \le a_{k} \le n$）。

某一时刻，Bajtek 的爸爸走进房间，说该睡觉了。Bajtek 恳求爸爸在睡觉前再给他演示一次应该如何洗牌。于是 Bajtazar 洗了一次牌，这次原来在位置 $k$ 的牌移到了位置 $b_{k}$ （同样 $1 \le k, b_{k} \le n$）。

Bajtek 惊叹于爸爸洗牌的熟练。他也很想学会！可惜 Bajtek 还小，还不能像爸爸那样洗牌。但他想到一个办法，就是尝试多次重复自己的洗牌方法，看看最终能否得到爸爸洗牌后的排列。

现在小男孩睡不着了，因为他一直在想，这样做是否可能。请你帮帮他！

输入格式

输入的第一行包含一个整数 $n$ （$2 \le n \le 1,000,000$）。第二行和第三行分别描述了排列 $a_{1}, \ldots, a_{n}$ 和 $b_{1}, \ldots, b_{n}$，即 $n$ 个互不相同、取值范围为 1 到 $n$ 的整数。你可以假定这两个排列不相同。

输出格式

输出的唯一一行应为一个单词 TAK 或 NIE，表示是否存在 $k>1$，使得通过重复 $k$ 次 Bajtek 的洗牌方法后，可以得到 Bajtazar 洗牌的结果。

样例

输入

4
2 4 3 1
1 2 3 4

输出

TAK

输入 2

4
1 2 3 4
2 4 3 1

输出 2

NIE