String Function Transformations

For a string $S$, we define the $Z$-function as follows: Z[i] = lcp(S, S[i..|S|]), where lcp(S_1, S_2) is the length of the longest common prefix of the strings S_1 and S_2. For example, for S = abacabaa, the $Z$-function is [8, 0, 1, 0, 3, 0, 1, 1].

For a string $S$, we define its prefix function as: pi[i] = max\{k | 0 \le k < i, S[1..k] = S[i - k + 1..i]\}. For example, for S = abacabaa, its prefix function is [0, 0, 1, 0, 1, 2, 3, 1].

Given a string $S$, its $Z$-function was calculated, but the string $S$ itself was lost. Your task is to derive its prefix function from the given $Z$-function.