为了收拾旧物,迎接崭新的一年,彻底的房屋大扫除是必须的。
小汤米找到了一个旧多项式,并通过对另一个多项式取模来清理它。但现在他却后悔这么做了……
给定两个整数 p 和 k,找到一个非负整数系数严格小于 k 的多项式 f(x),除以 (x + k) 时余数为 p。即,f(x) = q(x)·(x + k) + p,其中q(x) 是多项式(不一定具有整数系数)。
输入
输入的唯一一行包含两个空格分隔的整数 p 和 k (1 ≤ p ≤ 1018, 2 ≤ k ≤ 2 000)。
输出
如果多项式不存在,则打印单个整数-1,否则输出两行。
在第一行中打印一个非负整数 d — 多项式中的系数数量。
在第二行中打印 d 个空格分隔的整数 a0, a1, ..., ad - 1,描述满足给定要求的多项式 $$f(x) = \sum_{i=0}^{d-1} a_i \cdot x^i$$。对于所有 0 ≤ i ≤ d - 1,并且 ad - 1 ≠ 0,您的输出应满足 0 ≤ ai < k。
如果有多种可能的解决方案,请打印其中任何一个。
示例
输入 #1
46 2
输出 #1
7 0 1 0 0 1 1 1
输入 #2
2018 214
输出 #2
3 92 205 1
注意
在第一个示例中,f(x) = x6 + x5 + x4 + x = (x5 - x4 + 3x3 - 6x2 + 12x - 23)·(x + 2) + 46。
在第二个示例中,f(x) = x2 + 205x + 92 = (x - 9)·(x + 214) + 2018。