题目描述

小 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 一等奖而奋斗呢。

输入格式

第一行包含两个正整数 $N,M$。

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

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

输出格式

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

2 3
noi
noip
Q 1 2
I 2 2 ctsc
Q 1 2

3
0

提示

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

对于 $25\%$ 的数据，满足 $N,M\le 1000$，$\text{st},\text{sum}\le3000$；
对于 $50\%$ 的数据，满足 $N,M\le 2\times 10^4$，$\text{st},\text{sum}\le 4\times 10^4$；
对于 $100\%$ 的数据，满足 $N,M\le 5\times 10^4$，$\text{st},\text{sum}\le 6\times 10^5$。

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

题目来源

2014 年国家集训队十五人互测