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*<sub class="lower-index">*i*</sub>. 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
The first line of input contains integers *n* and *q* (1 ≤ *n* ≤ 2 × 10<sup class="upper-index">5</sup> and 1 ≤ *q* ≤ 5 × 10<sup class="upper-index">5</sup>).

The next *n* lines contain the phone numbers, *i*-th line contains a string *s*<sub class="lower-index">*i*</sub> consisting of lowercase English letters (<img align="middle" class="tex-formula" src="https://espresso.codeforces.com/b60bbd11dae7b5f43c55918a57e5e68833b6b60a.png" style="max-width: 100.0%;max-height: 100.0%;"/>).

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*).
def find_tel(q,l,d):
    sum=0
    tofind=l[int(q[2])-1]
    if tofind not in d.keys():
        d[tofind]={}
    for i in range (int(q[0])-1,int(q[1])):
        if i in d[tofind].keys():
            sum=sum+d[tofind][i]
        else:
            if len(l[i])>=len(tofind):
                if l[i]==tofind:
                    sum+=1
                    d[tofind][i]=1
                else:
                    if tofind in l[i]:
                        indice=0
                        sum2=0
                        while indice + len(tofind)<=len(l[i]):
                            if tofind in l[i][indice:]:
                                if l[i][indice:indice + len(tofind)]==tofind:
                                    sum+=1
                                    sum2+=1
                                    indice+=1
                                else:
                                    indice+=1
                            else:
                                break
                        d[tofind][i]=sum2
    return sum,d
    
lines=[]
result=[]
n=input()
n=n.split()
dic={}
for _ in range (0, int(n[0])):
    lines.append(input())
for _ in range (0, int(n[1])):
    question=input()
    question=question.split()
    resu,dic=find_tel(question,lines,dic)
    result.append(resu)
for i in result:
    print(i)