Little N defined a function $f(X, Y)$ on two strings $X$ and $Y$ (both strings are indexed starting from $1$), satisfying:

$$\begin{aligned} f(X, Y) = \sum_{i = 1}^{\min(\vert X \vert, \vert Y \vert)} [X_i = Y_i] \end{aligned}$$

(For a proposition $A$, if $A$ is true, then $[A] = 1$; otherwise, $[A] = 0$.)

That is, it is the number of positions where the corresponding characters of strings $X$ and $Y$ are equal. For example, $f(\texttt{axc}, \texttt{abc}) = 2$, $f(\texttt{abxc}, \texttt{abc}) = 2$, $f(\texttt{abc}, \texttt{abxc}) = 2$.

Now, Little N gives a string $S$ of length $n$ consisting only of lowercase English letters. Let $S_i$ denote the suffix of $S$ starting from the $i$-th character. Please output, for each $k = 1, 2, \dots, n$, the value of $f(S_1, S_k) + f(S_2, S_k) + \dots + f(S_n, S_k)$.

Input

There are two lines of input.

The first line contains an integer $n$ $(1 \le n \le 10^5)$, representing the length of string $S$.

The second line contains a string $S$ of length $n$ consisting only of lowercase English letters.

Output

Output $n$ lines. The $k$-th line contains the value of $f(S_1, S_k) + f(S_2, S_k) + \cdots + f(S_n, S_k)$.

Examples

Input 1

3
abb

Output 1

4
4
2

Input 2

11
mississippi

Output 2

24
26
23
24
21
17
15
11
7
6
4

Note

For sample 1, $S_1 = \texttt{abb}$, $S_2 = \texttt{bb}$, $S_3 = \texttt{b}$.

When $k = 1$, $f(S_1, S_1) + f(S_2, S_1) + f(S_3, S_1) = 3 + 1 + 0 = 4$.

When $k = 2$, $f(S_1, S_2) + f(S_2, S_2) + f(S_3, S_2) = 1 + 2 + 1 = 4$.

When $k = 3$, $f(S_1, S_3) + f(S_2, S_3) + f(S_3, S_3) = 0 + 1 + 1 = 2$.