给定两个由字母 a 和 b 组成的单词 $u$ 和 $v$。我们的目标是将单词 $u$ 转换成单词 $v$。为此我们可以进行如下的交换操作：选择 $u$ 中两个 $不相交$ 的片段 ab 和 ba，并交换它们的位置。是否可以通过有限次这样的操作，将 $u$ 转换为 $v$？

输入格式

输入的第一行包含一个整数 $n$（$2 \le n \le 1,000,000$），表示单词的长度。接下来的两行每行包含一个由 $n$ 个 a 和/或 b 组成的字符串。第一行描述单词 $u$，第二行描述单词 $v$。你可以假设这两个单词是不同的。

输出格式

输出的第一行应为一个单词 TAK 或 NIE，表示是否可以仅通过交换操作将单词 $u$ 转换为单词 $v$。

如果答案是肯定的，且 $n \le 4,000$，你的程序还应输出一个实现目标的操作序列示例。这个描述的第一行应为一个整数 $m$（$1 \le m \le 1,000,000$），表示操作的次数。接下来的 $m$ 行每行包含两个整数 $a_{i}$、$b_{i}$（$1 \le a_{i}, b_{i} \le n - 1$），分别表示被交换的 ab 片段和 ba 片段的首字母的位置。

如果存在多个可能的方案，你的程序可以输出其中任意一个。特别地，你的方案不必使操作次数 $m$ 最小化。

样例

输入

6
aabbaa
baaaab

输出

TAK
2
2 4
1 5

输入 2

6
aaabbb
ababab

输出 2

NIE