Stanley defines the beauty of an array $a$ of length $n$, which contains non-negative integers, as follows: $$\sum\limits_{i = 1}^{n} \left \lfloor \frac{a_{i}}{k} \right \rfloor,$$ which means that we divide each element by $k$, round it down, and sum up the resulting values.

Stanley told Sam the integer $k$ and asked him to find an array $a$ of $n$ non-negative integers, such that the beauty is equal to $b$ and the sum of elements is equal to $s$. Help Sam — find any of the arrays satisfying the conditions above.


-----Input-----

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 1000$). Description of the test cases follows.

The first line of each test case contains integers $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}$).

It is guaranteed that the sum of $n$ over all test cases does not exceed $10^5$.


-----Output-----

For each test case print $-1$ if such array $a$ does not exist. Otherwise print $n$ non-negative integers $a_1, a_2, \ldots, a_n$ ($0 \leq a_{i} \leq 10^{18}$) — the answer.


-----Examples-----

Input
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
Output
-1
-1
0 0 19
0 3 3 3 29
-1
-1
0
0 0 0 1000000000000000000


-----Note-----

In the first, the second, the fifth and the sixth test cases of the example it is possible to show that such array does not exist.

In the third testcase of the example $a = [0, 0, 19]$. The sum of elements in it is equal to 19, the beauty of it is equal to $\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$.

In the fourth testcase of the example $a = [0, 3, 3, 3, 29]$. The sum of elements in it is equal to $38$, the beauty of it is equal to $(0 + 0 + 0 + 0 + 7) = 7$.

Difficulty: EASY
Tags: Greedy algorithms

Mathematics

Constructive algorithms
Skill types: Greedy algorithms

Starter code:

Solutions:
for _ in range(int(input())):
	(n, k, b, s) = map(int, input().split())
	nums = 0
	if k * b <= s <= k * b + n * (k - 1):
		while s - k >= b * k:
			s -= k - 1
			nums += 1
		print('0 ' * (n - nums - 1) + f'{k - 1} ' * nums + str(s))
	else:
		print(-1)


t = int(input())
for tt in range(t):
	(n, k, b, s) = map(int, input().split())
	if b * k > s:
		print(-1)
	elif int((s - (n - 1) * (k - 1)) / k) > b:
		print(-1)
	elif int(s / k) == b:
		print('0 ' * (n - 1), end='')
		print(s)
	else:
		k1 = str(k - 1) + ' '
		g = (s - k * b - 1) // (k - 1)
		print('0 ' * (n - g - 1), end='')
		print(k1 * g, end='')
		print(s - g * (k - 1))


import math
cases = int(input())
for _ in range(cases):
	line = input().strip('\r\n')
	ss = line.split(' ')
	(n, k, b, s) = tuple([int(x) for x in ss])
	max_v = math.floor(s / k)
	min_v = math.floor((s - (n - 1) * (k - 1)) / k)
	if b < min_v or b > max_v:
		print('-1')
		continue
	if k == 1:
		ans = [0] * (n - 1) + [s]
	else:
		num = max_v - b
		v = s - num * (k - 1)
		while v // k > b:
			m = v // k - b
			num += m
			v = s - num * (k - 1)
		ans = [0] * (n - num - 1) + [k - 1] * num + [v]
	print(' '.join([str(x) for x in ans]))


kol = int(input())
for j in range(0, kol):
	(n, k, b, s) = map(int, input().split())
	f = True
	count = 0
	start = s
	while s / k - 1 >= b and count < n - 1:
		s = s - k + 1
		count = count + 1
	kol = s // k
	if kol != b:
		print(-1)
	else:
		sum1 = start - (k - 1) * count - s
		x = n - count - 1
		l0 = ['0'] * x
		if sum1 != 0:
			l1 = [str(sum1)]
		else:
			l1 = []
		l2 = [str(k - 1)] * count
		l3 = [str(s)]
		l0.extend(l1)
		l0.extend(l2)
		l0.extend(l3)
		print(' '.join(l0))


