Mahmoud和Ehab解决了邪恶博士的问题,邪恶博士给了他们邪恶之地之门的密码。当他们试图用它打开门时,门给了他们在离开之前要解决的最后一个问题(是的,门是数字的,邪恶博士是现代的)。如果不解决的话,一切的努力都将毫无意义,他们也永远无法离开邪恶之地。你会帮助他们吗?
Mahmoud 和 Ehab 被给予 n 个字符串 s1, s2, ... , sn 编号从 1 到 n 和 q 个查询,每个查询具有以下形式之一:
- 1 a b (1 ≤ a ≤ b ≤ n),对于所有区间 [l;r],其中 (a ≤ l ≤ r ≤ b) 找到此最大值表达式:(r - l + 1) * LCP(sl, sl + 1, ... , sr - 1, sr) 其中 LCP(str1, str2, str3, ... ) 是字符串的最长公共前缀的长度str1, str2, str3, ... 。
- 2 x y (1 ≤ x ≤ n) 其中 y 是一个字符串,由小写英文字母组成。将位置 x 处的字符串更改为 y。
输入
输入的第一行包含 2 个整数 n 和 q (1 ≤ n ≤ 105, 1 ≤ q ≤ 105) – 分别是字符串的数量和查询的数量。
第二行包含n个由小写英文字母组成的字符串stri。
接下来的 q 行描述查询,并且可能具有以下 2 种形式之一:
- 1 a b (1 ≤ a ≤ b ≤ n)。
- 2 x y (1 ≤ x ≤ n),其中y是由小写英文字母组成的字符串。
输入中所有字符串的总长度不会超过 105
输出
对于第一种类型的每个查询,在新行中输出其答案。
示例
输入 #1
5 9 mahmoud mahmoudbadawy drmahmoud drevil mahmoud 1 1 5 1 1 2 1 2 3 2 3 mahmoud 2 4 mahmoud 2 2 mahmouu 1 1 5 1 2 3 1 1 1
输出 #1
14 14 13 30 12 7