You might not know this, but the brothers Bituś and Bajtuś have quite impressive toy collections! Each brother has $n$ toys, and each toy is one of 26 types. For convenience, the brothers have labeled the toys of each type with consecutive letters of the English alphabet — from a to z.

During today's game, Bituś took out his toys and arranged them in a sequence from left to right. Thus, Bituś can describe the arrangement of his toys using a sequence of $n$ English alphabet characters; the $i$-th character of this sequence denotes the $i$-th toy from the left in Bituś's sequence. Bajtuś also took out his toys and arranged them in a sequence from left to right. Now, Bituś would like to be like Bajtuś — to make his toys arranged in the same order as Bajtuś's toys.

During the game, Bituś can change the order of his toys using moves: each move consists of taking an odd number of consecutive toys and reversing their order. Thus, if the sequence of characters abcdea describes the order of Bituś's toys, then in one move Bituś can obtain, for example, the order adcbea (by reversing the order of toys from the second to the fourth) or edcbaa (by reversing the toys from the first to the fifth). However, he cannot produce the order bacdea in one move.

Is Bituś able to make his toys arranged in the same order as Bajtuś's toys?

Input

The first line of input contains a single integer $n$ ($1 \le n \le 300\,000$) denoting the number of toys owned by Bituś (and also the number of toys owned by Bajtuś). The second line contains a sequence of $n$ English alphabet characters (from a to z) describing the arrangement of Bituś's toys at the beginning of the game. The third line describes the arrangement of Bajtuś's toys — in the same format as the second line.

Output

If Bituś can transform his initial toy arrangement into Bajtuś's toy arrangement using the reversal operations, print TAK in the only line of output. Otherwise, print NIE.

Examples

Input 1

7
abcdefg
edgbcfa

Output 1

TAK

Note 1

In the first example, from the initial toy arrangement, Bitek can create the target toy arrangement in three moves:

a b c d e f g e d c b a f g e d c b g f a e d g b c f a

Input 2

5
abcde
fghhh

Output 2

NIE

Note 2

The answer to the second example is NIE, because Bitek does not possess any toy of type h needed in the target toy arrangement.

Subtasks

Some test groups satisfy the following property: if the answer to a test in this group is TAK, then the target toy arrangement can be obtained from the original in at most one move.

Furthermore, tests in about half of the groups satisfy $n \le 2000$.