CF547E.Mike and Friends

What-The-Fatherland is a strange country! All phone numbers there are strings consisting of lowercase English letters. What is double strange that a phone number can be associated with several bears!

In that country there is a rock band called CF consisting of n bears (including Mike) numbered from 1 to n.

Phone number of i-th member of CF is s__i. May 17th is a holiday named Phone Calls day. In the last Phone Calls day, everyone called all the numbers that are substrings of his/her number (one may call some number several times). In particular, everyone called himself (that was really strange country).

Denote as call(i, j) the number of times that i-th member of CF called the j-th member of CF.

The geek Mike has q questions that he wants to ask you. In each question he gives you numbers l, r and k and you should tell him the number

《父国》是一个奇特的国家！该国所有的电话号码都是由小写英文字母组成的字符串。更奇怪的是，一个电话号码可能对应多只熊！

该国有一支名为 CF 的摇滚乐队，由 $n$ 只熊（包括 Mike）组成，编号从 $1$ 到 $n$。

CF 的第 $i$ 位成员的电话号码为 $s_i$。5 月 17 日是一个名为“电话呼叫日”的节日。在上一次“电话呼叫日”，每个人都拨打了自己电话号码的所有子串所对应的号码（一个人可能多次拨打同一号码）。特别地，每个人都给自己打了一次电话（这的确是个非常奇怪的国家）。

记 $call(i, j)$ 为 CF 的第 $i$ 位成员拨打 CF 的第 $j$ 位成员的次数。

极客 Mike 向你提出了 $q$ 个问题。在每个问题中，他给出整数 $l$、$r$ 和 $k$，你需要告诉他以下表达式的值：

The first line of input contains integers n and q (1 ≤ n ≤ 2 × 105 and 1 ≤ q ≤ 5 × 105).

The next n lines contain the phone numbers, i-th line contains a string s__i consisting of lowercase English letters ().

The next q lines contain the information about the questions, each of them contains integers l, r and k (1 ≤ l ≤ r ≤ n and 1 ≤ k ≤ n).

输入的第一行包含两个整数 $n$ 和 $q$（$1 \leq n \leq 2 \times 10^5$，$1 \leq q \leq 5 \times 10^5$）。

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

再接下来的 $q$ 行描述查询信息，每行包含三个整数 $l$、$r$ 和 $k$（$1 \leq l \leq r \leq n$，$1 \leq k \leq n$）。

Print the answer for each question in a separate line.

每个问题的答案请单独打印在一行中。