题目描述

Deni 想出了一个只由小写拉丁字母组成的字符串，并想要衡量它有多“美”。

她会反复进行两种操作：

• 操作 1：在字符串末尾追加一个字符；
• 操作 2：删除当前字符串的第一个字符。

对于操作过程中得到的每一个字符串（包括最初的字符串），她都想知道其中不同子串的个数。

请你编写程序 substrings，输出每一步对应字符串的不同子串数量。

输入格式

第一行输入一个由 N 个小写拉丁字母组成的字符串。
第二行输入一个整数 Q，表示操作次数。

接下来 Q 行，每行为以下两种格式之一：

• 1 c：表示执行一次操作 1，在末尾添加字符 c；
• 2：表示执行一次操作 2，删除当前字符串的第一个字符。

输出格式

输出一行，共 Q + 1 个整数，依次表示：

• 初始字符串的不同子串个数；
• 每次操作之后当前字符串的不同子串个数。

数据范围

• 1 <= N <= 10^5
• 0 <= Q <= 10^5

子任务

通过某个子任务的全部测试点后，才能获得该子任务对应的全部分数。

样例 1

输入 1

abaababa
6
2
1 b
1 b
2
2
2

输出 1

24 19 23 31 24 17 14

样例解释 1

字符串在操作过程中依次变为：

abaababa -> baababa -> baababab -> baabababb -> aabababb -> abababb -> bababb

例如在最后一个字符串 bababb 中，不同子串共有如下 14 个：

b, a, ba, ab, bb, bab, aba, abb, baba, abab, babb, babab, ababb, bababb

样例 2

输入 2

abaababa
16
2
2
2
2
2
2
2
1 a
1 b
1 a
1 a
1 b
1 a
1 b
1 a

输出 2

24 19 14 9 7 5 3 1 0 1 3 5 8 11 14 19 24

样例解释 2

字符串在操作过程中依次变为：

abaababa -> baababa -> aababa -> ababa -> baba -> aba -> ba -> a -> 空串 -> a -> ab -> aba -> abaa -> abaab -> abaaba -> abaabab -> abaababa