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*).
class TrieNode:
    def __init__(self):
        self.children = {}
        self.count = 0

def insert_phone_number(root, phone_number):
    node = root
    for char in phone_number:
        if char not in node.children:
            node.children[char] = TrieNode()
        node = node.children[char]
        node.count += 1

def count_prefixes(root, prefix):
    node = root
    for char in prefix:
        if char not in node.children:
            return 0
        node = node.children[char]
    return node.count

n, q = map(int, input().split())

# Create an empty trie.
root = TrieNode()

# Read and insert phone numbers into the trie.
phone_numbers = []
for i in range(n):
    phone_number = input().strip()
    phone_numbers.append(phone_number)
    insert_phone_number(root, phone_number)

# Process each query.
for _ in range(q):
    l, r, k = map(int, input().split())
    l -= 1  # Adjust for 0-based indexing.
    r -= 1
    k -= 1

    # Initialize a dictionary to store the counts of phone numbers in the range [l, r].
    counts = {}

    # Count the occurrences of each phone number in the range [l, r].
    for i in range(l, r + 1):
        counts[phone_numbers[i]] = counts.get(phone_numbers[i], 0) + 1

    # Initialize the total count to 0.
    total_count = 0

    # Iterate through the unique phone numbers in the range [l, r].
    for phone_number in counts.keys():
        # Count the occurrences of the phone number in the trie.
        occurrences_in_trie = count_prefixes(root, phone_number)

        # Calculate the contribution of this phone number to the total count.
        contribution = min(counts[phone_number], occurrences_in_trie)

        # Add the contribution to the total count.
        total_count += contribution

    # Print the total count for this query.
    print(total_count)
