You are given two words $u$ and $v$ consisting of the letters a and b. Our goal is to transform word $u$ into word $v$. For this purpose, we have the following swap operation available: we choose two $disjoint$ substrings ab and ba in the first word and swap them. Can we transform $u$ into $v$ by performing a finite number of such operations?

Input

The first line of input contains a single integer $n$ ($2 \le n \le 1\,000\,000$), representing the length of the words. Each of the next two lines contains a string consisting of $n$ characters a and/or b. The first line describes word $u$, and the second describes word $v$. You may assume that these words are different.

Output

The first line of the output should contain one word TAK or NIE, indicating whether word $u$ can be transformed into word $v$ using only the swap operations.

If the answer is affirmative $and$ $n \le 4\,000$, your program should also output an example sequence of operations leading to the goal. The first line of this description should contain a single integer $m$ ($1 \le m \le 1\,000\,000$), representing the number of operations. Each of the next $m$ lines should contain two integers $a_{i}$, $b_{i}$ ($1 \le a_{i}, b_{i} \le n - 1$), representing the starting positions of the swapped substrings ab (at $a_{i}$) and ba (at $b_{i}$).

If there are multiple possible solutions, your program should output any one of them. In particular, your solution does not need to minimize the number of operations, i.e., the number $m$.

Examples

Input 1

6
aabbaa
baaaab

Output 1

TAK
2
2 4
1 5

Input 2

6
aaabbb
ababab

Output 2

NIE