Bimokh is Mashmokh's boss. For the following n days he decided to pay to his workers in a new way. At the beginning of each day he will give each worker a certain amount of tokens. Then at the end of each day each worker can give some of his tokens back to get a certain amount of money. The worker can save the rest of tokens but he can't use it in any other day to get more money. If a worker gives back w tokens then he'll get $\lfloor \frac{w \cdot a}{b} \rfloor$ dollars. 

Mashmokh likes the tokens however he likes money more. That's why he wants to save as many tokens as possible so that the amount of money he gets is maximal possible each day. He has n numbers x_1, x_2, ..., x_{n}. Number x_{i} is the number of tokens given to each worker on the i-th day. Help him calculate for each of n days the number of tokens he can save.


-----Input-----

The first line of input contains three space-separated integers n, a, b (1 ≤ n ≤ 10^5; 1 ≤ a, b ≤ 10^9). The second line of input contains n space-separated integers x_1, x_2, ..., x_{n} (1 ≤ x_{i} ≤ 10^9).


-----Output-----

Output n space-separated integers. The i-th of them is the number of tokens Mashmokh can save on the i-th day.


-----Examples-----
Input
5 1 4
12 6 11 9 1

Output
0 2 3 1 1 
Input
3 1 2
1 2 3

Output
1 0 1 
Input
1 1 1
1

Output
0

Difficulty: MEDIUM
Tags: Mathematics

Sorting

Implementation

Greedy algorithms
Skill types: Sorting

Greedy algorithms

Starter code:

Solutions:
from math import *
(n, a, b) = map(int, input().split())
x = list(map(int, input().split()))
ans = [0] * n
for i in range(n):
	ans[i] = x[i] - ceil(int(x[i] * a / b) * b / a)
print(*ans)


