Problem: 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. 

<image>

Phone number of i-th member of CF is si. 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 

<image>

Input

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 si consisting of lowercase English letters (<image>).

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).

Output

Print the answer for each question in a separate line.

Examples

Input

5 5
a
ab
abab
ababab
b
1 5 1
3 5 1
1 5 2
1 5 3
1 4 5


Output

7
5
6
3
6

Solution (in JAVA):

Solution:
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;
import java.util.Locale;
import java.io.Writer;
import java.io.BufferedReader;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author Yakutov Dmitry
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        FastReader in = new FastReader(inputStream);
        FastWriter out = new FastWriter(outputStream);
        TaskE solver = new TaskE();
        solver.solve(1, in, out);
        out.close();
    }

    static class TaskE {
        public void solve(int testNumber, FastReader in, FastWriter out) {
            int n = in.nextInt();
            int cntQ = in.nextInt();
            int[] summary = new int[400_400];
            int[] color = new int[summary.length];
            int[] poses = new int[n];
            int[] length = new int[n];
            int size = 0;
            for (int i = 0; i < n; ++i) {
                int[] s = SuffixArray.toIntArray(in.nextCharArray(), -'a' + 1);
                poses[i] = size;
                length[i] = s.length;
                for (int x : s) {
                    color[size] = i;
                    summary[size++] = x;
                }
                color[size] = -1;
                summary[size++] = 27 + i;
            }
            summary = Arrays.copyOf(summary, size);
            color = Arrays.copyOf(color, size);
            SuffixArray sa = new SuffixArray(summary);
            TaskE.Query[] queries = new TaskE.Query[cntQ];
            for (int i = 0; i < cntQ; i++) {
                queries[i] = new TaskE.Query(in.nextInt() - 1, in.nextInt() - 1, in.nextInt() - 1);
            }
            for (TaskE.Query q : queries) {
                int x = sa.where[poses[q.k]];
                int len = length[q.k];
                int left = x;
                int right = sa.size();
                while (right - left > 1) {
                    int y = (left + right) / 2;
                    if (sa.getLCP(x, y) >= len) {
                        left = y;
                    } else {
                        right = y;
                    }
                }
                q.right = left;
                left = -1;
                right = x;
                while (right - left > 1) {
                    int y = (left + right) / 2;
                    if (sa.getLCP(x, y) >= len) {
                        right = y;
                    } else {
                        left = y;
                    }
                }
                q.left = right;
            }
            List<TaskE.Query>[] queriesByValue = new List[n];
            for (int i = 0; i < queriesByValue.length; i++) {
                queriesByValue[i] = new ArrayList<>();
            }
            for (TaskE.Query q : queries) {
                if (q.l > 0) {
                    queriesByValue[q.l - 1].add(q);
                }
                queriesByValue[q.r].add(q);
            }
            List<Integer>[] posesByValue = new List[n];
            for (int i = 0; i < posesByValue.length; i++) {
                posesByValue[i] = new ArrayList<>();
            }
            for (int i = 0; i < color.length; i++) {
                if (color[i] >= 0) {
                    posesByValue[color[i]].add(sa.where[i]);
                }
            }
            BinaryIndexedTreeSum tree = new BinaryIndexedTreeSum(sa.size());
            for (int c = 0; c < n; c++) {
                for (Integer pos : posesByValue[c]) {
                    tree.add(pos, 1);
                }
                for (TaskE.Query q : queriesByValue[c]) {
                    int now = tree.getSum(q.left, q.right + 1);
                    if (q.l - 1 == c) {
                        now *= -1;
                    }
                    q.answer += now;
                }
            }
            for (TaskE.Query q : queries) {
                out.println(q.answer);
            }
        }

        class Query {
            int l;
            int r;
            int k;
            int left;
            int right;
            int answer;

            public Query(int l, int r, int k) {
                this.l = l;
                this.r = r;
                this.k = k;
            }

        }

    }

    static class BinaryIndexedTreeSum {
        public final int n;
        private int[] a;

        public BinaryIndexedTreeSum(int n) {
            this.n = n;
            a = new int[n + 1];
        }

        public int getPrefixSum(int bound) {
            int res = 0;
            for (int i = bound; i > 0; i -= i & -i) {
                res += a[i];
            }
            return res;
        }

        public int getSum(int l, int r) {
            return getPrefixSum(r) - getPrefixSum(l);
        }

        public void add(int pos, int value) {
            for (int i = pos + 1; i <= n; i += i & -i) {
                a[i] += value;
            }
        }

    }

    static class SuffixArray {
        public int n;
        public int alphabet;
        public int[] a;
        public int[] sa;
        public int[] newSa;
        public int[] cl;
        public int[] newCl;
        public int[] start;
        public int[] where;
        public int[] lcp;
        public SparseTableMin table;

        public int size() {
            return n;
        }

        public SuffixArray(int[] a) {
            n = a.length;
            this.a = a.clone();
            sa = new int[n];
            newSa = new int[n];
            alphabet = 0;
            for (int x : a) {
                alphabet = Math.max(alphabet, x);
            }
            alphabet += 2;
            cl = new int[Math.max(n, alphabet)];
            newCl = new int[cl.length];
            start = new int[cl.length];
            where = new int[n];
            build();
        }

        public static int[] toIntArray(char[] s, int shift) {
            int[] a = new int[s.length];
            for (int i = 0; i < s.length; i++) {
                a[i] = s[i] + shift;
            }
            return a;
        }

        public void buildLCP() {
            lcp = new int[n - 1];
            int last = 0;
            for (int i = 0; i < n; i++) {
                if (last > 0) {
                    last--;
                }
                if (where[i] == n - 1) {
                    last = 0;
                    continue;
                }
                int j = sa[where[i] + 1];
                while (i + last < n && j + last < n && a[i + last] == a[j + last]) {
                    last++;
                }
                lcp[where[i]] = last;
            }
            table = null;
        }

        public int getLCP(int ithPosInSA, int jthPosInSA) {
            if (ithPosInSA == jthPosInSA) {
                return n - sa[ithPosInSA];
            }
            if (lcp == null) {
                buildLCP();
            }
            if (ithPosInSA > jthPosInSA) {
                int temp = ithPosInSA;
                ithPosInSA = jthPosInSA;
                jthPosInSA = temp;
            }
            if (ithPosInSA + 1 == jthPosInSA) {
                return lcp[ithPosInSA];
            }
            if (table == null) {
                table = new SparseTableMin(lcp);
            }
            return table.getMin(ithPosInSA, jthPosInSA);
        }

        private void build() {
            System.arraycopy(a, 0, cl, 0, a.length);
            Arrays.fill(start, 0);
            for (int i = 0; i < n; i++) {
                start[cl[i] + 1]++;
            }
            for (int i = 1; i < alphabet; i++) {
                start[i] += start[i - 1];
            }
            for (int i = 0; i < n; i++) {
                sa[start[cl[i]]++] = i;
            }
            Arrays.fill(start, 0);
            for (int i = 0; i < n; i++) {
                start[cl[i] + 1]++;
            }
            for (int i = 1; i < alphabet; i++) {
                start[i] += start[i - 1];
            }
            for (int half = 1; half < n; half *= 2) {
                for (int i = 0; i < n; i++) {
                    sa[i] -= half;
                    if (sa[i] < 0) sa[i] += n;
                }
                for (int i = 0; i < n; i++) {
                    int x = sa[i];
                    newSa[start[cl[x]]++] = x;
                }
                newCl[newSa[0]] = 0;
                int last = 0;
                start[0] = 0;
                for (int i = 0; i + 1 < n; i++) {
                    int x = newSa[i];
                    int y = newSa[i + 1];
                    int xx = x + half;
                    if (xx >= n) xx -= n;
                    int yy = y + half;
                    if (yy >= n) yy -= n;
                    if (cl[x] != cl[y] || cl[xx] != cl[yy]) {
                        newCl[y] = ++last;
                        start[last] = i + 1;
                    } else {
                        newCl[y] = newCl[x];
                    }
                }
                int[] temp = cl;
                cl = newCl;
                newCl = temp;
                temp = sa;
                sa = newSa;
                newSa = temp;
            }
            for (int i = 0; i < n; i++) {
                where[sa[i]] = i;
            }
        }

    }

    static class FastReader {
        private StringTokenizer tokenizer;
        private BufferedReader reader;

        public FastReader(InputStream inputStream) {
            reader = new BufferedReader(new InputStreamReader(inputStream));
        }

        public String nextToken() {
            try {
                while (tokenizer == null || !tokenizer.hasMoreElements()) {
                    tokenizer = new StringTokenizer(reader.readLine());
                }
                return tokenizer.nextToken();
            } catch (IOException e) {
                return null;
            }
        }

        public int nextInt() {
            return Integer.parseInt(nextToken());
        }

        public char[] nextCharArray() {
            String next = nextToken();
            if (next == null) {
                return null;
            }
            return next.toCharArray();
        }

    }

    static class SparseTableMin {
        private int[][] a;
        private int[] deg;

        public SparseTableMin(int[] array) {
            int n = array.length;
            int log = 1;
            while ((1 << (log - 1)) < n) {
                log++;
            }
            a = new int[log][];
            a[0] = array.clone();
            for (int i = 1; i < log; i++) {
                int len = 1 << i;
                a[i] = new int[n];
                for (int j = 0; j + len <= a[i].length; j++) {
                    a[i][j] = Math.min(a[i - 1][j], a[i - 1][j + (len >> 1)]);
                }
            }
            deg = new int[n + 1];
            for (int i = 2; i <= n; i++) {
                deg[i] = 1 + deg[i >> 1];
            }
        }

        public int getMin(int left, int right) {
            int i = deg[right - left];
            return Math.min(a[i][left], a[i][right - (1 << i)]);
        }

    }

    static class FastWriter extends PrintWriter {
        public FastWriter(OutputStream out) {
            super(out);
        }

        public FastWriter(Writer out) {
            super(out);
        }

        public PrintWriter printf(String format, Object... args) {
            return super.format(Locale.US, format, args);
        }

        public void close() {
            super.close();
        }

    }
}