In order to put away old things and welcome a fresh new year, a thorough cleaning of the house is a must.

Little Tommy finds an old polynomial and cleaned it up by taking it modulo another. But now he regrets doing this...

Given two integers p and k, find a polynomial f(x) with non-negative integer coefficients strictly less than k, whose remainder is p when divided by (x + k). That is, f(x) = q(x)·(x + k) + p, where q(x) is a polynomial (not necessarily with integer coefficients).


-----Input-----

The only line of input contains two space-separated integers p and k (1 ≤ p ≤ 10^18, 2 ≤ k ≤ 2 000).


-----Output-----

If the polynomial does not exist, print a single integer -1, or output two lines otherwise.

In the first line print a non-negative integer d — the number of coefficients in the polynomial.

In the second line print d space-separated integers a_0, a_1, ..., a_{d} - 1, describing a polynomial $f(x) = \sum_{i = 0}^{d - 1} a_{i} \cdot x^{i}$ fulfilling the given requirements. Your output should satisfy 0 ≤ a_{i} < k for all 0 ≤ i ≤ d - 1, and a_{d} - 1 ≠ 0.

If there are many possible solutions, print any of them.


-----Examples-----
Input
46 2

Output
7
0 1 0 0 1 1 1

Input
2018 214

Output
3
92 205 1



-----Note-----

In the first example, f(x) = x^6 + x^5 + x^4 + x = (x^5 - x^4 + 3x^3 - 6x^2 + 12x - 23)·(x + 2) + 46.

In the second example, f(x) = x^2 + 205x + 92 = (x - 9)·(x + 214) + 2018.

Difficulty: HARD
Tags: Mathematics

Starter code:

Solutions:
(p, k) = map(int, input().split())
l = []
while p:
	l.append((p % k + k) % k)
	p = (p % k - p) // k
print(len(l))
for i in l:
	print(i, end=' ')


l = []

def f(p, k):
	if p == 0:
		return
	r = p % k
	q = (p - r) // -k
	l.append(r)
	f(q, k)
(p, k) = map(int, input().split())
f(p, k)
print(len(l))
print(*l)


