← 返回题目列表

Codeforces · 1715/B

B. 美丽的阵列

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

Stanley 定义了长度为 $$$n$$$ 的数组 $$$a$$$ 的美感,其中包含非负整数,如下所示: $$$$$$\sum\limits_{i = 1}^{n} \left \lfloor \frac{a_{i}}{k} \right \rfloor,$$$$$$ 这意味着我们将每个元素除以 $$$k$$$,四舍五入下来,并对结果值求和。

Stanley告诉Sam整数$$$k$$$,并要求他找到一个由$$$n$$$个非负整数组成的数组$$$a$$$,使得美丽等于$$$b$$$,元素之和等于$$$s$$$。帮助 Sam — 找到满足上述条件的任何数组。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 1000$$$)。测试用例的描述如下。

每个测试用例的第一行包含整数 $$$n$$$, $$$k$$$, $$$b$$$, $$$s$$$ ($$$1 \leq n \leq 10^{5}$$$, $$$1 \leq k \leq 10^{9}$$$, $$$0 \leq b \leq 10^{9}$$$, $$$0 \leq s \leq 10^{18}$$$)。

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

输出

对于每个测试用例,如果这样的数组 $$$a$$$ 不存在,则打印 $$$-1$$$ 。否则打印 $$$n$$$ 非负整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \leq a_{i} \leq 10^{18}$$$) — 答案。

示例

输入 #1

8
1 6 3 100
3 6 3 12
3 6 3 19
5 4 7 38
5 4 7 80
99978 1000000000 100000000 1000000000000000000
1 1 0 0
4 1000000000 1000000000 1000000000000000000

输出 #1

-1
-1
0 0 19
0 3 3 3 29
-1
-1
0
0 0 0 1000000000000000000

注意

在示例的第一、第二、第五和第六个测试用例中,可以表明这样的数组不存在。

在示例的第三个测试用例中 $$$a = [0, 0, 19]$$$。其中元素之和等于19,它的美感等于$$$\left ( \left \lfloor \frac{0}{6} \right \rfloor + \left \lfloor \frac{0}{6} \right \rfloor + \left \lfloor \frac{19}{6} \right \rfloor \right ) = (0 + 0 + 3) = 3$$$。

在示例的第四个测试用例中 $$$a = [0, 3, 3, 3, 29]$$$。其中的元素总和等于$$$38$$$,它的美感等于$$$(0 + 0 + 0 + 0 + 7) = 7$$$。