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
4000 ms 256 Mb Правила оформления программ и список ошибок при автоматической проверке задач