palindrome

初始字符串为空。按照输入顺序执行所有操作，得到最终字符串。

字符串的“好听程度”定义为其最长回文子序列的长度。子序列可以通过从原字符串中删除任意若干字符得到，但剩余字符的相对顺序不能改变。

请输出最终字符串的好听程度。

输入格式

输入包含若干行操作，读至文件结束。

每行包含以下五种操作之一。除 Insert 操作的插入位置外，字符串中的位置均从 $1$ 开始编号。

Insert $i$ $c$ ：在当前字符串的第 $i$ 个字符之后插入字符 $c$ 。当 $i=0$ 时，表示插入到字符串最前端。
Modify $l$ $r$ $c$ ：将闭区间 $[l,r]$ 内的所有字符修改为 $c$ 。
Remove $i$ ：删除当前字符串的第 $i$ 个字符。
Reverse $l$ $r$ ：翻转闭区间 $[l,r]$ 。
Rotate $l$ $r$ $k$ ：将闭区间 $[l,r]$ 循环向右移动 $k$ 位，移动位数对区间长度取模。

输出格式

输出一个整数，表示最终字符串的好听程度。

样例输入

Insert 0 f
Insert 1 j
Insert 2 x
Insert 3 m
Insert 4 l
Insert 5 h
Insert 6 x
Insert 7 w
Insert 8 j
Insert 9 z
Insert 10 b
Insert 11 m
Insert 12 r
Insert 11 z
Insert 12 b
Modify 10 11 m
Remove 10
Insert 7 t
Insert 8 o
Insert 9 o
Insert 10 r
Reverse 8 11
Rotate 1 11 4

样例输出

数据范围

所有操作参数均保证合法。

来源与许可

本题题面与测试数据整理自 BZOJ。

样例 1

输入

Insert 0 f
Insert 1 j
Insert 2 x
Insert 3 m
Insert 4 l
Insert 5 h
Insert 6 x
Insert 7 w
Insert 8 j
Insert 9 z
Insert 10 b
Insert 11 m
Insert 12 r
Insert 11 z
Insert 12 b
Modify 10 11 m
Remove 10
Insert 7 t
Insert 8 o
Insert 9 o
Insert 10 r
Reverse 8 11
Rotate 1 11 4