双端队列回文计数

【题目描述】

有一个初始为空的字符串 $s$。依次处理 $Q$ 个查询。

• 0 $c$：在字符串 $s$ 的开头添加字符 $c$。
• 1 $c$：在字符串 $s$ 的末尾添加字符 $c$。
• 2：删除字符串 $s$ 开头的字符。
• 3：删除字符串 $s$ 末尾的字符。

每处理完一个查询后，依次输出以下 $3$ 个参数。

• $s$ 的不同非空回文子串个数
• $s$ 的最长回文前缀长度
• $s$ 的最长回文后缀长度

若 $s$ 为空串，则改为输出 0 0 0。

【输入】

$Q$
$\textrm{Query}_0$
$\textrm{Query}_1$
$\vdots$
$\textrm{Query}_{Q - 1}$

【输出】

每处理完一个查询后输出一行，依次为 $s$ 的不同非空回文子串个数、$s$ 的最长回文前缀长度、$s$ 的最长回文后缀长度。若 $s$ 为空串，则输出 0 0 0。

【输入样例】

9
1 a
1 b
1 c
1 b
1 c
1 b
1 a
3
1 c

【输出样例】

1 1 1
2 1 1
3 1 1
4 1 3
5 1 3
6 1 5
7 7 7
6 1 5
7 1 5

【输入样例2】

12
0 o
0 x
0 o
1 o
1 x
1 o
2
2
2
3
3
3

【输出样例2】

1 1 1
2 1 1
3 3 3
4 3 2
5 3 4
6 6 6
5 4 3
4 2 3
3 3 3
2 1 1
1 1 1
0 0 0

【数据范围】

• $1 \leq Q \leq 500000$
• $c$ 为小写英文字母。
• 查询 $2$ 或查询 $3$ 到来时，字符串 $s$ 不为空。

【来源】

Library Checker（yosupo06） palindromes_in_deque