G. Uniform Change
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

A cashier has an infinite number of banknotes with denominations $$$1, 2, \ldots, K$$$.

The cashier prefers the stacks of banknotes to end uniformly:

  • Suppose the cashier gives change as $$$C_1$$$ banknotes of denomination $$$1$$$, $$$C_2$$$ banknotes of denomination $$$2$$$, ..., $$$C_K$$$ banknotes of denomination $$$K$$$.
  • The cashier wants the maximum value among $$$C_1, C_2, \ldots, C_K$$$ to be as small as possible.

Help the cashier — find any way to give $$$N$$$ units of change uniformly.

Input

The only line contains two integers $$$N$$$ and $$$K$$$ separated by a space ($$$1 \le N \le 10^{18}$$$; $$$1 \le K \le 2 \cdot 10^5$$$) — the amount of change and the number of different available denominations.

Output

Print $$$K$$$ integers $$$C_1, C_2, \ldots, C_K$$$ ($$$0 \le C_i \le N$$$) separated by spaces — the number of banknotes of denomination $$$i$$$ in a uniform change of $$$N$$$.

The answer must satisfy the following conditions:

  • $$$\sum_{i=1}^{K} C_i \cdot i = N$$$ — exactly $$$N$$$ units of change are given;
  • $$$\max(C_1, C_2, \ldots, C_K)$$$ is minimal among all ways to give change of size $$$N$$$ using denominations from $$$1$$$ to $$$K$$$.

If there are multiple answers satisfying the conditions, print any of them.

Examples
Input
10 3
Output
2 1 2
Input
61 7
Output
1 3 3 3 3 3 0
Note

In the first example, the cashier gave:

  • $$$C_1 = 2$$$ banknotes of denomination $$$1$$$;
  • $$$C_2 = 1$$$ banknote of denomination $$$2$$$;
  • $$$C_3 = 2$$$ banknotes of denomination $$$3$$$.

In total, the cashier gave $$$C_1 \cdot 1 + C_2 \cdot 2 + C_3 \cdot 3 = 10$$$ units.

In the second example, the cashier gave:

  • $$$1$$$ banknote of denomination $$$1$$$;
  • $$$3$$$ banknotes each of denominations $$$2, 3, 4, 5, 6$$$;
  • $$$0$$$ banknotes of denomination $$$7$$$.

In total, the cashier gave $$$1 \cdot 1 + 3 \cdot (2 + 3 + 4 + 5 + 6) + 0 \cdot 7 = 61$$$ units.

Note that this is only one possible answer with $$$\max(C_1, \ldots, C_7) = 3$$$. It can be shown that there is no answer where $$$\max(C_1, \ldots, C_7)$$$ is less than $$$3$$$.