Задача D. Dynamic Cinderella ≡

Условие

В сказке братьев Гримм одним из испытаний для Золушки был эпизод, когда злая мачеха рассыпала крупы в кучу на пол и приказала перебрать их, разложив по тарелочкам. Крупы варьируются в зависимости от версии. В одной сказке Золушка перебирала просо и мак. В другой она раскладывала бобы и чечевицу. В третьей отделяла ячмень от овса. Были и горох с рисом, и гречка с пшеном, и мешки с красной и белой фасолью. Какой из вариантов правдивый — неизвестно, поэтому в этой задаче мачеха сформировала кучу из десятичных цифр и потребовала, чтобы Золушка посчитала количество каждой цифры в куче.

Всего в куче n уровней, на самом верхнем — единственная цифра d, в каждом следующем уровне на одну цифру больше, чем на уровне выше. Для удобства представим кучу (в ней n = 4 и d = 8) так, как указано на рисунке.

Куча цифр сформирована мачехой по определенным правилам. Самое первое число на уровнях, начиная со второго, равно первому числу на уровне выше, увеличенному на 1 и взятому по модулю 10. Например, первое число на втором уровне равно (8 + 1) % 10 = 9. Первое число на третьем уровне равно (9 + 1) % 10 = 0, и так далее.

Остальные цифры в куче формируются следующим образом: берется два числа — левее в том же уровне и на уровне выше над только что взятым числом, складываются и результат берется по модулю 10. Например, второе число на втором уровне равно (9 + 8) % 10 = 7.

Если бы Золушка знала, что такое динамическое программирование, то правила заполнения кучи выглядели бы так:

DP[1, 1] = d;
DP[i, 1] = (DP[i - 1, 1] + 1) % 10;
DP[i, j] = (DP[i, j - 1] + DP[i - 1, j - 1]) % 10.

Ходят слухи, что мачеха способна за секунду определить количество всех цифр в куче и проверить правильность работы Золушки. Вам придется взять на себя роль доброй феи и помочь девушке выполнить это нелегкое задание.

Формат входных данных

Входные данные содержат два целых числа: n и d.

Формат выходных данных

Выведите десять чисел — количество цифр от 0 до 9 в куче.

Ограничения

2 ≤ n ≤ 10⁵

1 ≤ d ≤ 9

Примеры тестов

4 8

2 2 0 0 0 0 2 1 1 2