N. Na zdrowie
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Frank and his friends are playing a game at the little gas station. The game has a list of $$$n$$$ distinct languages $$$a_1, a_2, \ldots , a_n$$$. Each language is represented by a number from $$$1$$$ to $$$n$$$ and appears only once. Frank does not trust the competitive programming skills of Brazilians, so he wants you to answer $$$q$$$ queries. Each query contains two integers $$$l$$$ and $$$r$$$, and you need to tell Frank if the sublist $$$a_l, a_{l+1}, \ldots , a_r$$$ is a good drink. Since Frank only speaks Polish, respond with "TAK" if the list is a good drink and "NIE" otherwise.

A list of size $$$m$$$ is a good drink if it is a permutation, that is, it contains all the numbers from $$$1$$$ to $$$m$$$ exactly once.

Input

The first line contains two integers $$$n$$$ and $$$q$$$ ($$$1 \leq n, q \leq 10^5$$$), the size of the list and the number of queries, respectively.

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots , a_n$$$ ($$$1 \leq a_i \leq n$$$), representing the elements of the list. It is guaranteed that the list is a permutation.

The next $$$q$$$ lines contain two integers $$$l$$$ and $$$r$$$ ($$$1 \leq l \leq r \leq n$$$), representing the queries.

Output

For each query, print a line with the word "TAK" if the sublist $$$a_l, a_{l+1}, \ldots , a_r$$$ forms a permutation, or "NIE" otherwise.

Examples
Input
4 3
1 2 3 4
1 2
2 3
1 4
Output
TAK
NIE
TAK
Input
5 4
4 1 2 3 5
2 3
1 3
2 4
1 4
Output
TAK
NIE
TAK
TAK
Input
1 1
1
1 1
Output
TAK