AtCoder Beginner Contest 085 - Otoshidama

The commonly used bills in Japan are 10000-yen, 5000-yen and 1000-yen bills. Below, the word "bill" refers to only these.

According to Aohashi, he received an otoshidama (New Year money gift) envelope from his grandfather that contained N bills for a total of Y yen, but he may be lying. Determine whether such a situation is possible, and if it is, find a possible set of bills contained in the envelope. Assume that his grandfather is rich enough, and the envelope was large enough.

Constraints

* 1 ≤ N ≤ 2000
* 1000 ≤ Y ≤ 2 × 10^7
* N is an integer.
* Y is a multiple of 1000.

Input

Input is given from Standard Input in the following format:


N Y


Output

If the total value of N bills cannot be Y yen, print `-1 -1 -1`.

If the total value of N bills can be Y yen, let one such set of bills be "x 10000-yen bills, y 5000-yen bills and z 1000-yen bills", and print x, y, z with spaces in between. If there are multiple possibilities, any of them may be printed.

Examples

Input

9 45000


Output

4 0 5


Input

20 196000


Output

-1 -1 -1


Input

1000 1234000


Output

14 27 959


Input

2000 20000000


Output

2000 0 0

Difficulty: UNKNOWN_DIFFICULTY

Starter code:

Solutions:
(n, y) = map(int, input().split())
ans = [-1, -1, -1]
for i in range(n + 1):
	for j in range(n + 1 - i):
		if 10000 * i + 5000 * j + 1000 * (n - i - j) == y:
			ans = [i, j, n - i - j]
print(*ans)


(n, y) = map(int, input().split())
for i in range(n + 1):
	for j in range(n + 1):
		if 10000 * n - 5000 * i - 9000 * j == y and n - i - j >= 0:
			print(n - i - j, i, j)
			quit()
print(-1, -1, -1)


(N, Y) = map(int, input().split())
for i in range(N + 1):
	for m in range(N + 1 - i):
		y = N - i - m
		if Y == i * 10000 + m * 5000 + y * 1000:
			print(i, m, y)
			exit()
print(-1, -1, -1)


(n, y) = map(int, input().split(' '))
for i in range(0, n + 1):
	for j in range(0, n + 1 - i):
		k = n - i - j
		if 10000 * i + 5000 * j + 1000 * k == y:
			print(i, j, k)
			exit()
print('-1 -1 -1')


(n, y) = map(int, input().split())
y //= 1000
for i in range(n + 1):
	for j in range(n - i + 1):
		if n - i - j == y - 10 * i - 5 * j:
			print(i, j, n - i - j)
			exit()
print(-1, -1, -1)


(N, Y) = map(int, input().split())
for x in range(N + 1):
	for y in range(N - x + 1):
		z = N - x - y
		if 10000 * x + 5000 * y + 1000 * z == Y:
			print(x, y, z)
			quit()
print(-1, -1, -1)


(N, Y) = map(int, input().split())
for i in range(N + 1):
	for j in range(N + 1 - i):
		k = N - i - j
		if Y == 10000 * i + 5000 * j + 1000 * k:
			print(i, j, k)
			exit()
print(-1, -1, -1)


(n, y) = map(int, input().split())
d = y // 1000 - n
a = d * 7 % 9
b = (d - a * 4) // 9
c = n - a - b
if c >= 0 and b >= 0:
	print(b, a, c)
else:
	print(-1, -1, -1)


import sys
(n, y) = map(int, input().split())
for a in range(n + 1):
	for b in range(n + 1 - a):
		if 10000 * a + 5000 * b + 1000 * (n - a - b) == y:
			print(a, b, n - a - b)
			sys.exit()
print(-1, -1, -1)


(n, k) = map(int, input().split())
a = [-1, -1, -1]
for i in range(n + 1):
	for j in range(n - i + 1):
		if i * 10000 + j * 5000 + (n - i - j) * 1000 == k:
			a = [i, j, n - i - j]
