### 问题描述 荣神有一个 $n$ 个字符的字符串，索引为 $1, 2, \dots, n$。他想计算以下函数的所有值： - $z(i)$ 表示从位置 $i$ 开始并且是字符串的前缀的最大子串长度。另外，$z(1) = 0$。 - $\pi(i)$ 表示以位置 $i$ 结尾并且是字符串前缀的最大长度的子串，且其长度最多为 $i-1$。 请注意，函数 $z$ 用于 $Z$ 算法，函数 $\pi$ 用于 $KMP$ 算法。 ### 输入格式 只有一行，包含长度为 $n$ 的字符串，由字符 $a-z$ 组成。 ### 输出格式 输出两行，第一行是 $z$ 函数的值，第二行是 $\pi$ 函数的值。 ### 样例输入 ``` abaabca ``` ### 样例输出 ``` 0 0 1 2 0 0 1 0 0 1 1 2 0 1 ``` ### 评测数据规模 $1 \leq n \leq 10^5$。