Для рядка S
визначимо Z
-функцію наступним чином: Z\[i\] = lcp(S, S\[i..|S|\]), де lcp(S\[1\], S\[2\]) дорівнює довжині найбільшого спільного префікса рядків S\[1\] та S\[2\]. Наприклад, для S = abacabaa Z
-функція рівна \[8, 0, 1, 0, 3, 0, 1, 1\].
Для рядка S
визначимо її префікс-функцію: pi\[i\] = max{k | 0 ≤ k
< i, S\[1..k\] = S\[i - k + 1..i\]}. Наприклад, для S = abacabaa його префікс-функція має вид: \[0, 0, 1, 0, 1, 2, 3, 1\].
Для деякого рядка S
була порахована її Z
-функція, а рядок S
було втрачено. Ваша задача отримати його префікс-функцію за заданою Z
-функцією.
У першому рядку вхідного файлу міститься натуральне число N
(1 ≤ N ≤ 200000
), де N
- довжина S
. У другому рядку записано Z
-функцію рядка S
.
Виведіть N
чисел - шукану префікс-функцію.