Welcome to ZOJ
Information
Select Problem
Runs
Ranklist
ZOJ Problem Set - 3891
K-hash

Time Limit: 2 Seconds      Memory Limit: 524288 KB

K-hash is a simple string hash function. It encodes a string Sconsist of digit characters into a K-dimensional vector (h0, h1, h2,... , hK-1). If a nonnegative number x occurs in S, then we call x is S-holded. And hi is the number of nonnegative numbers which are S-holded and congruent with i modulo K, for i from 0 to K-1.

For example, S is "22014" and K=3. There are 12 nonnegative numbers are "22014"-holded: 0, 1, 2, 4, 14, 20, 22, 201, 220, 2014, 2201 and 22014. And three of them, 0, 201 and 22014, are congruent with 0 modulo K, so h0=3. Similarly, h1=5 (1, 4, 22, 220 and 2014 are congruent with 1 modulo 3), h2=4(2, 14, 20 and 2201 are congruent with 2 modulo 3). So the 3-hash of "22014" is (3, 5, 4).

Please calculate the K-hash value of the given string S.

Input

There are multiple cases. Each case is a string S and a integer number K. (S is a string consist of '0', '1', '2', ... , '9' , 0< |S| ≤ 50000, 0< K≤ 32)

Output

For each case, print K numbers (h0, h1, h2,... , hK-1 ) in one line.

Sample Input

123456789 10
10203040506007 13
12345678987654321 2
112123123412345123456123456712345678123456789 17
3333333333333333333333333333 11

Sample Output

0 1 2 3 4 5 6 7 8 9
3 5 5 4 3 2 8 3 5 4 2 8 4
68 77
57 58 59 53 49 57 60 55 51 45 59 55 53 49 56 42 57
14 0 0 14 0 0 0 0 0 0 0

Author: ZHOU, Yuchen
Source: ZOJ Monthly, July 2015
Submit    Status