t = int(input())
for tc in range(t):
	(n, k, b, s) = input().split()
	(n, k, b, s) = (int(n), int(k), int(b), int(s))
	if n == 1:
		if s // k == b:
			print(str(s))
		else:
			print(-1)
		continue
	if k == 1:
		if s != b:
			print(-1)
		else:
			arr = [str(s)]
			for i in range(n - 1):
				arr.append('0')
			print(' '.join(arr))
		continue
	if s < k * b:
		print(-1)
		continue
	x = 0
	if s // k > b:
		x = (s - b * k) // (k - 1)
		if (s - b * k) % (k - 1) == 0:
			x -= 1
	if x > n:
		print(-1)
		continue
	if x == n:
		if s - x * (k - 1) > 0:
			print(-1)
			continue
	arr = []
	for i in range(n):
		if i < x:
			arr.append(str(k - 1))
		elif i == x:
			arr.append(str(s - x * (k - 1)))
		else:
			arr.append(str(0))
	print(' '.join(arr))


case = int(input())
for i in range(case):
	(n, k, b, s) = (int(v) for v in input().split())
	if k * b > s:
		print(-1)
	elif (k - 1) * n + k * b < s:
		print(-1)
	elif n == k == b == s == 1:
		print(1)
	else:
		ans = []
		for j in range(n):
			if s == 0:
				ans.append(str(0))
			elif s - k * b > k - 1:
				ans.append(str(k - 1))
				s -= k - 1
			else:
				ans.append(str(s))
				s = 0
		print(' '.join(ans))


import math
t = int(input())
for i in range(t):
	(n, k, b, s) = list(map(int, input().split()))
	if s // k < b:
		print(-1)
	elif (s - (k - 1) * (n - 1)) // k > b:
		print(-1)
	else:
		ansLis = []
		while s // k != b:
			ansLis.append(k - 1)
			s -= k - 1
		ansLis.append(s)
		while len(ansLis) < n:
			ansLis.append(0)
		print(' '.join(list(map(str, ansLis))))


def Solve():
	for t in range(int(input())):
		(n, k, b, s) = map(int, input().split())
		if k * b > s:
			print(-1)
		elif (s - k * b) // n > k:
			print(-1)
		elif n > 1:
			ans = []
			ans.append(k * b)
			n -= 1
			s -= k * b
			Y = k - 1
			c = s // Y
			if c > n:
				s -= Y * n
				ans += [Y] * n
				n = 0
			else:
				s -= Y * c
				n -= c
				ans += [Y] * c
				c = 0
			if ans[0] + s >= k * (b + 1):
				print(-1)
			else:
				ans[0] += s
				ans += [0] * n
				print(*ans[::-1])
		elif s // k == b:
			print(s)
		else:
			print(-1)
Solve()


import math
T = int(input())
for t in range(T):
	(n, k, b, s) = [int(x) for x in input().split(' ')]
	arr = [s]
	reduce = 0
	for i in range(n - 1):
		if math.floor(arr[0] / k) > b:
			arr.append(k - 1)
			arr[0] = arr[0] - (k - 1)
			reduce = reduce + 1
		elif math.floor(arr[0] / k) == b:
			arr.append(0)
	if math.floor(arr[0] / k) != b:
		print(-1)
	else:
		print(' '.join([str(x) for x in arr]))


t = int(input())
for _ in range(t):
	(n, k, b, s) = map(int, input().split())
	a = [0] * n
	if s // k < b:
		print(-1)
		continue
	border = (n - 1) * (k - 1)
	if (s - border) // k > b:
		print(-1)
		continue
	i = 0
	while s // k > b:
		a[i] = k - 1
		i += 1
		s -= k - 1
	a[i] = s
	print(*a)


t = int(input())
for i in range(t):
	nkb = list(map(int, input().split()))
	(n, k, b, s) = (nkb[0], nkb[1], nkb[2], nkb[3])
	stop = k * b
	stop2 = k * b + (k - 1) * n
	if stop > s or stop2 < s:
		print(-1)
	elif stop == s:
		print(*[0 for i in range(n - 1)] + [stop])
	else:
		m = [0 for i in range(n - 1)] + [stop]
		w = s - stop
		q = 0
		while w > k - 1:
			m[q] = m[q] + k - 1
			w = w - k + 1
			q += 1
		m[-1] = m[-1] + w
		print(*m)