CF862F.Mahmoud and Ehab and the final stage

Mahmoud and Ehab solved Dr. Evil's questions so he gave them the password of the door of the evil land. When they tried to open the door using it, the door gave them a final question to solve before they leave (yes, the door is digital, Dr. Evil is modern). If they don't solve it, all the work will be useless and they won't leave the evil land forever. Will you help them?

Mahmoud and Ehab are given n strings _s_1, _s_2, ... , s__n numbered from 1 to n and q queries, Each query has one of the following forms:

• 1 a b (1 ≤ a ≤ b ≤ n), For all the intervals [l;r] where (a ≤ l ≤ r ≤ b) find the maximum value of this expression:

  (r - l + 1) * LCP(s__l, s__l + 1, ... , s__r - 1, s__r) where LCP(_str_1, _str_2, _str_3, ... ) is the length of the longest common prefix of the strings _str_1, _str_2, _str_3, ... .

• 2 x y (1 ≤ x ≤ n) where y is a string, consisting of lowercase English letters. Change the string at position x to y.

马哈茂德和埃哈卜解答了恶魔博士的问题，因此他给了他们通往邪恶之地大门的密码。当他们尝试用该密码打开大门时，大门向他们提出了一个最终问题，只有解答出来才能离开（没错，这扇门是数字化的，恶魔博士很现代）。如果他们无法解答，之前的所有努力都将白费，他们将永远无法离开邪恶之地。你愿意帮助他们吗？

马哈茂德和埃哈卜被给定 $n$ 个字符串 $s_1,\ s_2,\ \dots,\ s_n$，编号从 $1$ 到 $n$，以及 $q$ 个查询。每个查询具有以下两种形式之一：

• 1 a b（其中 $1 \le a \le b \le n$）：对所有满足 $a \le l \le r \le b$ 的区间 $[l;r]$，求下列表达式的最大值：

  $$(r - l + 1) \times \mathrm{LCP}(s_l,\ s_{l+1},\ \dots,\ s_{r-1},\ s_r)$$

  其中 $\mathrm{LCP}(\mathrm{str}_1,\ \mathrm{str}_2,\ \mathrm{str}_3,\ \dots)$ 表示字符串 $\mathrm{str}_1,\ \mathrm{str}_2,\ \mathrm{str}_3,\ \dots$ 的最长公共前缀的长度。

• 2 x y（其中 $1 \le x \le n$），其中 $y$ 是一个仅由小写英文字母组成的字符串。将位置 $x$ 处的字符串替换为 $y$。

The first line of input contains 2 integers n and q (1 ≤ n ≤ 105, 1 ≤ q ≤ 105) – The number of strings and the number of queries, respectively.

The second line contains n strings str__i consisting of lowercase English letters.

The next q lines describe the queries and may have one of the 2 forms:

• 1 a b (1 ≤ a ≤ b ≤ n).
• 2 x y (1 ≤ x ≤ n), where y is a string consisting of lowercase English letters.

the total length of all strings in input won't exceed 105

输入的第一行包含两个整数 $n$ 和 $q$（$1 ≤ n ≤ 10^5$，$1 ≤ q ≤ 10^5$）——分别表示字符串的个数和查询的个数。

第二行包含 $n$ 个字符串 $str_i$，每个字符串均由小写英文字母组成。

接下来的 $q$ 行描述了各次查询，每行查询为以下两种形式之一：

• 1 a b（$1 ≤ a ≤ b ≤ n$）。
• 2 x y（$1 ≤ x ≤ n$），其中 $y$ 是一个由小写英文字母组成的字符串。

输入中所有字符串的总长度不超过 $10^5$。

For each query of first type output its answer in a new line.

对于每个第一类查询，在新的一行中输出其答案。