\begin{problem}{Помогите, спасите!}{keepcounted.in}{keepcounted.out}{4 секунды}{256 мегабайт}

Дана строка. Найдите для каждого её префикса количество различных подстрок в нём.

\InputFile
В единственной строке входных данных содержится непустая строка $S$, состоящая из $N$ ($1 \leq N \leq 2 \cdot 10^5$) маленьких букв английского алфавита.

\OutputFile
Выведите $N$ строк, в $i$-й строке должно содержаться количество различных подстрок в $i$-м префиксе строки $S$.


\Examples

\begin{example}
\exmp{aabab
}{1
2
5
8
11
}%
\exmp{atari
}{1
3
5
9
14
}%
\end{example}

\end{problem}
