String Algorithm

Time limit20sMemory limit512 MB

Summary

For every k, cut s into blocks of length k, discard the tail, and count block pairs whose Hamming distance is at most one.

Level: Hard9 of 10
Topics: String, Hash map, String matching, Divide and conquer
Solved: No attempts yet

Problem

We give you a string $s$ of length $n$ .

Fix some $k$ ( $1 \le k \le n$ ). Create $m = \lfloor n/k \rfloor$ strings of length $k$ , the $i$ -th of them being the substring of $s$ that starts at position $(i-1)k+1$ : $p_i = s_{(i-1)k+1} s_{(i-1)k+2} \dots s_{ik}$ .

In other words, cut the string $s$ into strings of length $k$ and discard the leftovers. Let $f(k) = |\{(i, j) \mid 1 \le i < j \le m, \operatorname{dist}(p_i, p_j) \le 1\}|$ , where $\operatorname{dist}$ is the Hamming distance. That is, $f(k)$ is the number of pairs of strings $p$ that differ in at most one position.

Design an algorithm to compute $f(k)$ for all $k$ from 1 to $n$ .

Input

The first line contains one positive integer $n$ ( $1 \le n \le 2 \cdot 10^5$ ), the length of the string.

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

Output

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

Examples3

Example 1
Input
```
7
kkekeee
```
Expected output
```
21 2 1 0 0 0 0
```
Example 2
Input
```
10
babaiskeke
```
Expected output
```
45 2 0 0 0 0 0 0 0 0
```
Example 3
Input
```
11
aaabaaabaaa
```
Expected output
```
55 10 2 1 0 0 0 0 0 0 0
```