Tournament

$n$ players ($n$ is a power of two) play in a single-elimination tournament. Each player receives a distinct number $i$ with $1 \le i \le n$. The bracket is built as follows. The player numbers are drawn one by one, and the $i$-th drawn number is $a_i$. In the first round, player $a_1$ plays $a_2$, $a_3$ plays $a_4$, and so on, until $n/2$ winners remain. In the second round, the first winner plays the second, the third plays the fourth, and so on, until $n/4$ winners remain. This continues until one tournament champion is left. Some players find certain schedules unsuitable, so they propose replacing the sequence $A$ with another sequence $B_j$. The remaining players want the tournament to stay identical to the original. That means every pair of players must be able to meet in the same round, provided both keep winning until then.

The first line contains two integers $n$ and $k$, the number of players and the number of proposed sequences. The second line contains the sequence $A$, where the $i$-th number is $a_i$. The next $k$ lines contain the sequences $B_j$ ($1 \le j \le k$). On line $j+2$, the $i$-th number $b_{j,i}$ is the proposed value for $a_i$ ($1 \le i \le n$).

Print $k$ lines, each containing one word: TAIP if the tournament defined by $B_j$ is identical to the tournament defined by $A$, or NE otherwise.

$4 \le n \le 2^{16}$, $n$ is a power of two, $1 \le k \le 20$, $1 \le a_i, b_{j,i} \le n$. For $u \ne v$, $a_u \ne a_v$ and $b_{j,u} \ne b_{j,v}$.