Codeforces Round 435 (Div. 2) |
---|
Закончено |
Махмуд и Ехаб справились со всеми задачами Доктора Зло, поэтому он дал им пароль от двери, которая выведет их из злой страны. Когда они попытались открыть дверь, на ней отобразилась задача, которую надо решить, чтобы спастись (да, дверь цифровая, Доктор Зло любит современные технологии). Если они не решат её, все старания будут напрасными, и Махмуд и Ехаб никогда не покинут злую страну. Вы поможете им?
Махмуду и Ехабу дали n строк s1, s2, ... , sn, пронумерованных от 1 до n, и q запросов. Каждый запрос относится к одному из двух типов:
(r - l + 1) * LCP(sl, sl + 1, ... , sr - 1, sr) где LCP(str1, str2, str3, ... )— это длина наибольшего общего префикса строк str1, str2, str3, ... .
В первой строке содержатся 2 целых числа n и q (1 ≤ n ≤ 105, 1 ≤ q ≤ 105) – число строк и число запросов, соответственно.
Во второй строке содержатся n строк stri состоящих из строчных букв английского алфавита.
В следующих q строках содержатся описания запросов, каждое из которых может быть одного из двух типов:
Суммарная длина всех строк во входных данных не превосходит 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
Название |
---|