给定一个长度为 $n$ 的字符串 $s$。

固定某个 $k$ ($1 \le k \le n$)。创建 $m = \lfloor \frac{n}{k} \rfloor$ 个长度为 $k$ 的字符串，其中第 $i$ 个字符串是 $s$ 从位置 $(i - 1)k + 1$ 开始的子串：$p_i = s_{(i-1)k+1}s_{(i-1)k+2} \dots s_{ik}$。

换句话说，我们将字符串 $s$ 切割成若干长度为 $k$ 的字符串，并丢弃剩余部分。令 $f(k) = |\{(i, j) \mid 1 \le i < j \le m, \text{dist}(p_i, p_j) \le 1\}|$，其中 $\text{dist}$ 表示汉明距离。通俗地说，$f(k)$ 是满足至多只有 1 个位置不同的字符串对 $(p_i, p_j)$ 的数量。

请设计一个算法，计算所有 $k$ 从 $1$ 到 $n$ 的 $f(k)$。

输入格式

第一行包含一个正整数 $n$ ($1 \le n \le 2 \cdot 10^5$)，表示字符串的长度。 第二行包含一个长度为 $n$ 的字符串 $s$，由小写英文字母组成。

输出格式

输出 $n$ 个数字，其中第 $k$ 个数字为 $f(k)$。

样例

输入格式 1

7
kkekeee

输出格式 1

2 1 2 1 0 0 0

输入格式 2

10
babaiskeke

输出格式 2

4 5 2 0 0 0 0 0 0 0

输入格式 3

11
aaabaaabaaa

输出格式 3

5 5 10 2 1 0 0 0 0 0 0