← 返回题目列表

Codeforces · 1512/E

E. 按和排列

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

排列是从 $$$1$$$ 到 $$$n$$$ 的 $$$n$$$ 整数序列,其中所有数字恰好出现一次。例如,$$$[1]$$$、$$$[3, 5, 2, 1, 4]$$$、$$$[1, 3, 2]$$$ 是排列,$$$[2, 3, 2]$$$、$$$[4, 3, 1]$$$、$$$[0]$$$ 不是排列。

Polycarp 被给予四个整数 $$$n$$$、$$$l$$$、$$$r$$$ ($$$1 \le l \le r \le n)$$$ 和 $$$s$$$ ($$$1 \le s \le \frac{n (n+1)}{2}$$$) 并要求从 $$$p$$$ 中找出数字的排列$$$1$$$ 到 $$$n$$$ 满足以下条件:

- $$$s = p_l + p_{l+1} + \ldots + p_r$$$。

例如,对于 $$$n=5$$$、$$$l=3$$$、$$$r=5$$$ 和 $$$s=8$$$,以下排列是合适的(未列出所有选项):

- $$$p = [3, 4, 5, 2, 1]$$$;
- $$$p = [5, 2, 4, 3, 1]$$$;
- $$$p = [5, 2, 1, 3, 4]$$$。

帮助 Polycarp,对于给定的 $$$n$$$、$$$l$$$、$$$r$$$ 和 $$$s$$$,找到符合上述条件的从 $$$1$$$ 到 $$$n$$$ 的数字排列。如果有几种合适的排列,请打印其中任何一个。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 500$$$)。然后是 $$$t$$$ 测试用例。

每个测试用例由一行四个整数组成 $$$n$$$ ($$$1 \le n \le 500$$$), $$$l$$$ ($$$1 \le l \le n$$$), $$$r$$$ ($$$l \le r \le n$$$), $$$s$$$ ($$$1 \le s \le \frac{n (n+1)}{2}$$$)。

保证所有输入数据集的$$$n$$$总和不超过$$$500$$$。

输出

对于每个测试用例,在单独的行上输出:

- $$$n$$$ 整数 - 长度为 $$$n$$$ 的排列,如果存在这样的排列,则符合上述条件;
- -1,否则。

如果有多个合适的排列,则打印其中任何一个。

示例

输入 #1

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

输出 #1

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