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*).
if True:
    from io import BytesIO, IOBase
    import math

    import random
    import sys
    import os

    import bisect
    import typing
    from collections import Counter, defaultdict, deque
    from copy import deepcopy
    from functools import cmp_to_key, lru_cache, reduce
    from heapq import heapify, heappop, heappush, heappushpop, nlargest, nsmallest
    from itertools import accumulate, combinations, permutations, count
    from operator import add, iand, ior, itemgetter, mul, xor
    from string import ascii_lowercase, ascii_uppercase, ascii_letters
    from typing import *
    BUFSIZE = 4096

    class FastIO(IOBase):
        newlines = 0

        def __init__(self, file):
            self._fd = file.fileno()
            self.buffer = BytesIO()
            self.writable = "x" in file.mode or "r" not in file.mode
            self.write = self.buffer.write if self.writable else None

        def read(self):
            while True:
                b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
                if not b:
                    break
                ptr = self.buffer.tell()
                self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
            self.newlines = 0
            return self.buffer.read()

        def readline(self):
            while self.newlines == 0:
                b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
                self.newlines = b.count(b"\n") + (not b)
                ptr = self.buffer.tell()
                self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
            self.newlines -= 1
            return self.buffer.readline()

        def flush(self):
            if self.writable:
                os.write(self._fd, self.buffer.getvalue())
                self.buffer.truncate(0), self.buffer.seek(0)

    class IOWrapper(IOBase):
        def __init__(self, file):
            self.buffer = FastIO(file)
            self.flush = self.buffer.flush
            self.writable = self.buffer.writable
            self.write = lambda s: self.buffer.write(s.encode("ascii"))
            self.read = lambda: self.buffer.read().decode("ascii")
            self.readline = lambda: self.buffer.readline().decode("ascii")

    sys.stdin = IOWrapper(sys.stdin)
    sys.stdout = IOWrapper(sys.stdout)
    input = lambda: sys.stdin.readline().rstrip("\r\n")
    
    def I():
        return input()

    def II():
        return int(input())

    def MII():
        return map(int, input().split())

    def LI():
        return list(input().split())

    def LII():
        return list(map(int, input().split()))

    def LFI():
        return list(map(float, input().split()))

    def GMI():
        return map(lambda x: int(x) - 1, input().split())

    def LGMI():
        return list(map(lambda x: int(x) - 1, input().split()))

    inf = float('inf')

dfs, hashing = True, True

if dfs:
    from types import GeneratorType

    def bootstrap(f, stack=[]):
        def wrappedfunc(*args, **kwargs):
            if stack:
                return f(*args, **kwargs)
            else:
                to = f(*args, **kwargs)
                while True:
                    if type(to) is GeneratorType:
                        stack.append(to)
                        to = next(to)
                    else:
                        stack.pop()
                        if not stack:
                            break
                        to = stack[-1].send(to)
                return to
        return wrappedfunc

if hashing:
    RANDOM = random.getrandbits(20)
    class Wrapper(int):
        def __init__(self, x):
            int.__init__(x)

        def __hash__(self):
            return super(Wrapper, self).__hash__() ^ RANDOM

class SparseTable:
    def __init__(self, data, merge_method):
        self.note = [0] * (len(data) + 1)
        self.merge_method = merge_method
        l, r, v = 1, 2, 0
        while True:
            for i in range(l, r):
                if i >= len(self.note):
                    break
                self.note[i] = v
            else:
                l *= 2
                r *= 2
                v += 1
                continue
            break
        self.ST = [[0] * len(data) for _ in range(self.note[-1]+1)]
        self.ST[0] = data
        for i in range(1, len(self.ST)):
            for j in range(len(data) - (1 << i) + 1):
                self.ST[i][j] = merge_method(self.ST[i-1][j], self.ST[i-1][j + (1 << (i-1))])

    def query(self, l, r):
        if l > r: return inf
        pos = self.note[r-l+1]
        return self.merge_method(self.ST[pos][l], self.ST[pos][r - (1 << pos) + 1])

class FenwickTree:
    def __init__(self, n):
        self.n = n
        self.bit = [0] * n
        length = (self.n + 1).bit_length() - 1
        self.powers = [1 << i for i in range(length, -1, -1)]
        self.tot = 0

    def sum(self, r):
        res = 0
        while r >= 0:
            res += self.bit[r]
            r = (r & (r + 1)) - 1
        return res

    def rsum(self, l, r):
        return self.sum(r) - self.sum(l - 1)

    def add(self, idx, delta):
        while idx < self.n:
            self.bit[idx] += delta
            idx = idx | (idx + 1)
        self.tot += delta

def sa_naive(s):
    n = len(s)
    return sorted(range(n), key=lambda i: s[i:])

def sa_doubling(s):
    def key(i):
        if i + k < n:
            return rank[i], rank[i + k]
        return rank[i], -1

    smax = max(s) + 1
    n = len(s)
    sa = list(range(n))
    rank = s[:]
    tmp = [0] * n

    k = 1
    while k < n:
        sa.sort(key=key)
        tmp[sa[0]] = 0
        for i in range(1, n):
            tmp[sa[i]] = tmp[sa[i-1]] + (key(sa[i-1]) < key(sa[i]))
        rank, tmp = tmp, rank
        k <<= 1
    return sa

