题目描述

题目译自 PA 2017 Runda 1 Permutacja

我们将一个包含从 $1$ 到 $n$ 的自然数且每个数字恰好出现一次的序列称为 $n$ 元素排列。将其中两个不同元素的对称为逆序对，当较大的元素在序列中出现的位置早于较小的元素时。

我们关注的是稳定排列，即那些在将序列中所有数字的顺序反转后，逆序对数量不变的排列。请找出 $n$ 元素排列中按字典序排列的第 $k$ 个稳定排列。

输入格式

输入数据的第一行包含两个整数 $n, k$ $(1 \leq n \leq 250000, 1 \leq k \leq 10^{18})$，分别表示排列的元素数量和所需稳定排列的序号。

输出格式

如果存在按字典序排列的第 $k$ 个 $n$ 元素稳定排列，则在第一行输出 TAK，在第二行输出 $n$ 个用单个空格分隔的自然数，即所需排列的各个元素。

如果指定的排列不存在，则在输出一行 NIE。

4 3

TAK
2 4 1 3

存在 $6$ 个 $4$ 元素稳定排列：

$$(1, 4, 3, 2), (2, 3, 4, 1), (2, 4, 1, 3), (3, 1, 4, 2), (3, 2, 1, 4), (4, 1, 2, 3). $$

4 57

NIE