Bytie's dad works as a tailor. One day, when dad left Bytie alone in his workshop, Bytie found a very nice tape. It actually was a tape measure containing consecutive numbers from $1$ to $n$. Somehow Bytie also managed to find his dad's scissors...
Unfortunately, when dad came, it was already too late: Bytie already cut the tape a few times. What is fortunate, in each of the cuts Bytie cut out a fragment of the tape, reversed it and put it back exactly at the same position. Bytie claims that he performed exactly $k$ such cuts. For example, if the initial tape was $[1,\,2,\,3,\,4,\,5,\,6]$ and Bytie cut out the fragment $[3,\,4,\,5]$ and reversed it, the tape would be $[1,\,2,\,5,\,4,\,3,\,6]$.
Help Bytie's dad and try to restore the initial tape using $k$ operations of cutting and reversing fragments.
Input
The first line of input contains two integers $n$ and $k$ ($1 \leq n \leq 100\,000$, $0 \leq k \leq 3$) that represent the number of integers written on the tape and the number of operations that Bytie claims to have performed. The next line contains the numbers written on the tape when Bytie's dad entered the room: a sequence of $n$ integers $a_i$ ($1 \leq a_i \leq n$).
Output
The first line of output should contain one word TAK (Polish for yes) or NIE (Polish for no),
depending on whether one can restore the initial state of the tape using $k$ cuts.
If the answer is positive, the following $k$ lines of output should contain two integers $l_i$, $r_i$ each ($1 \leq l_i \leq r_i \leq n$):
the indices of the first and last element of consecutive fragments that are to be reversed.
If there is more than one correct answer, your program should output any none of them.
Examples
Input
4 2 3 4 1 2
Output
TAK 1 3 2 4
Input
4 1 3 4 1 2
Output
NIE
Explanation
After Bytie played with the tape, the sequence of numbers is $[3,\, 4,\, 1,\, 2]$. In the first example we can restore the initial state of the tape in two operations:
- Cut and reverse the fragment from the first to the third tape element, the result is: $[1,\, 4,\, 3,\, 2]$.
- Cut and reverse the fragment from the second to the fourth tape element, the result is: $[1,\, 2,\, 3,\, 4]$.
One cannot restore the initial state of the tape using just a single operation.