Махмуд и Ехаб справились со всеми задачами Доктора Зло, поэтому он дал им пароль от двери, которая выведет их из злой страны. Когда они попытались открыть дверь, на ней отобразилась задача, которую надо решить, чтобы спастись (да, дверь цифровая, Доктор Зло любит современные технологии). Если они не решат её, все старания будут напрасными, и Махмуд и Ехаб никогда не покинут злую страну. Вы поможете им?
Махмуду и Ехабу дали 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.
Выходные данные
Для каждого запроса первого типа выведите ответ на него в новой строке
Примеры
| № | Входные данные | Выходные данные |
|
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
|
14
14
13
30
12
7
|