Дима плохо подготовился к тесту по строковым алгоритмам. Он отлично знает, как построить Z-функцию, но вот про префикс-функцию забыл всё, что когда-либо знал.
Вы давно дружите с Димой и решили помочь ему. Он передал вам листок, на котором написал свою Z-функцию. Помогите ему построить по ней префикс-функцию.
Формат входных данных
В первой строке содержится целое число \(n\ (n \le 10^5)\) — длина Z-функции Димы. Во второй строке содержится сама функция.
Формат выходных данных
Выведите полученную префикс-функцию.
Примечание
Префикс-функция строки \(s\) длины \(n\) — это массив \(\pi[0 \ldots n-1]\), где значение \(\pi[i]\) равно длине наибольшего собственного префикса подстроки \(s[0 \ldots i]\), который одновременно является её суффиксом.
Z-функция строки \(s\) длины \(n\) — это массив \(z[0 \ldots n-1]\), где значение \(z[i]\) равно длине наибольшего префикса строки \(s\), совпадающего с подстрокой, начинающейся в позиции \(i\). Считается, что \(z[0] = n\), где \(n\) — длина строки.
| № | Входные данные | Выходные данные |
|
1
|
8
8 0 1 0 3 0 1 1
|
0 0 1 0 1 2 3 1
|