Chef is very hungry. So, Chef goes to a shop selling burgers. The shop has 2 types of burgers:
Normal burgers, which cost X rupees each
Premium burgers, which cost Y rupees each (where Y > X)

Chef has R rupees. Chef wants to buy exactly N burgers. He also wants to maximize the number of premium burgers he buys. Determine the number of burgers of both types Chef must buy.

Output -1 if it is not possible for Chef to buy N burgers.

------ Input Format ------ 

- The first line contains a single integer T — the number of test cases. Then the test cases follow.
- The first and only line of each test case contains four space-separated integers X, Y, N and R — the cost of a normal burger, the cost of a premium burger, the number of burgers Chef wants to buy and the amount of money Chef has.

------ Output Format ------ 

For each test case, output on a new line two integers: the number of normal burgers and the number of premium burgers Chef must buy satisfying the given conditions.

Output -1 if he cannot buy N burgers.

------ Constraints ------ 

$1 ≤ T ≤ 10^{4}$
$1 ≤X < Y ≤1000$
$1 ≤N ≤10^{6}$
$1 ≤R ≤10^{9}$

----- Sample Input 1 ------ 
4
2 10 4 12
4 8 10 50
99 100 5 10
9 10 10 200

----- Sample Output 1 ------ 
4 0
8 2
-1
0 10

----- explanation 1 ------ 
Test case $1$: Chef has to buy $4$ normal burgers only. Even if he buys $1$ premium burger, he would not be able to buy $4$ burgers.

Test case $2$: Chef can buy $8$ normal burgers and $2$ premium burgers.

Test case $3$: It is not possible for Chef to buy $5$ burgers.

Source: codechef | Difficulty: EASY
Tags: Mathematics

Greedy algorithms


