Divisibility of binomial coefficients

Let us denote , where 0 ≤ i ≤ n and n, i are integer numbers. You are given a positive integer n and a prime p. We denote by k the greatest nonnegative integer such that inequality p^k ≤ n holds. Then we denote by a_j (j ≥ 0) the number of integers i from {0, 1, ..., n} such that C^i_n is divisible by p^j, but is not divisible by p^{j+1}. It is easy to verify that a_j = 0 for j > k. Therefore you are required to find numbers a_0, a_1, ..., a_k.

Input

The only line of the input file consists of a positive integer n ≤ 10^18 and a prime p < 10^18.

Output

In the only line of the output file write numbers a_0, a_1, ..., a_k separated by spaces.

Examples