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*).
# Function to build the prefix array
def build_prefix_array(phone_numbers, n):
    prefix = [[0] * (len(phone_numbers[i]) + 1) for i in range(n)]
    
    for i in range(n):
        for j in range(1, len(phone_numbers[i]) + 1):
            prefix[i][j] = prefix[i][j - 1] + (phone_numbers[i][j - 1] == phone_numbers[i][0])
    
    return prefix

# Function to answer a query
def answer_query(prefix, l, r, k):
    count = 0
    for i in range(l - 1, r):
        count += prefix[i][k]
    return count

# Read input
n, q = map(int, input().split())
phone_numbers = [input() for _ in range(n)]

# Build the prefix array
prefix = build_prefix_array(phone_numbers, n)

# Process queries and print answers
for _ in range(q):
    l, r, k = map(int, input().split())
    ans = answer_query(prefix, l, r, k)
    print(ans)
