#P18609. Balanced Permutations

Balanced Permutations

Balanced Permutations

给定一个长度为 nn 的排列 pp。若 pp 的某个连续子数组中的最大值是该子数组的第一个元素或最后一个元素,则称这个子数组为“不稳定子数组”。

在所有长度为 nn 的排列中,如果一个排列的不稳定子数组数量达到最小值,就称这个排列是“平衡排列”。长度为 11 的子数组也计入,且每个子数组只计一次。

给定 n,l,kn,l,k,请分别求出:

  • 按字典序从小到大排列的所有长度为 nn 的平衡排列中的第 ll 个。
  • 按字典序从大到小排列的所有长度为 nn 的平衡排列中的第 kk 个。

两个排名都从 11 开始。若其中某个排名对应的排列不存在,则只对该项输出 -1。

输入格式

输入仅一行,包含三个整数 n,l,kn,l,k。

满足 1≤n≤1051\le n\le 10^5,1≤l,k≤10181\le l,k\le 10^{18}。

输出格式

输出两行。

第一行输出字典序第 ll 小的平衡排列 p1,p2,…,pnp_1,p_2,\ldots,p_n;若不存在,输出 -1。

第二行输出字典序第 kk 大的平衡排列 q1,q2,…,qnq_1,q_2,\ldots,q_n;若不存在,输出 -1。

输出的每个排列都必须恰好包含整数 1,2,…,n1,2,\ldots,n 各一次。两行是否存在应当分别判断。

样例输入 1

3 1 2

样例输出 1

1 3 2
1 3 2

样例输入 2

4 9 13

样例输出 2

3 1 4 2
-1