3919: 回文子串
内存限制：256 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：0
解决：0
题目描述
这是一道模板题。
给定一个字符串 $ s $ 以及 $ Q $ 个操作。您需要编写一个程序以支持下列几种操作：
1. 在字符串 $ s $ 的末尾添加一个字符串；
2. 在字符串 $ s $ 的前端添加一个字符串的 **反序**；
3. 查询字符串 $ s $ 的所有非空回文子串的数量。
$ s $ 的两个子串视为不同，当且仅当这两个子串的长度不同或者这两个子串在 $ s $ 中的起始位置不同。
$ s $ 的反序字符串定义为将 $ s $ 中前后对称位置的字符两两对调位置后形成的字符串。
输入
输入文件第一行包含一个字符串 $ s $。
输入文件第二行包含一个整数 $ Q $，表示操作的数量。
接下来 $ Q $ 行，每行首先包含一个整数 $ op $，其含义如下所示：
+ 1：在字符串 $ s $ 的末尾添加一个字符串；
+ 2：在字符串 $ s $ 的前端添加一个字符串的 **反序**；
+ 3：查询字符串 $ s $ 的所有非空回文子串的数量。
若 $ op $ 为 1 或 2，则接下来会给出一个字符串 $ t $，表示要在末尾或前端添加的字符串。
输出
对于每个 $ op $ 为 3 的操作，分别在单独的一行上输出此时 $ s $ 中非空回文子串的数量。
样例输入 复制
aaa
1
3样例输出 复制
6提示
输入样例2
a 5 3 1 bba 3 2 ab 3
输出样例2
1 6 10
数据范围：对于 $ 100\% $ 的测试数据，保证有： 初始时 $ 0 < |s| \leq 10^5 $，$ 0 < Q \leq 10^5 $，$ 0 < |t| < 1000 $ 且操作序列结束时有 $ 0 < |s| \leq 4 \times 10^5 $。