Подільність біноміальних коефіцієнтів

Позначимо , де 0 ≤ i ≤ n и n, i - цілі числа. Вам задано натуральне число n і просте число p. Позначимо через k найбільше ціле невід'ємне число, для якого p^k ≤ n. Далі позначимо для j ≥ 0 через a_j кількість чисел i Є {0, 1, ..., n}, для яких C^i_n ділиться на p^j, але не ділиться на p^{j+1}. Легко перевірити, що a_j = 0 при j > k. Тому від вас вимагається знайти числа a_0, a_1, ..., a_k.

Вхідні дані

У єдиному рядку вхідного файлу задано натуральне число n ≤ 10^18 і просте число p < 10^18.

Вихідні дані

У єдиний рядок вихідного файлу виведіть через пропуск числа a_0, a_1, ..., a_k.

Приклади