题目描述

XX 在进行字符串研究的时候，遇到了一个十分棘手的问题。

在这个问题中，给定一个字符串 $S$，与一个整数 $k$，定义 $S$ 的子串 $T=S(i, j)$ 是关于第 $k$ 位的识别子串，满足以下两个条件：

1. $i\leq k\leq j$​；

2. 子串 $T$ 只在 $S$ 中出现过一次。

例如，$S =$ banana，$k = 5$，则关于第 $k$ 位的识别子串有 nana，anan，anana，nan，banan 和 banana。

现在，给定 $S$，XX 希望知道对于 $S$ 的每一位，最短的识别子串长度是多少，请你来帮助他。

输入格式

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

输出格式

输出 $n$ 行，每行一个整数，第 $i$ 行的整数表示对于第 $i$ 位的最短识别子串长度。

agoodcookcooksgoodfood

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

数据规模与约定

对于 $100\%$​ 的数据，$1\leq n\leq 5\times 10^5$。