CF587F.Duff is Mad

Duff is mad at her friends. That's why she sometimes makes Malek to take candy from one of her friends for no reason!

She has n friends. Her i-th friend's name is s__i (their names are not necessarily unique). q times, she asks Malek to take candy from her friends. She's angry, but also she acts with rules. When she wants to ask Malek to take candy from one of her friends, like k, she chooses two numbers l and r and tells Malek to take exactly candies from him/her, where occur(t, s) is the number of occurrences of string t in s.

Malek is not able to calculate how many candies to take in each request from Duff. That's why she asked for your help. Please tell him how many candies to take in each request.

达芙对她的朋友们很生气。因此，她有时会毫无理由地让马莱克从她的某个朋友那里拿走糖果！

她有 $n$ 个朋友。她的第 $i$ 个朋友的名字是 $s_i$（这些名字不一定互不相同）。共进行 $q$ 次操作，每次她都会让马莱克从她的某个朋友那里拿走糖果。虽然达芙很生气，但她行事仍遵循一定规则。当她想让马莱克从某个朋友（比如编号为 $k$ 的朋友）那里拿糖果时，她会选定两个数 $l$ 和 $r$，并告诉马莱克必须恰好拿走

颗糖果，其中 $\mathrm{occur}(t,\,s)$ 表示字符串 $t$ 在字符串 $s$ 中的出现次数。

马莱克无法计算每次达芙请求中应拿走多少颗糖果。因此，达芙请你帮忙。请告诉他每次请求中应拿走多少颗糖果。

The first line of input contains two integers n and q (1 ≤ n, q ≤ 105).

The next n lines contain the names. i-th of them contains an string s__i, consisting of lowercase English letters ().

The next q lines contain the requests. Each of them contains three integers, l, r and k (says that Malek should take candies from Duff's k-th friend).

输入的第一行包含两个整数 $n$ 和 $q$（$1 ≤ n, q ≤ 10^5$）。

接下来的 $n$ 行包含姓名，其中第 $i$ 行是一个字符串 $s_i$，由小写英文字母组成（）。

接下来的 $q$ 行包含请求，每行包含三个整数 $l$、$r$ 和 $k$（表示 Malek 应从 Duff 的第 $k$ 位朋友处取走 颗糖果）。

Print the answer to each request in one line.

每行输出每个请求的答案。