题目描述

给定一个仅包含小写英文字母的字符串 $S$，长度为 $n$。

对于每个位置 $i\ (1 \leq i \leq n)$，求出以 $S_i$ 结尾的最长回文子串的长度。

输入格式

一行一个字符串 $S$，仅包含小写英文字母。$1 \leq |S| \leq 10^5$。

输出格式

一行 $n$ 个整数，用空格分隔。第 $i$ 个整数表示以第 $i$ 个字符结尾的最长回文子串的长度。

样例 1

aabbaa

1 2 1 2 4 6

以各位置结尾的最长回文子串：

• 位置 1：只有 a，长度为 1
• 位置 2：aa，长度为 2
• 位置 3：b，长度为 1
• 位置 4：bb，长度为 2
• 位置 5：abba，长度为 4
• 位置 6：aabbaa，长度为 6

样例 2

abacaba

1 1 3 1 3 5 7

数据范围

对于 $100\%$ 的数据，$1 \leq n \leq 10^5$，$S$ 仅包含小写英文字母。