← 返回题目列表

Codeforces · 862/F

F. Mahmoud 和 Ehab 以及最后阶段

中文机器翻译题面 查看原题

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