题目描述 小 K 因为学习 OI 认识了两位神犇，他们分别叫做小 H 和小 Y。两位神犇平时是这么对待小 K 的：“这不是道傻逼题么”“这都不会做你智商堪忧啊”……

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

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

第一种操作 Insert(L,R,S)：表示在 [ L , R ] [L,R] 之间的所有串前都加上一个新的非空串 S S； 第二种操作 Query(L,R)：询问 [ L , R ] [L,R] 之间所有串的最长公共前缀。如果 L

R L=R，则输出对应串的长度。 两位神犇分分钟就把这个游戏玩通了。于是他们准备虐一虐小 K，让他也来玩玩。不出所料，小 K 被虐得头昏眼花，于是他找到你，看你能不能帮他一把。小 K 还需要为 NOIP 一等奖而奋斗呢。

输入格式 第一行包含两个正整数 N , M N,M。

接下来的 N N行，每行都包含一个非空的串 S S，表示第 i i 个初始的串。

再接下来的 M M 行每行的开头都有一个字母 type，I 表示这行对应一个 Insert 操作，而 Q 表示对应一个 Query 操作。接下来会从 左到右依次给出这个操作的参数。

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

输入数据 1 2 3 noi noip Q 1 2 I 2 2 ctsc Q 1 2 输出数据 1 3 0 提示 令 st st 表示初始时所有串的长度之和， sum sum 表示所有 Insert 操作中所给串的长度之和。

对于 25 % 25% 的数据，满足 N , M ≤ 1000 N,M≤1000， st , sum ≤ 3000 st,sum≤3000； 对于 50 % 50% 的数据，满足 N , M ≤ 2 × 10 4 N,M≤2×10 4 ， st , sum ≤ 4 × 10 4 st,sum≤4×10 4 ； 对于 100 % 100% 的数据，满足 N , M ≤ 5 × 10 4 N,M≤5×10 4 ， st , sum ≤ 6 × 10 5 st,sum≤6×10 5 。

保证所有的串都只包含小写英文字母。保证有一些数据是随机的。

题目来源 2014 年国家集训队十五人互测