Problem D. Dynamic Cinderella

Author:Антон Карабанов   Time limit:1 sec
Input file:Standard input   Memory limit:512 Mb
Output file:Standard output  


In the Brothers Grimm's fairy tale, one of the tests for Cinderella was an episode when the evil stepmother scattered cereals in a heap on the floor and ordered her to sort them out on plates. The cereals vary depending on the version. In one fairy tale, Cinderella was sorting through millet and poppy seeds. In another, she arranged beans and lentils. In the third, barley was separated from oats. There were peas with rice, and buckwheat with millet, and bags of red and white beans. Which version is true is unknown, so in this problem the stepmother formed a bunch of decimal digits and demanded that Cinderella count the number of each digit in the heap.

In total, there are n levels in the heap, at the topmost there is a single digit d, on each next level there is one more digit than at the higher level. For convenience, let's imagine a heap (for n = 4 and d = 8) as shown in the picture.

Heap of numbers was formed by the stepmother according to certain rules. The very first number on the levels starting from the second is equal to the first number on the higher level, increased by 1 and taken modulo 10. For example, the first number on the second level is (8 + 1)% 10 = 9. The first number on the third level is (9 + 1)% 10 = 0, and so on.

The rest of the digits in the heap are formed as follows: take two numbers — to the left in the same level and on a higher level above the number just taken, they are added and the result is taken modulo 10. For example, the second number at the second level is (9 + 8) % 10 = 7.

If Cinderella knew what dynamic programming is, then the rules for filling the heap would look like this:

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.

Input format

Input contains two numbers: n and d.

Output format

Output ten integers — number of digits from 0 to 9 in the heap.


2 ≤ n ≤ 105

1 ≤ d ≤ 9

Sample tests

No. Standard input Standard output
4 8
2 2 0 0 0 0 2 1 1 2

0.118s 0.011s 15