题目描述

档案馆中有 $n$ 份编号为 $1$ 到 $n$ 的档案。现在需要把这 $n$ 份档案排成一个排列。

对于一个排列 $p_1,p_2,\ldots,p_n$，如果一对下标 $(i,j)$ 满足：

那么称 $(i,j)$ 是这个排列中的一个 顺序对。

现在给定三个整数 $n,k,m$。你需要找出所有长度为 $n$、且恰有 $m$ 个顺序对的排列，并按照字典序从小到大排序。

请输出其中字典序第 $k$ 小的排列。

为了方便，保证 $m$ 在下面这个区间内均匀随机生成：

如果不存在第 $k$ 小的合法排列，输出 -1。

输入格式

输入一行三个非负整数 $n,k,m$。

输出格式

如果无解，输出一行 -1。

否则输出一行 $n$ 个正整数，表示字典序第 $k$ 小的合法排列。

样例 1 输入

5 4 2

样例 1 输出

4 5 3 1 2

样例 1 解释

顺序对数恰为 $2$ 的长度为 $5$ 的排列有：

3 5 4 2 1
4 3 5 2 1
4 5 2 3 1
4 5 3 1 2
5 2 4 3 1
5 3 2 4 1
5 3 4 1 2
5 4 1 3 2
5 4 2 1 3

其中，字典序第 $4$ 小的排列为：

4 5 3 1 2

样例 2 输入

10 1145141919810 6

样例 2 输出

-1

样例 2 解释

长度为 $10$ 且顺序对数恰好为 $6$ 的排列不足 $1145141919810$ 个，因此无解。

样例 3,4,5

见选手目录下：

• perm/ex_perm.3-5.in
• perm/ex_perm.3-5.out

测试点约束

对于所有数据，满足：

各子任务如下：

• 子任务 1：$n=8$，无特殊性质，分值 10。
• 子任务 2：$n=18$，无特殊性质，分值 10。
• 子任务 3：$n=100$，无特殊性质，分值 15。
• 子任务 4：$n=3000$，无特殊性质，分值 15。
• 子任务 5：$n=10^5$，$k=1$，分值 15。
• 子任务 6：$n=10^5$，无特殊性质，分值 20。
• 子任务 7：$n=2\times 10^5$，无特殊性质，分值 15。