def sa_is(s, upper, THRESHHOLD_NAIVE=20, THRESHHOLD_DOUBLE=100):
    def induce(lms):
        for i in range(n):
            sa[i] = -1
        buf = sum_s[:]
        for d in lms:
            if d == n:
                continue
            sa[buf[s[d]]] = d
            buf[s[d]] += 1

        buf = sum_l[:]
        sa[buf[s[n - 1]]] = n - 1
        buf[s[n - 1]] += 1
        for i in range(n):
            v = sa[i]
            if v >= 1 and not ls[v - 1]:
                sa[buf[s[v - 1]]] = v - 1
                buf[s[v - 1]] += 1

        buf = sum_l[:]
        for i in range(n)[::-1]:
            v = sa[i]
            if v >= 1 and ls[v - 1]:
                buf[s[v - 1] + 1] -= 1
                sa[buf[s[v - 1] + 1]] = v - 1

    n = len(s)
    if n == 0:
        return []
    if n == 1:
        return [0]
    if n <= THRESHHOLD_NAIVE:
        return sa_naive(s)
    if n <= THRESHHOLD_DOUBLE:
        return sa_doubling(s)

    sa = [0] * n
    ls = [0] * n
    for i in range(n - 1)[::-1]:
        if s[i] == s[i + 1]:
            ls[i] = ls[i + 1]
        else:
            ls[i] = int(s[i] < s[i + 1])

    sum_l = [0] * (upper + 1)
    sum_s = [0] * (upper + 1)
    for i, x in enumerate(ls):
        if not x:
            sum_s[s[i]] += 1
        else:
            sum_l[s[i] + 1] += 1
    for i in range(upper + 1):
        sum_s[i] += sum_l[i]
        if i < upper:
            sum_l[i + 1] += sum_s[i]

    lms_map = [-1] * (n + 1)
    lms = []
    m = 0
    for i in range(1, n):
        if not ls[i - 1] and ls[i]:
            lms_map[i] = m
            lms.append(i)
            m += 1

    induce(lms)

    if m:
        sorted_lms = []
        for v in sa:
            if v == -1:
                print("minuse")
            if lms_map[v] != -1:
                sorted_lms.append(v)

        rec_s = [0] * m
        rec_upper = 0
        rec_s[lms_map[sorted_lms[0]]] = 0
        for i in range(1, m):
            l = sorted_lms[i - 1]
            r = sorted_lms[i]
            end_l = lms[lms_map[l] + 1] if lms_map[l] + 1 < m else n
            end_r = lms[lms_map[r] + 1] if lms_map[r] + 1 < m else n
            same = 1
            if end_l - l != end_r - r:
                same = 0
            else:
                while l < end_l:
                    if s[l] != s[r]:
                        break
                    l += 1
                    r += 1
                if l == n or s[l] != s[r]:
                    same = 0
            if not same:
                rec_upper += 1
            rec_s[lms_map[sorted_lms[i]]] = rec_upper

        rec_sa = sa_is(rec_s, rec_upper)
        for i in range(m):
            sorted_lms[i] = lms[rec_sa[i]]
        induce(sorted_lms)
    return sa

def suffix_array(S, compress=True):
    if compress:
        ch = sorted(set(S))
        ctoi = {c: i for i, c in enumerate(ch, 1)}
        S = [ctoi[s] for s in S]

    upper = max(S) + 1
    return sa_is(S, upper)

def construct_lcp(s, sa):
    n = len(s)
    assert(n >= 1)
    rank = [0] * n
    for i in range(n):
        rank[sa[i]] = i

    lcp = [0] * n
    h = 0
    for i in range(n):
        if h > 0:
            h -= 1
        if rank[i] == 0:
            continue
        j = sa[rank[i] - 1]
        while j + h < n and i + h < n:
            if s[j + h] != s[i + h]:
                break
            h += 1
        lcp[rank[i] - 1] = h
    return lcp

n, q = MII()
strs = [I() for _ in range(n)]

s = '#'.join(strs)
start = []
group = []
for i in range(n):
    start.append(len(group))
    group.extend([i] * len(strs[i]))
    group.append(-1)

sa = suffix_array(s)
pos = [None] * len(sa)
for i, v in enumerate(sa):
    pos[v] = i

lcp = construct_lcp(s, sa)
st = SparseTable(lcp, min)

left = [None] * n
right = [None] * n
for i in range(n):
    l, r = 0, pos[start[i]]
    while l <= r:
        m = (l + r) // 2
        if st.query(m, pos[start[i]] - 1) >= len(strs[i]):
            r = m - 1
        else:
            l = m + 1
    left[i] = l
    l, r = pos[start[i]], len(s) - 1
    while l <= r:
        m = (l + r) // 2
        if st.query(pos[start[i]], m - 1) >= len(strs[i]):
            l = m + 1
        else: 
            r = m - 1
    right[i] = r
del lcp, st, pos, start

group = [group[i] for i in sa]
del sa

queries = [[] for _ in range(len(s) + 1)]
for q_idx in range(q):
    l, r, k = GMI()
    queries[left[k]].append((~q_idx, l, r))
    queries[right[k] + 1].append((q_idx, l, r))
del left, right

ans = [0] * q
fen = FenwickTree(n)
for i in range(len(s) + 1):
    for q, l, r in queries[i]:
        if q >= 0: ans[q] += fen.rsum(l, r)
        else: ans[~q] -= fen.rsum(l, r)
    if i < len(s) and group[i] >= 0:
        fen.add(group[i], 1)

print(*ans, sep='\n')