G. Сколько раз встречается каждый префикс

Для каждого $k$ от 1 до $n$ посчитайте, сколько раз префикс длины $k$ встречается в строке как подстрока.

Одна строка длины $n$ ($1 \le n \le 10^6$) из строчных латинских букв.

Одна строка из $n$ чисел: сколько раз встречается префикс длины 1, 2, ..., $n$.