print(*a)


(N, Y) = map(int, input().split())
L = Y // 1000 - N
H = L * 7 % 9
F = (L - 4 * H) // 9
if F < 0 or H + F > N:
	print('-1 -1 -1')
else:
	print('{} {} {}'.format(F, H, N - F - H))


(N, Y) = map(int, input().split())
for i in range(N + 1):
	for j in range(N + 1 - i):
		if 9000 * i + 4000 * j == Y - 1000 * N:
			print(i, j, N - i - j)
			exit()
print(-1, -1, -1)


(n, y) = map(int, input().split())
for a in range(n + 1):
	for b in range(9):
		c = n - a - b
		if c >= 0 and a * 10000 + b * 5000 + c * 1000 == y:
			print(a, b, c)
			exit()
print(-1, -1, -1)


(n, y) = map(int, input().split())
for i in range(n + 1):
	for j in range(n - i + 1):
		if 9 * i + 4 * j + n == y / 1000.0:
			print(i, j, n - i - j)
			exit()
print(-1, -1, -1)


(N, Y) = map(int, input().split())
for x in range(N + 1):
	for y in range(N + 1 - x):
		z = N - x - y
		if 10000 * x + 5000 * y + 1000 * z == Y and 2000 >= z >= 0:
			print(x, y, z)
			exit()
print(-1, -1, -1)


(N, Y) = map(int, input().split())
Y //= 1000
for i in range(N + 1):
	for j in range(N - i + 1):
		if i * 10 + j * 5 + (N - i - j) == Y:
			print(i, j, N - i - j)
			exit()
print(-1, -1, -1)


import sys
(a, b) = map(int, input().split())
b = b / 1000
for i in range(a + 1):
	for j in range(a - i + 1):
		if 10 * i + 5 * j + a - i - j == b:
			print(i, j, a - i - j)
			sys.exit()
print(-1, -1, -1)


(N, Y) = map(int, input().split())
for a in range(N + 1):
	for b in range(N - a + 1):
		c = N - a - b
		if a * 10000 + b * 5000 + 1000 * c == Y:
			print(a, b, c)
			exit()
print('-1 -1 -1')


import sys
(n, y) = map(int, input().split())
for i in range(n + 1):
	for j in range(n + 1 - i):
		if 10000 * i + 5000 * j + 1000 * (n - i - j) == y and n - i - j >= 0:
			print(i, j, n - i - j)
			sys.exit()
print(-1, -1, -1)


(n, y) = map(int, input().split())
(s, t, u) = (-1, -1, -1)
for i in range(n + 1):
	for j in range(n - i + 1):
		if 10000 * i + 5000 * j + 1000 * (n - i - j) == y:
			(s, t, u) = (i, j, n - i - j)
print(s, t, u)


(N, Y) = map(int, input().split())
Y = Y // 1000
for x in range(N + 1):
	for y in range(N + 1 - x):
		if N + 9 * x + 4 * y == Y:
			print(x, y, N - x - y)
			exit()
print('-1 -1 -1')


(a, b) = map(int, input().split())
for i in range(a + 1):
	for j in range(a - i + 1):
		if i * 10000 + j * 5000 + (a - i - j) * 1000 == b:
			print(i, j, a - i - j)
			exit()
print(-1, -1, -1)


(N, Y) = map(int, input().split())
A = -1
B = -1
C = -1
for i in range(N + 1):
	for j in range(N + 1 - i):
		if 10000 * i + 5000 * j + 1000 * (N - i - j) == Y:
			(A, B, C) = (i, j, N - i - j)
print(A, B, C)


(mai, yen) = map(int, input().split())
for i in range(mai + 1):
	for j in range(mai + 1 - i):
		if 10000 * i + 5000 * j + 1000 * (mai - i - j) == yen:
			print(i, j, mai - i - j)
			exit()
else:
	print(-1, -1, -1)


