Khi luyện tập sang dạng bài xử lý xâu cho kì thi học sinh giỏi quốc gia sắp tới, Tuấn gặp một bài toán thú vị như sau:

Cho một xâu ~S = S_1S_2 \dots S_n~ gồm ~n~ kí tự latin viết thường và một số nguyên không âm ~d~, các kí tự của ~S~ được đánh số từ 1 đến ~n~ từ trái qua phải.

Tiếp theo cho một số nguyên ~k~ (~1 \le k \le n~) và tạo ra ~m = \lfloor \frac{n}{k} \rfloor~ xâu độ dài ~k~, xâu thứ ~i~ trong ~m~ xâu là một xâu các kí tự con liên tiếp độ dài ~k~ của ~S~ bắt đầu từ vị trí ~(i - 1) \times k + 1~. Nhắc lại, ~[z]~ là phép toán lấy phần nguyên của số ~z~. Nói một cách khác thì xâu ~S~ được cắt thành ~m~ xâu độ dài ~k~ và bỏ đi phần thừa. Kí hiệu xâu thứ ~i~ trong ~m~ xâu vừa được cắt là ~P^i~, khi đó ~P^i = S_{(i-1) \times k + 1} S_{(i-1) \times k + 2} \dots S_{i \times k}~.

Định nghĩa ~dist(X, Y)~ là khoảng cách Hamming của hai xâu ~X~ và ~Y~ có cùng độ dài ~k~, nghĩa là số vị trí ~u~ (~1 \le u \le k~) mà kí tự thứ ~u~ của ~X~ khác kí tự thứ ~u~ của ~Y~. Gọi ~f(k) = |\{(i, j) | (1 \le i < j \le m) \text{ thoả mãn } dist(P^i, P^j) \le d\}|~. Nói một cách khác, ~f(k)~ là số cặp xâu trong các xâu ~P~ thỏa mãn hai xâu đó khác nhau ở nhiều nhất ~d~ vị trí.

Yêu cầu: Với mỗi giá trị ~k~ từ 1 đến ~n~, hãy tính giá trị ~f(k)~.

Input

• Dòng đầu tiên chứa hai số nguyên ~n~ (~1 \le n \le 5 \times 10^4~) và ~d~ (~0 \le d \le 1~);
• Dòng thứ hai chứa xâu ~s~ độ dài ~n~, gồm ~n~ kí tự latin viết thường.

Output

• Ghi ra ~n~ số nguyên trên một dòng, số nguyên thứ ~k~ là giá trị của ~f(k)~.

Sample Input 1

11 0
ababaaabaaa

Sample Output 1

31 4 1 0 0 0 0 0 0 0 0