题目描述

给定字符串 $S$，对每个 $i \in [1, n]$，定义 $\pi_i$ 为 $S[:i]$ 的最长 Border。求数组 $\pi$。

输入格式

输入只有一行，包含一个只含有小写字母的字符串 $S$。

输出格式

输出一行，包含 $|S|$ 个整数，描述 $\pi_1, \pi_2, \cdots, \pi_{|S|}$。

样例数据

样例 1 输入

abcababcababcbacbabc

样例 1 输出

0 0 0 1 2 1 2 3 4 5 6 7 8 0 1 0 0 1 2 3

样例 2

见下发文件

样例 3

见下发文件

子任务

对于所有数据，$1 \leq |S| \leq 10^5$。