#2865. 字符串识别

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

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

1、i≤K≤j。

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

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

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

样例输入

			
agoodcookcooksgoodfood

样例输出

			


1



2



3



3



2



2



3



3



2



2



3



3



2



1



2



3



3



2



1



2



3



4