← 返回题目列表

Codeforces · 1508/B

B. 几乎已排序

中文机器翻译题面 查看原题

Seiji Maki 不仅喜欢观察正在展开的关系,他还喜欢观察数字序列,尤其是排列。今天,他关注的是几乎已排序的排列。

如果条件 $$$a_{i + 1} \ge a_i - 1$$$ 对于 $$$1$$$ 和 $$$n - 1$$$ 之间的所有 $$$i$$$ 成立,则 $$$1, 2, \dots, n$$$ 的排列 $$$a_1, a_2, \dots, a_n$$$ 被认为是几乎排序的。

Maki 正在考虑按字典顺序给出的 $$$1, 2, \dots, n$$$ 的所有几乎排序排列的列表,他想找到此列表中的第 $$$k$$$ 排列。你能帮他找到这样的排列吗?

排列 $$$p$$$ 按字典顺序小于排列 $$$q$$$ 当且仅当以下条件成立时:

- 在 $$$p$$$ 和 $$$q$$$ 不同的第一个位置,排列 $$$p$$$ 的元素比 $$$q$$$ 中的相应元素小。

输入

第一行包含一个整数 $$$t$$$ ($$$1\le t\le 1000$$$) — 测试用例的数量。

每个测试用例由一行组成,其中包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$1 \le n \le 10^5$$$, $$$1 \le k \le 10^{18}$$$)。

保证所有测试用例的$$$n$$$总和不超过$$$10^5$$$。

输出

对于每个测试用例,打印一行,其中包含按字典顺序排列的第 $$$k$$$ 个几乎排序的长度为 $$$n$$$ 的排列,或者 $$$-1$$$(如果不存在)。

示例

输入 #1

5
1 1
1 2
3 3
6 5
3 4

输出 #1

1 
-1
2 1 3 
1 2 4 3 5 6 
3 2 1

注意

对于第一个和第二个测试,$$$n = 1$$$ 的几乎排序排列列表是 $$$\{[1]\}$$$。

对于第三个和第五个测试,$$$n = 3$$$ 的几乎排序排列列表为 $$$\{[1, 2, 3], [1, 3, 2], [2, 1, 3], [3, 2, 1]\}$$$。