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_1 S_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) \cdot k + 1\). Nhắc lại, \(\lfloor z \rfloor\) 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)\cdot k+1} S_{(i-1)\cdot k+2} \dots S_{i\cdot k}\).

Định nghĩa \(\text{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) \mid (1 \le i < j \le m) \text{ thoả mãn } \text{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.

Các số trên cùng một dòng cách nhau bởi dấu cách.

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)\). Các số trên cùng một dòng cách nhau bởi dấu cách.

Example

11 0
ababaaabaaa

31 4 1 0 0 0 0 0 0 0 0

11 1
ababaaabaaa

55 10 1 1 0 0 0 0 0 0 0

Scoring

• Có \(25\%\) test ứng với \(d \le 1, N \le 1000\).
• Có \(25\%\) test khác ứng với \(d \le 1, N \le 3000\).
• Có \(25\%\) test khác ứng với \(d = 0, N \le 50000\).
• \(25\%\) còn lại test ứng với \(d \le 1, N \le 50000\).