(n, y) = map(int, input().split())
x = [-1, -1, -1]
for i in range(n + 1):
	for j in range(n - i + 1):
		if 10000 * i + 5000 * j + 1000 * (n - i - j) == y:
			x = [i, j, n - i - j]
			break
for _ in range(3):
	print(x[_])


(N, Y) = map(int, input().split())
res = (-1, -1, -1)
for x in range(N + 1):
	for y in range(N + 1 - x):
		if N - x - y >= 0 and 10000 * x + 5000 * y + 1000 * (N - x - y) == Y:
			res = [x, y, N - x - y]
print(res[0], res[1], res[2])


(n, Y) = map(int, input().split())
for x in range(-~n):
	for y in range(-~n - x):
		if x * 10 + y * 5 + (n - x - y) == Y // 1000:
			print(x, y, n - x - y)
			exit()
print(*[-1] * 3)


(n, y) = map(int, input().split())
y //= 1000
for i in range(n + 1):
	(p, q) = divmod(y - n - i, 4)
	if q == 0 and i <= p - i <= n:
		print(i, p - 2 * i, n - p + i)
		exit()
print('-1 ' * 3)


(N, Y) = map(int, input().split())
a = -1
b = -1
c = -1
for i in range(N + 1):
	for j in range(N + 1 - i):
		if i * 9000 + j * 4000 == Y - 1000 * N:
			a = i
			b = j
			c = N - i - j
print(a, b, c)


(n, Y) = map(int, input().split())
a = (-1, -1, -1)
for x in range(n + 1):
	for y in range(n - x + 1):
		z = n - x - y
		if 10000 * x + 5000 * y + 1000 * z == Y:
			a = (x, y, z)
			break
print(*a)


(n, y) = map(int, input().split())
for i in range(n + 1):
	for g in range(n - i + 1):
		s = n - i - g
		if 10000 * i + 5000 * g + 1000 * s == y:
			print(i, g, s)
			exit()
print('-1 -1 -1')


(n, t) = map(int, input().split())
for x in range(n + 1):
	for y in range(n - x + 1):
		z = n - x - y
		if 10000 * x + 5000 * y + 1000 * z == t and z >= 0:
			print(x, y, z)
			exit()
print(-1, -1, -1)


(n, x) = map(int, input().split())
for i in range(n + 1):
	for j in range(n - i + 1):
		if x == 10000 * i + 5000 * j + 1000 * (n - i - j):
			print(i, j, n - i - j)
			exit()
print('-1 -1 -1')


(n, m) = map(int, input().split())
count = 0
for i in range(n + 1):
	for j in range(n - i + 1):
		if i * 10000 + j * 5000 + (n - j - i) * 1000 == m:
			print(i, j, n - j - i)
			exit()
if count == 0:
	print('-1 -1 -1')


(n, y) = map(int, input().split())
ans = [-1] * 3
y //= 1000
for i in range(n + 1):
	for j in range(n - i + 1):
		if i * 9 + j * 4 + n == y:
			ans = [i, j, n - i - j]
print(*ans)


(n, y) = map(int, input().split())
y = y / 1000
ans = (-1, -1, -1)
for i in range(1 + n):
	for j in range(n - i + 1):
		if i * 10 + j * 5 + (n - i - j) == y and n - i - j >= 0:
			ans = (i, j, n - i - j)
print(*ans)


(n, y) = map(int, input().split())
for a in range(n + 1):
	for b in range(n - a + 1):
		c = n - a - b
		if 10 * a + 5 * b + c == y / 1000.0:
			print(a, b, c)
			exit()
print(-1, -1, -1)


(N, Y) = map(int, input().split())
for x in range(N + 1):
	for y in range(N + 1 - x):
		if 10000 * x + 5000 * y + 1000 * (N - x - y) == Y:
			print('%d %d %d' % (x, y, N - x - y))
			exit()
print('-1 -1 -1')


