Permutation

Time limit1sMemory limit1024 MB

Summary

Find the k-th lexicographically smallest permutation of length n whose inversion count is exactly half of all pairs, or report NIE if none exists.

Level: Hard8 of 10
Topics: Combinatorics, Math, Greedy
Solved: No attempts yet

Problem

A permutation of length $n$ is a sequence in which each integer from 1 to $n$ appears exactly once. An inversion is a pair of distinct elements where the larger one appears earlier in the sequence. A permutation is stable if reversing the order of all its elements leaves the number of inversions unchanged. Find the $k$ -th stable permutation of length $n$ in lexicographic order.

Input

The first line contains two integers $n$ and $k$ ( $1 ≤ n ≤ 250000$ , $1 ≤ k ≤ 10^{18}$ ), the number of elements in the permutation and the index of the permutation to find.

Output

If the $k$ -th stable permutation of length $n$ exists, print TAK on the first line and the elements of the permutation on the second line, separated by single spaces. Otherwise, print NIE on a single line.

Hint

For $n = 4$ there are 6 stable 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).

Examples2

Example 1
Input
```
4 3
```
Expected output
```
TAK
2 4 1 3
```
Example 2
Input
```
4 57
```
Expected output
```
NIE
```