无聊的游戏
时间限制：40s 空间限制：512MB
题目描述
小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
保证所有的串都只包含小写英文字母。
保证有一些数据是随机的。
题目来源
2014年国家集训队十五人互测