Dima 逐个将字母 $s_1, \dots, s_n$ 添加到一个单词的末尾。每添加一个字母后，他都会询问 Misha 在添加该字母后出现了多少个新的回文子串。如果两个子串作为字符串不同，则它们被视为不同的子串。已知 Misha 从不出错，请问他会说出哪 $n$ 个数字？

顺便提一下，别忘了仔细考虑时间限制（TL）、内存限制（ML）以及最大字符串长度。你可能已经在不同的限制条件下见过这个问题。我们已经尽一切努力让你的旧解法无法通过 :)

输入格式

输入包含一个由字母 'a' 和 'b' 组成的字符串 $s_1 \dots s_n$ ($1 \le n \le 5\,000\,000$)。

输出格式

输出 $n$ 个数字，中间不要有空格：第 $i$ 个数字必须是前缀 $s_1 \dots s_i$ 的回文子串数量减去前缀 $s_1 \dots s_{i-1}$ 的回文子串数量。输出的第一个数字应该是 1。

样例

输入 1

abbbba

输出 1

111111

说明

我们拥有的唯一一个能解决此问题的 Java 解法在处理输入和输出时非常小心。我们可以保证它满足内存限制（ML）和一半的时间限制（TL/2）。

我们反对针对不同编程语言设置不同的时间限制和内存限制。我们也不认为缺少某个问题的 Java 解法是正常的。无论如何，如果你选择用 Java 编写代码，你必须确实了解在该语言中处理内存、输入和输出的特定方法。

以防万一，这里有一个我们的提示：我们仅使用 FileReader 和 FileWriter 处理输入和输出。

FileReader in = new FileReader("input.txt");
FileWriter out = new FileWriter("output.txt");
s = new char[SIZE];
result = new char[SIZE];
int slen = in.read(s, 0, SIZE);
...
out.write(result, 0, slen);
out.flush();