字符串识别

XX 在研究字符串时遇到了一个棘手的问题。

给定一个字符串 $S$ 和一个整数 $K$，定义 $S$ 的子串 $T=S(i,j)$ 为关于第 $K$ 位的识别子串，当且仅当满足以下条件：

• $i\le K\le j$；
• 子串 $T$ 在字符串 $S$ 中只出现过一次。

例如，当 $S=\texttt{banana}$、$K=5$ 时，关于第 $K$ 位的识别子串有 nana、anan、anana、nan、banan 和 banana。

现在给定字符串 $S$，请求出对于 $S$ 的每一位，包含该位置的最短识别子串的长度。

输入格式

输入仅一行，为长度为 $N$ 的字符串 $S$。

输出格式

输出 $N$ 行，每行一个整数。第 $i$ 行表示字符串 $S$ 的第 $i$ 位所对应的最短识别子串长度。

样例输入

agoodcookcooksgoodfood

样例输出

1
2
3
3
2
2
3
3
2
2
3
3
2
1
2
3
3
2
1
2
3
4

数据范围

• $N\le 5\times 10^5$。

来源与许可

本题题面与测试数据整理自 BZOJ。

样例 1

输入

agoodcookcooksgoodfood

输出

1
2
3
3
2
2
3
3
2
2
3
3
2
1
2
3
3
2
1
2
3
4