配置

25组数据,传统型,没有SpecialJudge。

背景

萌萌哥哥为什么这么萌呢?tangjz发现,在叫萌萌哥哥的时候,觉得萌萌哥哥越来越萌了,这是因为叫法中使用了叠词。tangjz认为,像"萌萌"和"哥哥"这样正着读和反着读一样的名字是很萌很有爱的,名字越长越萌,tangjz想请你从一段字符串中挑选出萌度最高的(即最长的)回文序列让他细细品味。>_<

描述

本来tangjz想要给你一个字符串,请你求出其中的最长回文序列,可是tangjz的电脑太慢了,新装的萌萌文本编辑器什么字符串都跑不出来,为了赶时间把这道题出好,tangjz直接把操作复制出来了……

于是你需要根据这些操作,还原字符串。最萌回文序列有可能有很多个,你只需要告诉tangjz它的长度,tangjz会自己去找的。

注意,初始时文本编辑器里没有字符。

操作包括以下五种:

Insert x y 在第x位后插入字符y
Remove x 删除第x位的字符
Modify x y z 把第x位到第y位的字符统一改成z
Reverse x y 把第x位到第y位的字符进行区间翻转
Rotate x y z 把第x位到第y位的字符整体右移z次

比如说我要将区间”abcde”右移2次,它会变成”deabc”,而右移8次会变成”cdeab”。

输入格式

第一行一个正整数N,表示有N个操作。

接下来N行,每行一个操作。

输出格式

第一行输出还原的字符串。

第二行输出最长回文序列长度。

样例输入1

27
Insert 0 g
Insert 1 n
Insert 2 e
Insert 3 m
Insert 4 g
Insert 5 n
Insert 6 e
Insert 7 m
Rotate 1 8 4
Reverse 1 8
Insert 8 d
Insert 9 a
Insert 10 x
Insert 11 i
Insert 12 m
Insert 13 e
Insert 14 n
Insert 15 g
Insert 16 m
Insert 17 e
Insert 18 n
Insert 19 g
Modify 17 20 a
Remove 18
Modify 17 17 c
Modify 19 19 o
Rotate 11 19 3

样例输出1

mengmengdacaoximeng
7

样例解释1

某一个最长回文序列是”emacame”。

样例输入输出2

比赛数据包\name\name.in和name.out

数据范围与约定

  • 对于24%的数据:仅Insert
  • 对于36%的数据:Insert和Remove
  • 对于72%的数据:Insert、Remove和Modify
  • 对于80%的数据:Insert、Remove、Modify、Reverse
  • 对于100%的数据:N\leq 50000,Rotate操作的z是32位有符号位整型的非负整数,字符串只含小写字母。