(N, Y) = map(int, input().split())
for k in range(N + 1):
	for l in range(N - k + 1):
		if 10000 * k + 5000 * l + 1000 * (N - k - l) == Y:
			print(k, l, N - k - l)
			exit(0)
print('-1 -1 -1')


import math
(n, y) = map(int, input().split())
y = y // 1000
k = math.ceil(2 * (y - n) / 9)
if k * 4 <= y - n and 5 * k <= y:
	print(-4 * k + y - n, 9 * k - 2 * (y - n), y - 5 * k)
else:
	print(-1, -1, -1)


(n, y) = map(int, input().split())

def solve():
	for i in range(n + 1):
		for j in range(n + 1 - i):
			if 10000 * i + 5000 * j + 1000 * (n - i - j) == y:
				return (i, j, n - i - j)
	return (-1, -1, -1)
print(*solve())


(N, K) = map(int, input().split())
a = -1
b = -1
c = -1
for i in range(N + 1):
	for k in range(N - i + 1):
		if 10000 * i + 5000 * k + 1000 * (N - i - k) == K:
			a = i
			b = k
			c = N - k - i
print(a, b, c)


(n, m) = map(int, input().split())
for x in range(n + 1):
	for y in range(n + 1 - x):
		if 10000 * x + 5000 * y + 1000 * (n - x - y) == m:
			print(x, y, n - x - y)
			exit()
print('-1 -1 -1')


(n, Y) = map(int, input().split())
a = Y // 1000
for x in range(n + 1):
	for y in range(n - x + 1):
		if 9 * x + 4 * y == a - n and n - x - y >= 0:
			print(x, y, n - x - y)
			exit()
print(-1, -1, -1)


(N, Y) = map(int, input().split())
y = Y // 1000
d = y - N
k = min(d // 4, (N + d) // 5)
if 9 * k >= 2 * d:
	print(d - 4 * k, -2 * d + 9 * k, N + d - 5 * k)
else:
	print(-1, -1, -1)


(N, Y) = map(int, input().split())
L = [-1, -1, -1]
for i in range(0, min(Y // 10000, N) + 1):
	for j in range(0, N - i + 1):
		if i * 10000 + j * 5000 + (N - i - j) * 1000 == Y:
			L = [i, j, N - i - j]
			break
print(*L)


(N, Y) = map(int, input().split())
for i in range(N + 1):
	for s in range(N + 1):
		k = N - i - s
		if k >= 0 and 1000 * i + 5000 * s + 10000 * k == Y:
			print(k, s, i)
			exit()
print(-1, -1, -1)


(N, Y) = map(int, input().split())
ans = [-1, -1, -1]
for x in range(N + 1):
	for y in range(N + 1 - x):
		if 9000 * x + 4000 * y + 1000 * N == Y:
			ans = [x, y, N - x - y]
print(*ans)


(N, Y) = map(int, input().split())
ans = (-1, -1, -1)
for i in range(N + 1):
	for j in range(N + 1 - i):
		if 1 <= N <= 2000 and 10000 * i + 5000 * j + 1000 * (N - i - j) == Y:
			ans = (i, j, N - i - j)
print(*ans)


(n, yen) = map(int, input().split())
(x, y, z) = (-1, -1, -1)
for i in range(n + 1):
	for j in range(n + 1 - i):
		k = n - i - j
		if i * 10000 + j * 5000 + k * 1000 == yen:
			(x, y, z) = (i, j, k)
print(x, y, z)


import sys
(N, Y) = map(int, input().split())
for i in range(N + 1):
	for j in range(N + 1 - i):
		k = N - i - j
		if 10000 * i + 5000 * j + 1000 * k == Y:
			print(i, j, k)
			sys.exit(0)
else:
	print(-1, -1, -1)


(n, Y) = map(int, input().split())
for x in range(n + 1):
	for y in range(n + 1):
		if 10000 * n - 9000 * x - 5000 * y == Y and x + y <= n:
			print(n - x - y, y, x)
			exit()
print(-1, -1, -1)