409156: GYM103447 H What logic for?

What instructs and directs Reyna's analysis and cognition, is his soul together with a sort of sophisticated logic system. In the view of this system, which is blessed with awesome adaptiveness as well as adjustability, everything in a specific metaverse should be readily transformed into some kind of homogeneous expression, for instance, a string. So similarity and equivalency can be explored for further processing.

This afternoon, when wandering on a forest path in NeverLand, Reyna is absorbed by a line of peculiar silver birches. He soon realizes that some of them are essentially identical with the cue given by his logic system. To elaborate this observation, each birch is sparsely coded as a string in Reyna's mind, with a equivalency transition rule due to the sparseness.

A string $$$S$$$ can be represented as an integer sequence $$$S_1, S_2, \cdots, S_l$$$, and according to Reyna's rule, two strings are considered $$$k$$$-equivalent if one can be finitely $$$k$$$-operated to be the other one. For each $$$k$$$-operation, he can choose an integer $$$a\,(1\le a \le l-2k+1)$$$, and then swap $$$S_{a+i}$$$ and $$$S_{a+k+i}$$$ for all $$$i\,(i = 0, 1, \cdots, k-1)$$$.

Now there're $$$n$$$ query tuples $$$(S,\ T,\ k)$$$. For each tuple $$$(S,\ T,\ k)$$$, Reyna would like to query if $$$S$$$ and $$$T$$$ are $$$k$$$-equivalent.

The first line contatins an integer $$$n\,(1\le n\le 10^5)$$$, denoting the number of query tuples.

For each query tuple:

The first line contains $$$l_S + 1$$$ integers. The first integer $$$l_S\,(2\le l_S \le 10^5)$$$ denotes the length of string $$$S$$$, following $$$l_S$$$ integers $$$S_1, S_2, \cdots, S_{l_S} \, (1 \le S_i \le 10^9)$$$ denote the string $$$S$$$.

The second line contains $$$l_T + 1$$$ integers. The first integer $$$l_T\,(2\le l_T \le 10^5)$$$ denotes the length of string $$$T$$$, following $$$l_T$$$ integers $$$T_1, T_2, \cdots, T_{l_T} \, (1 \le T_i \le 10^9)$$$ denote the string $$$T$$$.

The third line contains one integer $$$k\,(1 \le 2k \le \min(l_S, l_T))$$$, denoting the transition parameter.

It's guaranteed that $$$\sum(l_S + l_T) \le 10^5$$$.

For each query tuple, output "TAK"(without quotes) in one line if $$$S$$$ and $$$T$$$ are equivalent, or output "NIE"(without quotes) in one line.

3
5 1 2 3 4 5
5 3 2 5 4 1
2
5 1 2 3 4 5
5 3 2 1 4 5
2
5 1 2 3 4 5
5 5 4 3 2 1
2

TAK
NIE
TAK

For the first query, one possible scheme is:

1. Choose $$$a = 1$$$, then $$$\{1, 2, 3, 4, 5\} \rightarrow \{3, 4, 1, 2, 5\}$$$
2. Choose $$$a = 2$$$, then $$$\{3, 4, 1, 2, 5\} \rightarrow \{3, 2, 5, 4, 1\}$$$

For the third query, one possible scheme is:

1. Choose $$$a = 1$$$, then $$$\{1, 2, 3, 4, 5\} \rightarrow \{3, 4, 1, 2, 5\}$$$
2. Choose $$$a = 2$$$, then $$$\{3, 4, 1, 2, 5\} \rightarrow \{3, 2, 5, 4, 1\}$$$
3. Choose $$$a = 1$$$, then $$$\{3, 2, 5, 4, 1\} \rightarrow \{5, 4, 3, 2, 1\}$$$