题目背景

翻译自 CSES-2107 题。

题目描述

给定一个长度为 $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^6$。