1609_回文子串

这是一道模板题。

给定一个字符串 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 ，表示要在末尾或前端添加的字符串。

对于 100% 的测试数据，保证有：初始时 0<∣s∣≤ 10⁵  ，0 < Q ≤ 10⁵  ，0 <∣t∣< 1000 且操作序列结束时有 0 <∣s∣≤ 4×10⁵ 。

对于每个 op 为 3 的操作，分别在单独的一行上输出此时 s 中非空回文子串的数量。

Sample #1
aaa
1
3

Sample #2
a
5
3
1 bba
3
2 ab
3

Sample #1
6

Sample #2
1
6
10