An $n$-element permutation is a sequence of natural numbers from $1$ to $n$ in which each number appears exactly once. A pair of its distinct elements is called an inversion if the larger element appears earlier in the sequence.

We are interested in stable permutations, that is, those in which the number of inversions does not change if we reverse the order of all numbers in the sequence. Find the $k$-th lexicographically smallest stable $n$-element permutation.

Input

The first line of input contains two integers $n, k$ ($1 \le n \le 250\,000$, $1 \le k \le 10^{18}$), representing the number of elements in the permutation and the index of the desired stable permutation.

Output

If the $k$-th lexicographically smallest $n$-element permutation exists, print the word TAK in the first line, and in the second line, print $n$ natural numbers separated by single spaces — the consecutive elements of the sought permutation.

If the given permutation does not exist, print the word NIE in a single line.

Examples

Input 1

4 3

Output 1

TAK
2 4 1 3

Input 2

4 57

Output 2

NIE

Note

Explanation for the example: There are 6 stable 4-element permutations: $(1, 4, 3, 2), (2, 3, 4, 1), (2, 4, 1, 3), (3, 1, 4, 2), (3, 2, 1, 4), (4, 1, 2, 3)$.