def solve(n, k):
	if n == 0:
		return []
	x = n % k
	return [x] + solve(-(n - x) // k, k)
(n, k) = map(int, input().split())
a = solve(n, k)
print(len(a))
print(*a)


[p, k] = [int(x) for x in input().split()]
d = 1
res = []
while p:
	if d % 2 == 1:
		kek = k
		res.append(str(p % kek))
		p //= kek
	else:
		kek = k
		lol = kek - p % kek
		while lol >= kek:
			lol -= kek
		res.append(str(lol))
		p = (p + lol) // kek
	d += 1
print(len(res))
s = ' '
print(s.join(res))


(p, k) = map(int, input().split())
t = []
while p:
	s = (k - 1 - p) // k
	t.append(p + s * k)
	p = s
print(len(t), *t)


(p, k) = map(int, input().split())
r = [p % k]
p = p // k
while 1:
	if p <= 0 and -p < k:
		break
	(p, q) = divmod(-p, k)
	r.append(q)
if p:
	r.append(-p)
print(len(r))
print(*r, sep=' ')


(p, k) = list(map(int, input().split()))
arr = []
while p:
	(a, b) = divmod(p, -k)
	if b < 0:
		a += 1
		b += k
	p = a
	arr.append(str(b))
print(len(arr))
print(' '.join(arr))


(p, k) = list(map(int, input().split()))
ans = None
for x in range(0, k):
	res = []
	a = p
	used = set()
	ok = 1
	while 1:
		b = (-a + k - 1) // k
		if b == 0:
			res.append(a)
			break
		res.append(a + k * b)
		a = b
		if a in used:
			ok = 0
			break
		used.add(a)
	if ok:
		ans = res
		break
if ans is None:
	print(-1)
else:
	print(len(ans))
	print(*ans)


(p, k) = map(int, input().split())
coeff = [1]
maxi = k - 1
kk = k * k
while maxi < p:
	for i in range(2):
		coeff.append(0)
	maxi += kk * (k - 1)
	kk *= k * 2
n = len(coeff)
powk = [0 for i in range(n)]
pos = [0 for i in range(n)]
neg = [0 for i in range(n)]
powk[0] = 1
for i in range(1, n):
	powk[i] = powk[i - 1] * k
pos[0] = k - 1
neg[0] = 0
for i in range(1, n):
	if i % 2 == 0:
		pos[i] = pos[i - 1] + powk[i] * (k - 1)
		neg[i] = neg[i - 1]
	else:
		pos[i] = pos[i - 1]
		neg[i] = neg[i - 1] + powk[i] * (k - 1)
for i in range(n - 1, -1, -1):
	if i % 2 == 0:
		coeff[i] = (p + neg[i]) // powk[i]
		p -= coeff[i] * powk[i]
	else:
		coeff[i] = (-p + pos[i]) // powk[i]
		p += coeff[i] * powk[i]
ng = False
for i in range(n):
	if coeff[i] >= k:
		ng = True
if ng:
	print(-1)
else:
	d = n
	for i in range(n - 1, -1, -1):
		if coeff[i] == 0:
			d = d - 1
		else:
			break
	print(d)
	print(' '.join(map(str, coeff[0:d])))


(p, k) = map(int, input().split())
r = []
while p:
	r.append(p % k)
	p = -(p // k)
print(len(r))
print(*r, sep=' ')


def fu(a, b):
	r = a % b
	if r < 0:
		r = a % b - b
	return [(a - r) // b, r]
(p, k) = list(map(int, input().split()))
s = []
while 1 > 0:
	a = fu(p, -k)
	if a[0] == 0:
		if a[1] != 0:
			s.append(a[1])
		break
	else:
		s.append(a[1])
		p = a[0]
print(len(s))
print(*s)


(x, k) = map(int, input().split())
answer = []

def findBit(l, r, x, pwk):
	for i in range(0, k):
		if l + pwk * i <= x and x <= pwk * i + r:
			return i
	return 0

def rec(l, r, pwk):
	nonlocal x
	nonlocal k
	nonlocal answer
	nk = pwk * (k - 1)
	stepL = min(0, nk)
	stepR = max(0, nk)
	nl = l + stepL
	nr = r + stepR
	if nl <= x and x <= nr:
		answer.append(findBit(l, r, x, pwk))
		x -= answer[-1] * pwk
	else:
		rec(nl, nr, pwk * -k)
		answer.append(findBit(l, r, x, pwk))
		x -= answer[-1] * pwk
rec(0, 0, 1)
print(len(answer))
for x in reversed(answer):
	print(x, end=' ')
print()


(p, k) = map(int, input().split())
L = [0] * 100
R = [0] * 100
ans = [0] * 100
for i in range(0, 100):
	if i == 0:
		L[0] = 0
		R[0] = k - 1
	elif i % 2:
		L[i] = L[i - 1] + (-k) ** i * (k - 1)
		R[i] = R[i - 1]
	else:
		L[i] = L[i - 1]
		R[i] = R[i - 1] + (-k) ** i * (k - 1)
	if L[i] <= p <= R[i]:
		for j in range(i, -1, -1):
			if j == 0:
				ans[j] = p
			else:
				while not L[j - 1] <= p <= R[j - 1]:
					ans[j] += 1
					p -= (-k) ** j
		print(i + 1)
		print(' '.join(map(str, ans[:i + 1])))
		exit(0)
print(-1)


(p, k) = list(map(int, input().split()))

def convert(num, base):
	res = []
	if num == 0:
		res = [0]
	else:
		res = []
		while num != 0:
			(num, rem) = divmod(num, -base)
			if rem < 0:
				(num, rem) = (num + 1, rem + base)
			res.append(rem)
	return res
res = convert(p, k)
print(len(res))
print(' '.join([str(x) for x in res]))


(p, k) = map(int, input().split())
l = [0]
r = [0]
cp = [1]
coef = []
for deg in range(1, 2333):
	l.append(l[-1])
	r.append(r[-1])
	if cp[-1] > 0:
		r[-1] += cp[-1] * (k - 1)
	else:
		l[-1] += cp[-1] * (k - 1)
	if p <= r[-1] and p >= l[-1]:
		coef = [0] * deg
		break
	cp.append(cp[-1] * -k)
cv = p
for deg in range(len(coef), 0, -1):
	if cv >= l[deg - 1] and cv <= r[deg - 1]:
		continue
	elif cv > r[deg - 1]:
		coef[deg - 1] = (cv - r[deg - 1]) // cp[deg - 1]
		if (cv - r[deg - 1]) % cp[deg - 1] != 0:
			coef[deg - 1] += 1
		cv -= cp[deg - 1] * coef[deg - 1]
	elif cv < l[deg - 1]:
		coef[deg - 1] = (l[deg - 1] - cv) // -cp[deg - 1]
		if (l[deg - 1] - cv) % -cp[deg - 1] != 0:
			coef[deg - 1] += 1
		cv -= cp[deg - 1] * coef[deg - 1]
print(len(coef))
print(' '.join(map(str, coef)))


(a, b) = map(int, input().split())
c = -(a // b)
out = [a % b]
while True:
	out.append(c % b)
	c = -(c // b)
	if out[-1] == c == 0:
		break
print(len(out) - 1)
for i in out[:-1]:
	print(i, end=' ')
print()


(p, k) = map(int, input().split())
l = []
d = 0
sign = +1
while True:
	t = []
	st = sign * k ** d
	for j in range(k):
		t.append(j * st)
	l.append(t)
	d += 1
	sign = -sign
	if t[-1] >= p:
		break
a = 0
b = 0
neg = []
pos = []
for i in range(d):
	a += min(l[i][0], l[i][-1])
	b += max(l[i][0], l[i][-1])
	neg.append(a)
	pos.append(b)
ans = []
done = True
for i in range(d - 1, -1, -1):
	if i == 0:
		if p in l[i]:
			ans.append(p)
		else:
			done = False
		break
	for j in range(k):
		if l[i][j] + neg[i - 1] <= p and l[i][j] + pos[i - 1] >= p:
			ans.append(j)
			p -= l[i][j]
			break
if done and len(ans) == d:
	while ans[0] == 0:
		ans = ans[1:]
		d -= 1
	print(d)
	for i in range(d - 1, -1, -1):
		print(ans[i], end=' ')
else:
	print(-1)


(p, k) = map(int, input().split())
k = -k
a = []
while p != 0:
	r = p % k
	p //= k
	if r < 0:
		r += -k
		p += 1
	a.append(r)
print(len(a))
print(' '.join(map(str, a)))


def solve(n, p, k):
	P = p
	cf = 1
	a = [0] * n
	for i in range(n):
		if i & 1:
			p += cf * (k - 1)
			a[i] -= k - 1
		cf *= k
	for i in range(n):
		a[i] += p % k
		p //= k
	if p:
		return
	for i in range(n):
		if i & 1:
			a[i] *= -1
	cf = 1
	p = P
	for i in range(n):
		if a[i] < 0 or a[i] >= k:
			return
		if i & 1:
			p += a[i] * cf
		else:
			p -= a[i] * cf
		cf *= k
	if p:
		return
	print(len(a))
	print(*a)
	exit(0)
(p, k) = map(int, input().split())
for i in range(100):
	if k ** i > 1 << 100:
		break
	solve(i, p, k)
print(-1)


(p, k) = map(int, input().split())
ans = []
while p != 0:
	ans.append(p % k)
	p //= k
	p *= -1
print(len(ans))
print(*ans)


(p, k) = map(int, input().split())
if p < k:
	print(1)
	print(p)
else:
	ans = [p]
	cur = p
	while cur < 0 or cur >= k:
		cur = -(cur // k)
		ans.append(cur)
	arr = []
	for i in range(1, len(ans)):
		arr.append(str(k * ans[i] + ans[i - 1]))
	arr.append(str(ans[-1]))
	print(len(arr))
	print(' '.join(arr))


(p, k) = map(int, input().split())
a = []
while p != 0:
	t = p % k
	a.append(t)
	p = -((p - t) // k)
print(len(a))
a = list(map(str, a))
print(' '.join(a))


(p, k) = list(map(int, input().split()))
n = 0
cur = 1
ans = [0 for i in range(100)]
while True:
	tmp = p
	for i in range(n + 1):
		x = (p % k + k) % k
		ans[i] = x
		p = -(p - x) // k
	if p == 0 and ans[n] != 0:
		print(n + 1)
		for i in range(n + 1):
			print(ans[i])
		break
	cur *= k * k
	n += 2
	p = tmp


(n, a) = list(map(int, input().split()))
ar = []
j = 1
while n != 0:
	q = n % a
	n //= a
	n = -1 * n
	ar.append(q)
print(len(ar))
for i in range(len(ar)):
	print(ar[i])


def converttobase(n, b):
	if -1 <= b <= 1:
		return 'INVALID INPUT'
	elif b > 1:
		L = []
		while n != 0:
			L.append(str(n % b))
			n = n // b
		return L
	else:
		L = []
		while n != 0:
			if n % b < 0:
				x = -b + n % b
				L.append(x)
				n = 1 + n // b
			else:
				L.append(n % b)
				n = n // b
		return L
pk = input().split()
p = int(pk[0])
k = int(pk[1])
s = converttobase(p, -k)
print(len(s))
print(*s)


import sys
inp = input().split()
p = int(inp[0])
k = int(inp[1])
r = 0
pow = 1
while 1:
	if r % 2 == 0 and pow >= p:
		break
	r = r + 1
	pow = pow * k
i = r
ans = ''
while i >= 0:
	j = 0
	s = 0
	x = pow // k
	while x > 0:
		s = s + (k - 1) * x
		x = x // k // k
	if i == 0:
		j = p
	elif i % 2 == 0:
		while p - pow * j > 0 and p - pow * (j + 1) >= -s:
			j = j + 1
		p = p - pow * j
	else:
		while p + pow * j < 0 and p + pow * (j + 1) <= s:
			j = j + 1
		p = p + pow * j
	if j != 0 or ans != '':
		ans = str(j) + ' ' + ans
	else:
		r = r - 1
	i = i - 1
	pow = pow // k
print(r + 1)
print(ans)


def negaternary(i, k):
	if i == 0:
		digits = [0]
	else:
		digits = []
		while i != 0:
			(i, remainder) = divmod(i, -k)
			if remainder < 0:
				(i, remainder) = (i + 1, remainder + k)
			digits.append(remainder)
	return digits
(p, k) = map(int, input().split())
ans = negaternary(p, k)
while ans[-1] == 0:
	ans = ans[::-1]
print(len(ans))
print(*ans)


(p, k) = list(map(int, input().split()))
a = []
for i in range(99):
	v = p % k
	if v == 0 or i % 2 == 0:
		a.append(v)
	else:
		a.append(k - v)
		p += k
	p //= k
	if p == 0:
		break
print(len(a))
print(' '.join(list(map(str, a))))


(p, k) = map(int, input().split())
t = []
while p:
	t.append(p % k)
	p = -(p // k)
print(len(t), *t)


(p, k) = map(int, input().split())
num = [0] * 64
sum = 0
c = 0
power = k - 1
while sum < p:
	sum += power
	power *= k * k
	c += 2
print(c - 1)
i = 0
p = sum - p
while p > 0:
	num[i] = p % k
	p //= k
	i += 1
for i in range(c - 1):
	if i % 2 == 0:
		print(k - 1 - num[i], end=' ')
	else:
		print(num[i], end=' ')


(p, k) = map(int, input().split())
a = ''
cnt = 0
while p != 0:
	cnt += 1
	a += str(p % k) + ' '
	p -= p % k
	p //= -k
print(cnt)
print(a)


(p, k) = (int(x) for x in input().split())
rev_p_digits = []
p2 = p
curr_pow = 1
curr_k_pow = 1
i = 0
while p2 > 0:
	curr_pow += 1
	curr_k_pow *= k
	if curr_pow % 2 == 1:
		rev_p_digits.append((k - p2 % k) % k)
		p2 += rev_p_digits[-1]
	else:
		rev_p_digits.append(p2 % k)
	p2 //= k
print(len(rev_p_digits))
print(*rev_p_digits)


(p, k) = map(int, input().split(' '))
a = []
while p:
	a.append(p % k)
	p = -(p // k)
print(len(a))
print(' '.join((str(a[i]) for i in range(len(a)))))


(p, k) = input().strip().split(' ')
flag = 1
p = int(p)
k = int(k)
A = []
B = []
k = -k
while p != 0:
	A.append(p % k)
	p //= k
	if A[-1] < 0:
		p += 1
for i in A:
	if i < 0:
		B.append(i - k)
	else:
		B.append(i)
print(len(B))
for i in B:
	print(i, end=' ')


s = input()
(p, k) = list(map(int, s.split()))
res = []
f = True
while p != 0:
	if f:
		n = p % k
		m = (p - n) // k
		f = False
	else:
		n = -p % k
		m = (p + n) // k
		f = True
	res.append(n)
	p = m
print(len(res))
print(' '.join(list(map(str, res))))