문자열 덮개

문자열 $\alpha$가 문자열 $\beta$를 덮는다는 것은, $\beta$의 모든 위치에 대해 그 위치를 포함하는 $\alpha$의 출현이 $\beta$의 부분 문자열로 존재한다는 뜻이다. 예를 들어 aba는 abaabaababa를 덮지만 baba는 덮지 못한다. 어떤 문자열이든 자기 자신을 덮는다는 것은 자명하다.

문자열 $w$가 주어진다. 각 접두사 $w[1..k]$에 대해, 이를 덮는 가장 짧은 문자열을 구하시오.

입력 파일에는 소문자 라틴 알파벳으로 이루어진 문자열 $w$가 한 줄에 주어진다. $w$의 길이는 $250\,000$을 넘지 않는다.

$k$를 1부터 $w$의 길이까지 바꾸면서, 각 $k$에 대해 $w[1..k]$를 덮는 가장 짧은 문자열의 길이를 출력하시오.