无聊的游戏

内存限制：512 MiB 时间限制：40 Sec

小K因为学习OI认识了两位神犇，他们分别叫做小H和小Y。两位神犇平时是这么对待小K的：

“这不是道傻逼题么”

“这都不会做你智商堪忧啊”

“。。。。。。”

小K因此对生活失去了信心。最近两位神犇没什么题刷，于是他们开始用自己做题剩下的史诗级智商来享受生活的快乐——研究游戏开发了。

由于两位神犇太神，不久他们就创造了新的游戏。游戏一开始会给由你N个非空串构成的序列，然后你要进行M次操作。操作分为两种：

第一种操作Insert(L,R,S)：表示在[L,R]之间的所有串前都加上一个新的非空串S。

第二种操作Query(L,R)：询问[L,R]之间所有串的最长公共前缀。如果L=R，则输出对应串的长度。

两位神犇分分钟就把这个游戏玩通了。于是他们准备虐一虐小K，让他也来玩玩。不出所料，小K被虐得头昏眼花，于是他找到你，看你能不

能帮他一把。小K还需要为NOIP一等奖而奋斗呢。

第1行包含两个正整数N，M。接下来的N行每行都包含一个非空的串S，表示第i个初始的串。再接下来的M行每行的

开头都有一个字母type，type=`I'表示这行对应一个Insert操作，而type=`Q'时对应一个Query操作。接下来会从

左到右依次给出这个操作的参数。

对于每一个Query操作，输出一行。一行包含一个正整数，表示这组询问的答案。


			2 3

noi

noip

Q 1 2

I 2 2 ctsc

Q 1 2


			3

0

令st表示初始时所有串的长度之和，$sum$表示所有$Insert$操作中所给串的长度之和。

对于25%的数据，满足N,M<=1000, st,sum<=3000。

对于50%的数据，满足N,M<=20000, st,sum<=40000。

对于100%的数据，满足N,M<=50000,st+sum<=600000

保证所有的串都只包含小写英文字母。

保证有一些数据是随机的。

#3946. 无聊的游戏