给出长度为 $N$ 的字符串 $S$。对于每个整数 $i=1,2,\ldots,N-1$，小泽要寻找最大的整数 $l$，满足下面两个条件：

• $l+i\le N$；
• 对所有 $1\le k\le l$，都有 $S_k\ne S_{k+i}$。

也就是说，从字符串开头与向右偏移 $i$ 个位置处同时向后比较，在第一次遇到相同字符之前一共能连续比较多少对不同字符。请分别输出每个 $i$ 的答案。

输入格式

第一行包含整数 $N$。第二行包含长度为 $N$ 的字符串 $S$。

输出格式

输出 $N-1$ 行，第 $i$ 行表示偏移量为 $i$ 时的最大 $l$。

6
abcbac

5
1
2
0
1

3
aaa

0
0

5
abcde

4
3
2
1

数据范围

• $2\le N\le5000$
• $S$ 只含小写英文字母