| Codeforces Round 305 (Div. 1) |
|---|
| Закончено |
What-The-Fatherland — это странная страна! Все номера телефонов там представляют собой строки, состоящие из строчных букв латиницы. Вдвойне странно то, что один номер телефона может относиться к нескольким медведям!
В этой стране есть рок-группа под названием CF, состоящая из n медведей (включая Майка), пронумерованных от 1 до n.
Номер телефона i-го члена CF — si. 17 мая в стране выходной под названием День звонков. В последний День Звонков каждый медведь позвонил по всем номерам, являющимся построками его номера (возможно, по некоторому номеру пришлось позвонить несколько раз). В частности, каждый позвонил себе (это действительно странная страна!).
Обозначим как call(i, j) количество раз, которое i-й участник CF позвонил j-ому участнику CF.
У Майка есть q запросов, которые он хочет задать вам. В каждом запросе он дает вам номера l, r и k, а вы должны назвать ему число
В первой строке ввода записаны целые числа n и q (1 ≤ n ≤ 2 × 105 и 1 ≤ q ≤ 5 × 105).
В следующих n строках записаны номера телефонов, в i-й из них находится строка si, состоящая из прописных букв латиницы (
).
В следующих q строках следует описание запросов, в каждой строке записаны целые числа l, r и k (1 ≤ l ≤ r ≤ n и 1 ≤ k ≤ n).
Выведите ответ на каждый запрос на отдельной строке.
5 5
a
ab
abab
ababab
b
1 5 1
3 5 1
1 5 2
1 5 3
1 4 5
7
5
6
3
6
