| Codeforces Round 326 (Div. 1) |
|---|
| Закончено |
Duff в ярости на своих друзей. От злости она просит Malek'а отнимать конфеты у её друзей безо всякого повода!
У неё n друзей. Её i-ого друга зовут si (их имена не обязательно уникальны). Она попросить Malek'а забрать конфеты у её друзей q раз. Она в ярости, но всё же она действует по определённым правилам. Когда она хочет попросить Malek'а забрать конфету у одного из её друзей, имеющего номер k, она выбирает два числа, l и r и говорит Malek'у взять ровно 
конфет у друга, где occur(t, s) — это число вхождений строки t в строку s.
Malek не может посчитать, сколько конфет надо забрать в каждом из запросов Duff. Поэтому он просит вас о помощи. Пожалуйста, скажите ему, сколько конфет взять в каждом запросе.
В первой строке входа записано два целых числа, n и q (1 ≤ n, q ≤ 105).
В следующих n строках записаны имена друзей. В i-й находится строка si из строчных букв английского алфавита (
).
В следующих q строках содержатся запросы. Каждый их них содержитпо три целых числа, l, r и k (что означает, что Malek должен взять конфет у k-го друга Duff).
Выведите ответ на каждый запрос в одной строке.
5 5
a
ab
abab
ababab
b
1 5 4
3 5 4
1 5 2
1 5 3
1 4 1
12
6
3
7
1
