English · Original
Chinese · Translation
Formal · Original
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_.
## Input
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**
## Output
For each query of first type output its answer in a new line.
[samples]
Mahmoud 和 Ehab 解决了 Dr. Evil 的问题，因此他给了他们进入邪恶之地大门的密码。当他们尝试使用该密码打开门时，门给出了一个最终问题，必须在他们离开前解决（是的，这扇门是数字化的，Dr. Evil 很现代）。如果他们无法解决，所有努力都将白费，他们将永远无法离开邪恶之地。你能帮助他们吗？
Mahmoud 和 Ehab 被给予 #cf_span[n] 个字符串 #cf_span[s1, s2, ... , sn]，编号从 #cf_span[1] 到 #cf_span[n]，以及 #cf_span[q] 个查询，每个查询具有以下形式之一：
#cf_span[(r - l + 1) * LCP(sl, sl + 1, ... , sr - 1, sr)]，其中 #cf_span[LCP(str1, str2, str3, ... )] 是字符串 #cf_span[str1, str2, str3, ... ] 的最长公共前缀的长度。
输入的第一行包含两个整数 #cf_span[n] 和 #cf_span[q] #cf_span[(1 ≤ n ≤ 105, 1 ≤ q ≤ 105)] —— 字符串的数量和查询的数量。
第二行包含 #cf_span[n] 个由小写英文字母组成的字符串 #cf_span[stri]。
接下来的 #cf_span[q] 行描述查询，可能具有以下两种形式之一：
*输入中所有字符串的总长度不超过 #cf_span[105]*
对于每个第一类查询，请在新的一行输出其答案。
## Input
输入的第一行包含两个整数 #cf_span[n] 和 #cf_span[q] #cf_span[(1 ≤ n ≤ 105, 1 ≤ q ≤ 105)] —— 字符串的数量和查询的数量。第二行包含 #cf_span[n] 个由小写英文字母组成的字符串 #cf_span[stri]。接下来的 #cf_span[q] 行描述查询，可能具有以下两种形式之一：
#cf_span[1] #cf_span[a] #cf_span[b]（#cf_span[1 ≤ a ≤ b ≤ n]）。
#cf_span[2] #cf_span[x] #cf_span[y]（#cf_span[1 ≤ x ≤ n]），其中 #cf_span[y] 是由小写英文字母组成的字符串。
*输入中所有字符串的总长度不超过 #cf_span[105]*
## Output
对于每个第一类查询，请在新的一行输出其答案。
[samples]
**Definitions**
Let $ n, q \in \mathbb{Z}^+ $ denote the number of strings and queries, respectively.
Let $ S = (s_1, s_2, \dots, s_n) $ be a sequence of strings over the alphabet $ \Sigma = \{a, b, \dots, z\} $.
Let $ \text{LCP}(s_i, s_{i+1}, \dots, s_j) $ denote the length of the longest common prefix of the strings $ s_i, s_{i+1}, \dots, s_j $.
**Constraints**
1. $ 1 \leq n \leq 10^5 $, $ 1 \leq q \leq 10^5 $
2. Total length of all strings $ \sum_{i=1}^n |s_i| \leq 10^5 $
**Queries**
Each query is of type:
- Given $ l, r \in \mathbb{Z} $ with $ 1 \leq l \leq r \leq n $, compute:
$$
(r - l + 1) \cdot \text{LCP}(s_l, s_{l+1}, \dots, s_r)
$$
**Objective**
For each query of the given type, output the value of the above expression.
API Response (JSON)
{
"problem": {
"name": "F. Mahmoud and Ehab and the final stage",
"description": {
"content": "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 t",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 5000,
"memory_limit": 524288
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF862F"
},
"statements": [
{
"statement_type": "Markdown",
"content": "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 t...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "Mahmoud 和 Ehab 解决了 Dr. Evil 的问题，因此他给了他们进入邪恶之地大门的密码。当他们尝试使用该密码打开门时，门给出了一个最终问题，必须在他们离开前解决（是的，这扇门是数字化的，Dr. Evil 很现代）。如果他们无法解决，所有努力都将白费，他们将永远无法离开邪恶之地。你能帮助他们吗？\n\nMahmoud 和 Ehab 被给予 #cf_span[n] 个字符串 #cf_span...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**Definitions** \nLet $ n, q \\in \\mathbb{Z}^+ $ denote the number of strings and queries, respectively. \nLet $ S = (s_1, s_2, \\dots, s_n) $ be a sequence of strings over the alphabet $ \\Sigma = \\{a, ...",
"is_translate": false,
"language": "Formal"
}
]
}