(n, a, b) = map(int, input().split())
tokens = [i for i in map(int, input().split())]
for i in tokens:
	print(a * i % b // a, end=' ')


import math
(n, a, b) = map(int, input().split())
arr = list(map(int, input().split()))
results = []
for x in arr:
	rem = x * a % b
	k = math.floor(rem / a)
	results.append(k)
print(' '.join((str(x) for x in results)))


(n, a, b) = map(int, input().split())
t = [w - 1 - (w * a // b * b - 1) // a for w in map(int, input().split())]
print(' '.join(map(str, t)))


(a, b, c) = map(int, input().split())
d = list(map(int, input().split()))
e = []
for i in d:
	e.append(str(i * b % c // b))
print(' '.join(e))


(n, a, b) = map(int, input().split())
v = list(map(int, input().split()))
ans = [0] * n
for i in range(n):
	ans[i] = v[i] * a % b // a
print(*ans)


from collections import Counter
import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
import math
(n, a, b) = map(int, input().split())
arr = list(map(int, input().split()))
for i in range(n):
	x = arr[i] * a // b
	rem = arr[i] - math.ceil(x * b / a)
	print(rem, end=' ')


(n, a, b) = input().split(' ')
(n, a, b) = (int(n), int(a), int(b))
INPUT = [int(x) for x in input().split(' ')]
for w in INPUT:
	res = w * a % b
	res //= a
	print(res, end=' ')


(n, a, b) = map(int, input().split())
t = list(map(int, input().split()))
newlist = []
for x in t:
	newlist += [x * a % b // a]
print(*newlist)


(n, a, b) = input().split()
k = input()
for i in k.split():
	print(int(i) * int(a) % int(b) // int(a), end=' ')


(n, a, b) = map(int, input().split())
for w in map(int, input().split()):
	print(w * a % b // a, end=' ')


(n, a, b) = map(int, input().split())
x = list(map(int, input().split()))
[print(el * a % b // a, end=' ') for el in x]
print('\n')


(n, a, b) = [int(c) for c in input().split()]
days = [int(c) for c in input().split()]
res = []
for i in range(len(days)):
	p = days[i] * a % b
	f1 = int(p // a)
	res.append(f1)
print(' '.join(map(str, res)))


arr = []
arr2 = []
scann = input()
arr = scann.split()
n = int(arr[0])
a = int(arr[1])
b = int(arr[2])
scann = input()
arr2 = scann.split()
aux = []
j = 0
k = 0
l = 0
for i in range(n):
	j = int(arr2[i]) * a
	k = j % b
	l = k / a
	aux.append(int(l))
print(*aux)


from math import ceil
(n, a, b) = map(int, input().split())
l = list(map(int, input().split()))
ans = [0] * n
for i in range(n):
	r1 = l[i] * a // b
	r2 = l[i] - ceil(r1 * b / a)
	ans[i] = r2
for i in ans:
	print(i, end=' ')


def mymod(x, a, b):
	import math
	return x - math.ceil(int(x * a / b)) * b / a
(n, a, b) = map(int, input().strip().split())
x = list(map(int, input().split()))
for q in x:
	print(int(mymod(q, a, b)), end=' ')


import math
ip = input('')
ip = ip.split(' ')
(n, a, b) = ip
(n, a, b) = (int(n), int(a), int(b))
l = map(int, input().split())
g = math.gcd(a, b)
(a, b) = (a / g, b / g)
for i in l:
	tok = i * a // b
	print(int(i - math.ceil(tok * b / a)), end=' ')
print()


(n, a, b) = map(int, input().split())
for x in map(int, input().split()):
	print(x - (x * a // b * b + a - 1) // a)


import sys
from fractions import gcd
(n, a, b) = list(map(int, input().split()))
g = gcd(a, b)
a //= g
b //= g
x = list(map(int, input().split()))
ans = []
for xi in x:
	max = xi * a // b
	(L, R) = (0, xi)
	while L < R:
		M = (L + R) // 2
		if M * a // b < max:
			L = M + 1
		else:
			R = M
	ans.append(str(xi - L))
print(' '.join(ans))


(n, a, b) = map(int, input().split())
l = [int(i) for i in input().split()]
from math import ceil as ceil, floor as floor
for i in l:
	rem = i * a % b
	print(floor(rem / a), end=' ')


def main():
	(n, a, b) = map(int, input().split())
	ar = list(map(int, input().split()))
	ans = [0] * n
	for i in range(n):
		ans[i] = ar[i] * a % b // a
	print(*ans)
main()


R = lambda : map(int, input().split())
(n, a, b) = R()
print(' '.join(map(str, (w * a % b // a for w in R()))))


import math
(_, a, b) = list(map(int, input().split()))
jet = list(map(int, input().split()))

def jtd(w):
	j = w * a % b
	return j // a
for i in jet:
	print(int(jtd(i)), end=' ')
print()


import math
(n, a, b) = map(int, input().split())
arr = list(map(int, input().split()))
for i in range(n):
	x = math.floor(arr[i] * a / b)
	arr[i] -= math.ceil(x * b / a)
print(*arr)


class InputHandlerObject(object):
	inputs = []

	def getInput(self, n=0):
		res = ''
		inputs = self.inputs
		if not inputs:
			inputs.extend(input().split(' '))
		if n == 0:
			res = inputs[:]
			inputs[:] = []
		while n > len(inputs):
			inputs.extend(input().split(' '))
		if n > 0:
			res = inputs[:n]
			inputs[:n] = []
		return res
InputHandler = InputHandlerObject()
g = InputHandler.getInput
(n, a, b) = g()
(n, a, b) = (int(n), int(a), int(b))
c = [int(x) for x in g()]
r = []
for i in c:
	r.append(str(i * a % b // a))
print(' '.join(r))


import sys
[n, a, b] = map(int, sys.stdin.readline().split())
buttons = map(int, sys.stdin.readline().split())
res = []
for x in buttons:
	money = int(1.0 * x * a / b)
	rest = x - 1.0 * money * b / a
	res.append(int(rest))
print(' '.join(map(str, res)))


(n, a, b) = map(int, input().split())
arr = list(map(int, input().split()))
for i in range(n):
	arr[i] = arr[i] * a % b // a
print(arr[0], end='')
for i in range(1, len(arr)):
	print('', arr[i], end='')
print('')


from math import floor
(n, a, b) = map(int, input().split())
arr = list(map(int, input().split()))
for i in range(int(n)):
	earn = floor(arr[i] * a / b)
	arr[i] = int(arr[i] - earn / a * b)
print(*arr)


import sys
f = sys.stdin.readline
(n, a, b) = map(int, f().strip().split())
x = [int(v) for v in f().strip().split()]
out = []
for v in x:
	out.append(v * a % b // a)
print(' '.join(map(str, out)))


import math

class CodeforcesTask415BSolution:

	def __init__(self):
		self.result = ''
		self.n_a_b = []
		self.tokens = []

	def read_input(self):
		self.n_a_b = [int(x) for x in input().split(' ')]
		self.tokens = [int(x) for x in input().split(' ')]

	def process_task(self):
		result = []
		for x in range(self.n_a_b[0]):
			result.append(self.tokens[x] * self.n_a_b[1] % self.n_a_b[2] // self.n_a_b[1])
		self.result = ' '.join([str(x) for x in result])

	def get_result(self):
		return self.result
Solution = CodeforcesTask415BSolution()
Solution.read_input()
Solution.process_task()
print(Solution.get_result())


(n, a, b) = map(int, input().strip().split(' '))
L = list(map(int, input().split(' ')))
for i in range(n):
	s = L[i]
	res = s * a // b
	j = int(s - b * res / a)
	print(j)


def main():
	(n, a, b) = list(map(int, input().split()))
	x_list = list(map(int, input().split()))
	res = list()
	for x in x_list:
		res.append(str(x * a % b // a))
	print(' '.join(res))
main()


R = lambda : map(int, input().split())
(n, a, b) = R()
for x in R():
	print(a * x % b // a, end=' ')


import sys
import string
import math
from collections import defaultdict
from functools import lru_cache
from collections import Counter

def mi(s):
	return map(int, s.strip().split())

def lmi(s):
	return list(mi(s))

def tmi(s):
	return tuple(mi(s))

def mf(f, s):
	return map(f, s)

def lmf(f, s):
	return list(mf(f, s))

def js(lst):
	return ' '.join((str(d) for d in lst))

def line():
	return sys.stdin.readline().strip()

def linesp():
	return line().split()

def iline():
	return int(line())

def dist(x, y):
	return ((x[0] - y[0]) ** 2 + (x[1] - y[1]) ** 2) ** 0.5

def bin_search(a, b, n):
	form = lambda x: math.floor(x / b * a)
	looking = form(n)
	hi = n
	lo = 0
	while lo <= hi:
		if lo == hi:
			return lo
		elif lo == hi - 1:
			if form(lo) == looking:
				return lo
			else:
				return hi
		mid = (hi + lo) // 2
		if form(mid) < looking:
			lo = mid
		else:
			hi = mid

def main(a, b, arr):
	div = b / a
	final = []
	for n in arr:
		looking = math.floor(a * n / b)
		ans = math.ceil(b * (looking / a))
		final.append(n - ans)
	print(js(final))
(_, a, b) = mi(line())
arr = lmi(line())
main(a, b, arr)


import math
(n, a, b) = map(int, input().split())
xlist = [int(x) for x in input().split()]
savestring = ''
for i in range(n):
	maxmoney = math.floor(xlist[i] * a / b)
	saves = xlist[i] - math.ceil(maxmoney * b / a)
	savestring += str(saves) + ' '
print(savestring)


import functools
import math
import sys

def In():
	return map(int, sys.stdin.readline().split())
input = sys.stdin.readline

def mashtok():
	(n, a, b) = In()
	ans = []
	for i in input().split():
		ans.append(str(int(i) * a % b // a))
	print(' '.join(ans))
mashtok()


(n, a, b) = map(int, input().split())
lis = list(map(int, input().split()))
for i in lis:
	x = i * a % b
	print(int(x / a))


def binary_search(n, a, b):
	l = 0
	r = n
	maxx = n * a // b
	while l < r:
		mid = (l + r) // 2
		if mid * a // b < maxx:
			l = mid + 1
		else:
			r = mid
	return l
(n, a, b) = map(int, input().split())
l1 = list(map(int, input().split()))
a1 = []
for i in l1:
	ans1 = binary_search(i, a, b)
	a1.append(i - ans1)
print(*a1)


(n, a, b) = map(int, input().split())
x = list(map(int, input().split()))
for each in x:
	print(each * a % b // a)


(n, a, b) = map(int, input().split())
w = list(map(int, input().split()))
w = [x * a % b // a for x in w]
print(' '.join(map(str, w)))


[n, a, b] = [int(x) for x in input().split()]
amount = [int(x) for x in input().split()]
res = [0] * n
curr = 0
for (i, day) in enumerate(amount):
	s = int(day * a / b)
	tmp = int(s * b / a) if s * b % a == 0 else int(s * b / a) + 1
	res[i] = day + curr - tmp
print(' '.join(map(str, res)))


(n, a, b) = map(int, input().split())
p = list(map(int, input().split()))
for i in range(n):
	print(p[i] * a % b // a, end=' ')


(n, a, b) = map(int, input().split())
x = list(map(int, input().split()))
ans = []
for i in range(n):
	d = x[i] * a // b
	ans.append((x[i] * a - d * b) // a)
print(*ans)


import math
(n, a, b) = list(map(int, input().split()))
x = [int(i) for i in input().split()]
ans = [0] * n
for (i, w) in enumerate(x):
	r = w * a // b
	ans[i] = w - math.ceil(r * b / a)
	if ans[i] < 0:
		ans[i] = 0
print(' '.join((str(i) for i in ans)))


from math import floor
(n, a, b) = map(int, input().split())
x = [int(c) for c in input().split()]
ans = [int(i - floor(i * a / b) * b / a) for i in x]
print(*ans)


import math
x = input('').split(' ')
x = [int(y) for y in x]
a = x[0]
b = x[1]
c = x[2]
l = input('').split(' ')
str2 = ''
l = [int(y) for y in l]
for g in range(0, a):
	t = l[g]
	if t * b / c == math.floor(t * 2 / c):
		str2 = str2 + '0 '
	else:
		ttt = t * b
		equate = math.floor(ttt / c)
		if equate * c % b == 0:
			unawesome = equate * c / b
			str2 = str2 + str(int(t - unawesome))
			str2 = str2 + ' '
		else:
			unawesome = math.floor(equate * c / b) + 1
			str2 = str2 + str(int(t - unawesome))
			str2 = str2 + ' '
print(str2)


__author__ = 'Lipen'

def main():
	(n, a, b) = map(int, input().split())
	x = list(map(int, input().split()))
	answer = list(map(lambda i: int(x[i] - int(x[i] * a / b) / a * b), range(n)))
	print(' '.join(map(str, answer)))
main()


(n, a, b) = map(int, input().split())
coins = list(map(int, input().split()))
for i in range(n):
	coins[i] = coins[i] * a % b // a
print(*coins)


from fractions import Fraction
z = [int(i) for i in input().split()]
(n, a, b) = (z[0], z[1], z[2])
x = [int(i) for i in input().split()]
c = Fraction(a, b)
a = c.numerator
b = c.denominator
y = [0] * n
for i in range(n):
	if x[i] * a // b == 0:
		y[i] = x[i]
	else:
		zz = x[i] % b
		y[i] = zz * a % b // a
print(' '.join([str(j) for j in y]))


(n, a, b) = map(int, input().split())
x = [int(i) for i in input().split()]

def find_index(n):
	l = 0
	r = n
	while l < r:
		mid = (l + r) // 2
		if mid * a // b == r * a // b:
			r = mid
		else:
			l = mid + 1
	return r
for i in range(n):
	print(x[i] - find_index(x[i]), end=' ')
print()


def single_integer():
	return int(input())

def multi_integer():
	return map(int, input().split())

def string():
	return input()

def multi_string():
	return input().split()
import math
(n, a, b) = multi_integer()
tokens = multi_integer()
for i in tokens:
	x = i * a // b
	k = i - math.ceil(x * b / a)
	print(k, end=' ')


import sys

def ints_input():
	return [int(i) for i in sys.stdin.readline().strip('\n').split(' ')]

def print_list(arr):
	sys.stdout.writelines((str(x) + ' ' for x in arr))
	sys.stdout.write('\n')

def fast_input(type=str):
	return type(sys.stdin.readline().strip('\n'))
(n, a, b) = ints_input()
arr = ints_input()
for i in arr:
	print(i * a % b // a, end=' ')


import sys
import math
import itertools
import functools
import collections
import operator
import fileinput
import copy
ORDA = 97

def ii():
	return int(input())

def mi():
	return map(int, input().split())

def li():
	return [int(i) for i in input().split()]

def lcm(a, b):
	return abs(a * b) // math.gcd(a, b)

def revn(n):
	return str(n)[::-1]

def dd():
	return collections.defaultdict(int)

def ddl():
	return collections.defaultdict(list)

def sieve(n):
	if n < 2:
		return list()
	prime = [True for _ in range(n + 1)]
	p = 3
	while p * p <= n:
		if prime[p]:
			for i in range(p * 2, n + 1, p):
				prime[i] = False
		p += 2
	r = [2]
	for p in range(3, n + 1, 2):
		if prime[p]:
			r.append(p)
	return r

def divs(n, start=1):
	r = []
	for i in range(start, int(math.sqrt(n) + 1)):
		if n % i == 0:
			if n / i == i:
				r.append(i)
			else:
				r.extend([i, n // i])
	return r

def divn(n, primes):
	divs_number = 1
	for i in primes:
		if n == 1:
			return divs_number
		t = 1
		while n % i == 0:
			t += 1
			n //= i
		divs_number *= t

def prime(n):
	if n == 2:
		return True
	if n % 2 == 0 or n <= 1:
		return False
	sqr = int(math.sqrt(n)) + 1
	for d in range(3, sqr, 2):
		if n % d == 0:
			return False
	return True

def convn(number, base):
	newnumber = 0
	while number > 0:
		newnumber += number % base
		number //= base
	return newnumber

def cdiv(n, k):
	return n // k + (n % k != 0)

def ispal(s):
	for i in range(len(s) // 2 + 1):
		if s[i] != s[-i - 1]:
			return False
	return True
(n, a, b) = mi()
arr = li()
ans = []
for i in arr:
	ans.append(a * i % b // a)
print(*ans)


from math import gcd, floor

def f(a, b, w):
	x = w * a // b * b
	return floor((w * a - x) // a)
(n, a, b) = input().split(' ')
(a, b, n) = (int(a), int(b), int(n))
r = [str(f(a, b, int(i))) for i in input().split(' ')]
print(' '.join(r))


f = lambda : map(int, input().split())
(n, a, b) = f()
print(' '.join([str(int(x * a % b / a)) for x in f()]))


def solve(w, a, b):
	q = list()
	for i in w:
		k = i * a % b
		q.append(k // a)
	return q
(n, a, b) = map(int, input().split())
w = map(int, input().split())
res = map(str, solve(w, a, b))
print(' '.join(res))


import math
(n, a, b) = input().split(' ')
(n, a, b) = (int(n), int(a), int(b))
INPUT = [int(x) for x in input().split(' ')]
for w in INPUT:
	res = w * a / b
	if res == 0:
		print(w, end=' ')
	elif res == int(res):
		print('0', end=' ')
	else:
		ans = w - math.ceil(int(res) * b / a)
		print(ans, end=' ')


import math
(n, a, b) = map(int, input().split())
for i in input().split():
	print(int(i) - math.ceil((int(i) * a - int(i) * a % b) / a), end=' ')


(n, a, b) = list(map(int, input().split()))
coins = list(map(int, input().split()))
result = [str(x * a % b // a) for x in coins]
print(' '.join(list(result)))


(n, a, b) = map(int, input().split())
arr = [int(z) for z in input().split()]
res = []
for i in arr:
	res.append(i * a % b // a)
print(*res)


def Mashmokh(arr, a, b):
	arr1 = []
	for i in arr:
		if i % (a * b) == 0:
			arr1.append(0)
		else:
			resultado = i - b / a * (i * a // b)
			arr1.append(int(resultado))
	arr_aux = ' '.join(map(str, arr1))
	return arr_aux
(a1, a2, a3) = input().split()
n = int(a1)
a = int(a2)
b = int(a3)
arr = list(map(int, input().strip().split()))
print(Mashmokh(arr, a, b))


def arr_inp(n):
	if n == 1:
		return [int(x) for x in stdin.readline().split()]
	elif n == 2:
		return [float(x) for x in stdin.readline().split()]
	else:
		return [str(x) for x in stdin.readline().split()]
from sys import stdin
from math import floor
(n, a, b) = arr_inp(1)
arr = arr_inp(1)
for i in arr:
	print(floor(a * i % b / a), end=' ')


t = input().split()
n = int(t[0])
a = int(t[1])
b = int(t[2])
for x in input().split():
	w = int(x) * a % b
	w //= a
	print(w, end=' ')


(n, a, b) = map(int, input().split())
for i in input().split():
	i = int(i)
	r = b / a
	x = i // r
	print(int(i - r * x), end=' ')


import sys
import math
import collections
import bisect

def get_ints():
	return map(int, sys.stdin.readline().strip().split())

def get_list():
	return list(map(int, sys.stdin.readline().strip().split()))

def get_string():
	return sys.stdin.readline().strip()
for t in range(1):
	(n, a, b) = get_ints()
	arr = get_list()
	ans = []
	for i in arr:
		num = a * i
		val = num // b
		rem = i - math.ceil(val * b / a)
		ans.append(rem)
	print(*ans)


import math
(n, a, b) = map(int, input().split())
x = list(map(int, input().split()))
ans = []
for i in x:
	s = i * a // b
	ans.append(i - math.ceil(s * b / a))
print(*ans)


(n, a, b) = map(int, input().split())
l = list(map(int, input().split()))
out = []
for i in range(n):
	out.append(str(l[i] * a % b // a))
print(' '.join(out))


(n, a, b) = map(int, input().split())
coins = map(int, input().split())
result = map(lambda x: str(x * a % b // a), coins)
print(' '.join(list(result)))


import math

def f2(x, a, b):
	t = math.floor(x * a / b)
	r = x % t if t > 0 else x
	return r

def f(x, a, b):
	r = x * a % b
	return r
(n, a, b) = map(int, input().split(' '))
x = list(map(int, input().split(' ')))
r = [int(x[i] * a % b / a) for i in range(len(x))]
print(' '.join(map(str, r)))


def main():
	(n, a, b) = map(int, input().split())
	l = list(map(int, input().split()))
	for (i, x) in enumerate(l):
		l[i] = x * a % b // a
	print(' '.join(map(str, l)))
main()


import sys
(n, a, b) = map(int, sys.stdin.readline().split())
w_arr = map(int, sys.stdin.readline().split())
print(' '.join(map(str, [w * a % b // a for w in w_arr])))


import math
(n, a, b) = map(int, input().split())
l = list(map(int, input().split()))
for e in l:
	z = e * a // b
	s = e - math.ceil(z * b / a)
	print(s, end=' ')
print()


import math
(n, a, b) = map(int, input().split())
our_list = list(map(int, input().split()))
for i in range(n):
	print(our_list[i] - math.ceil(our_list[i] * a // b * b / a), end=' ')


from math import *
(n, a, b) = list(map(int, input().split()))
l = list(map(int, input().split()))
for i in l:
	x = i - ceil(i * a // b * b / a)
	print(x, end=' ')
print()