Solutions:
for T in range(int(input())):
	(x, y, n, r) = map(int, input().split())
	ans = [0, 0]
	if r < x * n:
		print(-1)
		next
	elif r >= y * n:
		print(0, n)
		next
	else:
		ans[1] = min(n, (r - x * n) // (y - x))
		ans[0] = n - ans[1]
		print(*ans)


for _ in range(int(input())):
	(x, y, n, r) = map(int, input().split())
	if r < x * n:
		print(-1)
		continue
	elif r > y * n:
		print(0, n)
		continue
	else:
		m = min(n, (r - x * n) // (y - x))
		print(n - m, m)
		continue


for _ in range(int(input())):
	(x, y, n, r) = map(int, input().split())
	if x * n > r:
		print(-1)
	else:
		P_B = min(n, (r - n * x) // (y - x))
		N_B = n - P_B
		print(N_B, P_B)


for i in range(int(input())):
	(x, y, n, r) = map(int, input().split())
	X = 0
	Y = 0
	if r < x * n:
		print(-1)
	else:
		N = min((r - n * x) // (y - x), n)
		X = n - N
		print(X, N)


for _ in range(int(input())):
	(x, y, n, r) = map(int, input().split())
	a = (r - x * n) // (y - x)
	if r // x >= n and y > x:
		if a >= n:
			print(0, ' ', n)
		else:
			print(n - a, ' ', a)
	else:
		print(-1)


for _ in range(int(input())):
	(X, Y, N, R) = map(int, input().split())
	if N * X > R:
		print(-1)
	else:
		y = min((R - N * X) // (Y - X), N)
		x = N - y
		print(x, y)


T = int(input())
for i in range(T):
	(X, Y, N, R) = map(int, input().split())
	X = int(X)
	Y = int(Y)
	N = int(N)
	R = int(R)
	tY = (R - X * N) // (Y - X)
	if tY < 0:
		print(-1)
	elif N - tY < 0:
		print(0, N)
	else:
		print(N - tY, tY)


import math as m
for _ in range(int(input())):
	(x, y, n, r) = map(int, input().split())
	if n * y <= r:
		print(0, n)
	else:
		a = m.floor((r - n * x) / (y - x))
		if a < 0:
			print(-1)
		else:
			print(n - a, a)


t = int(input())
for tc in range(t):
	(x, y, n, r) = map(int, input().split())
	if x * n > r:
		print('-1')
	else:
		a = (r - n * x) // (y - x)
		a = min(a, n)
		print(n - a, a)


t = int(input())
for i in range(t):
	(cost_x, cost_y, burgers, budget) = map(int, input().split())
	count_y = min((budget - burgers * cost_x) // (cost_y - cost_x), burgers)
	count_x = burgers - count_y
	if count_y < 0:
		print(-1)
	else:
		print(count_x, count_y)


for i in range(int(input())):
	(x, y, n, r) = map(int, input().split())
	if n * x > r:
		print(-1)
	else:
		b = (r - n * x) // (y - x)
		b = min(b, n)
		print(n - b, b)


T = int(input())
while T:
	(X, Y, N, R) = map(int, input().split())
	normal_burger = 0
	premium_burger = 0
	if R < X * N:
		print(-1)
	else:
		premium_burger = (R - N * X) // (Y - X)
		premium_burger = min(premium_burger, N)
		normal_burger = N - premium_burger
		print(normal_burger, premium_burger)
	T -= 1


t = int(input())
for i in range(t):
	(x, y, n, r) = map(int, input().split())
	if n * x > r:
		print(-1)
	elif y * n <= r:
		print(0, n)
	else:
		e = (r - n * x) // (y - x)
		print(n - e, e)


import math
for tc in range(int(input())):
	(x, y, n, r) = map(int, input().split())
	nb = n
	pb = 0
	cost = nb * x + pb * y
	if cost > r:
		print(-1)
	else:
		nb = math.ceil((r - n * y) / (x - y))
		if nb < 0:
			nb = 0
		pb = n - nb
		print(nb, pb)


def manage(x, y, n, r):
	yn = (r - n * x) // (y - x)
	return yn
T = int(input())
for _ in range(T):
	(x, y, n, r) = map(int, input().split())
	if r // n < x:
		print(-1)
	elif r // n < y:
		yn = manage(x, y, n, r)
		print(n - yn, yn)
	else:
		print(0, n)


t = int(input())
for i in range(t):
	l = list(map(int, input().split()))
	x = l[0]
	y = l[1]
	n = l[2]
	r = l[3]
	if r < n * x:
		print(-1)
	else:
		b = (r - n * x) // (y - x)
		b = min(b, n)
		a = n - b
		print(a, b)


T = int(input())
for _ in range(T):
	(x, y, n, r) = map(int, input().split())
	if x * n > r:
		print(-1)
		continue
	if y * n <= r:
		print(0, n)
		continue
	a = r - n * x
	b = y - x
	d = a // b
	print(n - d, d)


t = int(input())
for i in range(t):
	x = input().split()
	(cost_norm, cost_pre, num_of_bur, money) = (int(x[0]), int(x[1]), int(x[2]), int(x[3]))
	norm_bur = 0
	pre_bur = 0
	a = (money - cost_norm * num_of_bur) // (cost_pre - cost_norm)
	if type(a) == int:
		if a >= 0:
			if num_of_bur - a >= 0:
				print(num_of_bur - a, a)
			else:
				print('0', num_of_bur)
		else:
			print('-1')
	elif a < 0:
		print('-1')
	elif a < 1 and a >= 0:
		print(num_of_bur, '0')
	else:
		print(num_of_bur - int(a), int(a))


for i in range(int(input())):
	(n, p, q, a) = map(int, input().split())
	if n * q > a:
		print(-1)
	elif p * q <= a:
		print(0, q)
	else:
		e = (a - n * q) // (p - n)
		print(q - e, e)


for _ in range(int(input())):
	(x, y, n, r) = list(map(int, input().split()))
	if n * x > r:
		print(-1)
	elif y * n <= r:
		print(0, n)
	else:
		c = (r - n * x) // (y - x)
		print(n - c, c)


import math
for _ in range(int(input())):
	(x, y, n, r) = map(int, input().split())
	if min(x, y) * n > r:
		print(-1)
	elif x == y:
		print(0, n)
	else:
		a = (r - n * y) / (x - y)
		if a < 0:
			a = 0
		print(math.ceil(a), n - math.ceil(a))


class Burger:

	def __init__(self, x: int, y: int, n: int, r: int) -> None:
		self.__x = x
		self.__y = y
		self.__n = n
		self.__r = r

	def Solution(self):
		if self.__n * self.__x > self.__r:
			print('-1')
		elif (self.__r - self.__n * self.__x) // (self.__y - self.__x) > self.__n:
			print('0', self.__n)
		else:
			print(self.__n - (self.__r - self.__x * self.__n) // (self.__y - self.__x), (self.__r - self.__x * self.__n) // (self.__y - self.__x))
t = int(input())
assert t >= 1 and t <= 10000.0
while t:
	(x, y, n, r) = map(int, input().split(' '))
	ans = Burger(x, y, n, r)
	ans.Solution()
	t -= 1


for _ in range(int(input())):
	(x, y, n, r) = map(int, input().split())
	if n * x > r:
		print('-1')
	else:
		r = r - n * x
		t = r // (y - x)
		if t > n:
			t = n
		print(n - t, t)


for i in range(int(input())):
	(a, b, c, d) = map(int, input().split())
	if a * c > d:
		print(-1)
	elif b * c <= d:
		print(0, c)
	else:
		e = (d - c * a) // (b - a)
		print(c - e, e)


for _ in range(int(input())):
	(x, y, z, w) = map(int, input().split())
	if x * z > w:
		print(-1)
	elif y * z <= w:
		print(0, z)
	else:
		nl = z
		pr = 0
		d1 = y - x
		d2 = w - x * z
		ex = d2 // d1
		nl = nl - ex
		pr = pr + ex
		print(nl, pr)


t = int(input())
for _ in range(t):
	(x, y, n, r) = map(int, input().split())
	if r // x < n:
		print(-1)
	elif r // y >= n:
		print(0, n)
	else:
		normal = n
		pre = 0
		diff1 = y - x
		diff2 = r - x * n
		extra = diff2 // diff1
		normal = normal - extra
		pre = pre + extra
		print(normal, pre)


T = int(input())
for i in range(T):
	(a, b, c, d) = map(int, input().split())
	if int(d / a) < c:
		print(-1)
	else:
		ans = int((d - c * a) / (b - a))
		if ans > c:
			ans = c
		print(c - ans, ans)


t = int(input())
while t > 0:
	(x, y, n, r) = map(int, input().split())
	w = (r - x * n) // (y - x)
	if y * n < r:
		print(0, n)
	elif w < 0:
		print(-1)
	else:
		print(n - w, w)
	t = t - 1


for i in range(int(input())):
	(x, y, n, r) = map(int, input().split())
	w1 = (r - x * n) / (y - x)
	w = int(w1)
	if y * n < r:
		print(0, n)
	elif w1 < 0:
		print(-1)
	else:
		print(n - w, w)


import math
t = int(input())
for x in range(t):
	(normal, premium, n, money) = list(map(int, input().split(' ')))
	y = 0
	y = (money - normal * n) / (premium - normal)
	total = math.floor(y)
	if premium * n < money:
		print(0, n)
	elif y < 0:
		print(-1)
	else:
		print(n - total, total)


for _ in range(int(input())):
	(x, y, n, r) = map(int, input().split())
	n1 = 0
	if n * x > r:
		print('-1')
	elif y * n <= r:
		print(0, n)
	else:
		z = (r - n * x) // (y - x)
		print(n - z, z)


n = int(input())
for _ in range(0, n):
	arr = [int(i) for i in input().split()] + [0, 0, 0, 0]
	arr[5] = arr[3] - arr[2] * arr[0]
	arr[6] = arr[1] - arr[0]
	arr[4] = arr[5] // arr[6]
	arr[4] = min(arr[4], arr[2])
	if arr[4] >= 0:
		print(arr[2] - arr[4], arr[4])
	else:
		print(-1)


t = int(input())
for ni in range(t):
	(x, y, n, r) = map(int, input().split())
	if x * n > r:
		print(-1)
	else:
		r = r - x * n
		td = r // (y - x)
		if td > n:
			td = n
		print(int(n - td), td)


t = int(input())
for i in range(t):
	(x, y, n, r) = map(int, input().split())
	if x * n > r:
		print('-1')
	else:
		r -= x * n
		times_dif = r // (y - x)
		if times_dif > n:
			times_dif = n
		print(f'{n - times_dif} {times_dif}')


T = int(input())
for i in range(T):
	(X, Y, N, R) = map(int, input().split())
	if N * X > R:
		print('-1')
	else:
		R = R - N * X
		P = R // (Y - X)
		if P > N:
			P = N
		print(N - P, P)


t = int(input())
while t != 0:
	(x, y, n, r) = map(int, input().split())
	if n * x > r:
		print('-1')
	else:
		r = r - n * x
		p = r // (y - x)
		if p > n:
			p = n
		print(n - p, p)
	t -= 1


p = int(input())
for i in range(p):
	(x, y, n, r) = map(int, input().split())
	if x * n > r:
		print(-1)
	elif y * n <= r:
		print(0, n)
	else:
		z = (r - n * x) // (y - x)
		print(n - z, z)


T = int(input())
for _ in range(T):
	(X, Y, N, R) = list(map(int, input().split()))
	if R < X * N:
		print(-1)
	elif R >= Y * N:
		print(0, N)
	else:
		Rx = N * X
		remaining = R - Rx
		if not remaining >= Y - X:
			print(N, 0)
		else:
			Ny = remaining // (Y - X)
			print(N - Ny, Ny)


import math
t = int(input())
for i in range(t):
	(x, y, n, r) = map(int, input().split())
	u = n * y
	if u <= r:
		print(0, n)
	elif n * x > r:
		print(-1)
	else:
		o = math.ceil((y * n - r) / (y - x))
		print(o, n - o)


for t in range(int(input())):
	(x, y, n, r) = map(int, input().split())
	if r < x * n:
		print(-1)
	elif r / y >= n:
		print(0, n)
	else:
		base = x * n
		diff = y - x
		premium_burgers = int((r - base) // diff)
		print(n - premium_burgers, premium_burgers)


t = int(input())
for i in range(t):
	(x, y, n, r) = list(map(int, input().split()))
	if x * n > r:
		print('-1')
	else:
		Y = min((r - n * x) // (y - x), n)
		X = n - Y
		print(X, Y)


t = int(input())
for _ in range(t):
	(x, y, n, r) = map(int, input().split())
	if r / y >= n:
		print(0, ' ', n)
	elif r / x < n:
		print(-1)
	else:
		g = int(y * n)
		h = int(x - y)
		i = int((r - g) / h)
		if (r - g) % h != 0:
			i += 1
		print(i, ' ', n - i)


T = int(input())
for i in range(T):
	(x, y, n, r) = list(map(int, input().split()))
	if int(r / x) < n:
		print(-1)
	elif n * y <= r:
		print(0, n)
	else:
		premium = int((r - x * n) / (y - x))
		print(n - premium, premium)


t = int(input())
for _ in range(t):
	(x, y, n, r) = map(int, input().split())
	if r >= n * y:
		print(0, n)
	elif r >= n * x:
		leftover = r - n * x
		pre = leftover // (y - x) % n
		print(n - pre, pre)
	else:
		print(-1)


for _ in range(int(input())):
	(x, y, n, r) = map(int, input().split())
	if r < x * n:
		print('-1')
		continue
	if r >= n * y:
		print('0 ' + str(n))
		continue
	pre = (r - x * n) // (y - x)
	print(n - pre, pre)


for _ in range(int(input())):
	(x, y, n, r) = map(int, input().split())
	if x * n > r:
		print(-1)
	else:
		f = (r - n * x) // (y - x)
		s = min(f, n)
		print(n - s, s)


T = int(input())
for t in range(0, T):
	(X, Y, N, R) = map(int, input().split())
	p = min((R - N * X) // (Y - X), N)
	if p < 0:
		print(-1)
	else:
		print(N - p, p)


t = int(input())
for i in range(t):
	(x, y, n, r) = map(int, input().split())
	a2 = (r - n * x) // (y - x)
	a1 = n - a2
	if r // y >= n:
		print(0, n)
	elif a1 < 0 or a2 < 0:
		print(-1)
	else:
		print(a1, a2)