1-й квалификационный раунд завершен

Задания

Показывать по одной задаче на странице / все задачи на одной странице

"E" ЛИСА
Ограничение по времени 3 секунды
Ограничение по памяти 256 мегабайт

Илья работает в Лаборатории Изучения Строковых Алгоритмов (ЛИСА). Сейчас он пытается решить такую задачу.

Задан массив строк s1, s2, ..., sn и q запросов. Каждый запрос характеризуется двумя целыми числами li и ri (1 ≤ li ≤ ri ≤ n). Для ответа на запрос необходимо сделать следующее. Назовем строку представимой, если ее можно получить следующим образом: выберем две строки sx и sy, где li ≤ x, y ≤ ri, выберем непустой префикс строки sx и непустой суффикс строки sy, возьмем их конкатенацию. Ответом на запрос является количество различных представимых строк для заданных li и ri.

Например, пусть s = [abc, ab, ac, bcac], выберем li = 2, ri = 3. Представимыми будут строки:

x = 2, y = 2: ab = a + b, aab = a + ab, abb = ab + b, abab = ab + ab.

x = 2, y = 3: ac = a + c, aac = a + ac, abc = ab + c, abac = ab + ac.

x = 3, y = 2: ab = a + b, aab = a + ab, acb = ac + b, acab = ac + ab.

x = 3, y = 3: ac = a + c, aac = a + ac, acc = ac + c, acac = ac + ac.

Всего получилось 12 различных представимых строк.

Помогите Илье решить задачу достаточно быстро.

Формат входных данных

В первой строке заданы два целых числа n и q — количество слов и запросов соответственно (1 ≤ n, q ≤ 105).

Каждая из следующих n строк содержит непустые слова si, состоящие из строчных латинских букв. Суммарная длина всех слов не превосходит 105.

Следующие q строк содержат пары чисел li, ri (1 ≤ li ≤ ri ≤ n) — левая и правая граница i-го запроса соответственно.

Формат выходных данных

Выведите q строк, i-я из них должна содержать единственное целое число — ответ на i-й запрос.

Примеры
Входные данные
4 3
abc
ab
ac
bcac
3 4
1 3
2 3
Выходные данные
20
23
12
 

Отправить решение

Загрузить Максимальный размер - 256 Кб

Вход

ВКонтакте Facebook It.Mail

Забыли пароль?

Регистрация

На вашу электронную почту была
отправлена инструкция по восстановлению пароля.