F. Махмуд, Ехаб и последнее испытание
ограничение по времени на тест
5 секунд
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Махмуд и Ехаб справились со всеми задачами Доктора Зло, поэтому он дал им пароль от двери, которая выведет их из злой страны. Когда они попытались открыть дверь, на ней отобразилась задача, которую надо решить, чтобы спастись (да, дверь цифровая, Доктор Зло любит современные технологии). Если они не решат её, все старания будут напрасными, и Махмуд и Ехаб никогда не покинут злую страну. Вы поможете им?

Махмуду и Ехабу дали 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 строках содержатся описания запросов, каждое из которых может быть одного из двух типов:

  • 1 a b (1 ≤ a ≤ b ≤ n).
  • 2 x y (1 ≤ x ≤ n), где y — строка, состоящая из строчных букв английского алфавита.

Суммарная длина всех строк во входных данных не превосходит 105

Выходные данные

Для каждого запроса первого типа выведите ответ на него в новой строке

Пример
Входные данные
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