시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
20 초 512 MB 2 2 2 100.000%

문제

We give you a string s of length n.

Let’s fix some k (1 ≤ k ≤ n). Create m = ⌊n/k⌋ strings of length k, the i-th of them being a substring of s starting with position (i − 1)k + 1: pi = s(i−1)k+1s(i−1)k+2 . . . sik.

In other words, we cut the string s into strings of length k and discard leftovers. Let f(k) = |{(i, j) | 1 ≤ i < j ≤ m, dist(pi, pj) ≤ 1}|, where dist denotes the Hamming distance. In human words, f(k) is the number of pairs of strings p that are different in at most 1 position.

We ask you to devise an algorithm to compute f(k) for all k from 1 to n.

입력

The first line contains one positive integer n (1 ≤ n ≤ 2 · 105) — the length of the string.

The second line contains the string s of length n, consisting of lowercase English characters.

출력

Print n numbers, the k-th of them being f(k).

예제 입력 1

7
kkekeee

예제 출력 1

21 2 1 0 0 0 0

예제 입력 2

10
babaiskeke

예제 출력 2

45 2 0 0 0 0 0 0 0 0

예제 입력 3

11
aaabaaabaaa

예제 출력 3

55 10 2 1 0 0 0 0 0 0 0