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.util.List;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.ArrayList;
import java.io.BufferedReader;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.StringTokenizer;
import java.math.BigInteger;
import java.util.Collections;
import java.io.InputStream;

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

class TaskE_MaikAndFriends {
    public static char DELIM = '#';
    private String[] words;
    private SuffixArray suffixArray;
    int[] realPos;

    public void solve(int testNumber, InputReader in, PrintWriter out) {
        int countWords = in.nextInt();
        int countQueries = in.nextInt();
        StringBuilder bigWord = new StringBuilder("");
        words = new String[countWords];
        for (int i = 0; i < countWords; ++i) {
            words[i] = in.nextString();
            bigWord.append(words[i]).append(DELIM);
        }
        String word = bigWord.toString();
        int[] wordOnPos = new int[word.length()];
        int curWord = 0;
        realPos = new int[countWords];
        realPos[0] = 0;
        Arrays.fill(wordOnPos, -1);
        for (int i = 0; i < word.length(); ++i) {
            if (word.charAt(i) == DELIM) {
                ++curWord;
                if (curWord < countWords) {
                    realPos[curWord] = i + 1;
                }
            } else {
                wordOnPos[i] = curWord;
            }
        }
        suffixArray = new SuffixArray(word);
        rmq = new SparseTable(suffixArray.lcp);
        Query[] queries = new Query[countQueries];
        for (int i = 0; i < countQueries; ++i) {
            queries[i] = new Query(in.nextInt() - 1, in.nextInt() - 1, in.nextInt() - 1, i);
        }

        List<NewQuery> qs = new ArrayList<NewQuery>(4 * queries.length);
        for (Query query : queries) {
            qs.add(new NewQuery(true, query.right, query.lastIdInArray, query.id));
            if (query.firstIdInArray >= 1) {
                qs.add(new NewQuery(false, query.right, query.firstIdInArray - 1, query.id));
            }

            if (query.left >= 1) {
                qs.add(new NewQuery(false, query.left - 1, query.lastIdInArray, query.id));
                if (query.firstIdInArray >= 1) {
                    qs.add(new NewQuery(true, query.left - 1, query.firstIdInArray - 1, query.id));
                }
            }
        }

        Collections.sort(qs);
        FenwickTreeSum sum = new FenwickTreeSum(countWords);
        int ptr = 0;
        int[] res = new int[countQueries];
        for (int x = 0; x < suffixArray.n; ++x) {
            int number = wordOnPos[suffixArray.p[x]];
            if (number != -1) {
                sum.update(number, 1);
            }
            while (ptr < qs.size()) {
                if (qs.get(ptr).x == x) {
                    if (qs.get(ptr).lessThan >= 0) {
                        res[qs.get(ptr).qId] += (qs.get(ptr).sign ? 1 : -1) * sum.getPrefixSum(qs.get(ptr).lessThan);
                    }
                    ++ptr;
                } else {
                    break;
                }
            }
        }
        for (int i : res) {
            out.println(i);
        }
    }

    SparseTable rmq;

//    class SegmentTree {
//        int[] min;
//        int[] a;
//        int size;
//
//        SegmentTree(int size, int[] a) {
//            this.size = size;
//            min = new int[size * 4];
//            this.a = a;
//            buildTree(1, 0, size);
//        }
//
//        void buildTree(int v, int le, int ri) {
//            if (le + 1 == ri) {
//                min[v] = a[le];
//            } else {
//                int e = (le + ri) >> 1;
//                buildTree(v * 2, le, e);
//                buildTree(v * 2 + 1, e, ri);
//                min[v] = Math.min(min[v * 2], min[2 * v + 1]);
//            }
//        }
//
//        int getMin(int le, int ri) {
//            return internalMin(1, le, ri + 1, 0, size);
//        }
//
//        private int internalMin(int v, int le, int ri, int rLe, int rRi) {
//            if (le >= rRi || rLe >= ri) {
//                return Integer.MAX_VALUE;
//            }
//            if (rLe >= le && rRi <= ri) {
//                return min[v];
//            }
//            int e = (rLe + rRi) / 2;
//            return Math.min(internalMin(v * 2, le, ri, rLe, e), internalMin(v * 2 + 1, le, ri, e, rRi));
//        }
//    }

    class NewQuery implements Comparable<NewQuery> {
        boolean sign;
        int lessThan;
        int x;
        int qId;

        public NewQuery(boolean sign, int lessThan, int x, int qId) {
            this.sign = sign;
            this.lessThan = lessThan;
            this.x = x;
            this.qId = qId;
        }

        public int compareTo(NewQuery q) {
            return x - q.x;
        }
    }

    public static int BUBEN = 14;

    class SparseTable {
        int[][] table;

        public SparseTable(int[] level) {
            table = new int[BUBEN][level.length];
            table[0] = level.clone();
            for (int i = 1; i < BUBEN; ++i) {
                for (int j = 0; j < level.length; ++j) {
                    int prevLen = (1 << (i-1));
                    table[i][j] = table[i-1][j];
                    if (j + prevLen < level.length) {
                        table[i][j] = Math.min(table[i - 1][j], table[i - 1][j + prevLen]);
                    }
                }
            }
        }

        int getMin(int from, int to) {
            int len = to - from + 1;
            int log2 = Math.min(BUBEN-1, Integer.numberOfTrailingZeros(Integer.highestOneBit(len)));
            int lenToSearch = (1 << log2);
            int res = table[log2][from];
            for (int cur = from + lenToSearch; cur <= to - lenToSearch + 1; cur += lenToSearch) res = Math.min(res, table[log2][cur]);
            return Math.min(res, table[log2][to - lenToSearch + 1]);
            //Math.min(table[log2][from], table[log2][to - lenToSearch + 1]);
        }
    }

    class Query {
        int k;
        int left, right;
        int id;
        int firstIdInArray = -1;
        int lastIdInArray = -1;

        public Query(int left, int right, int k, int id) {
            this.k = k;
            this.left = left;
            this.right = right;
            this.id = id;

            firstIdInArray = suffixArray.p2[realPos[k]];
            int le = 0, ri = suffixArray.p2[realPos[k]] - 1, middle;
            while (le <= ri) {
                middle = (le + ri) / 2;
                if (rmq.getMin(middle, suffixArray.p2[realPos[k]] - 1) >= words[k].length()) {
                    firstIdInArray = middle;
                    ri = middle - 1;
                } else {
                    le = middle + 1;
                }
            }

            lastIdInArray = suffixArray.p2[realPos[k]];
            le = suffixArray.p2[realPos[k]] + 1;
            ri = suffixArray.n - 1;
            while (le <= ri) {
                middle = (le + ri) / 2;
                if (rmq.getMin(suffixArray.p2[realPos[k]], middle - 1) >= words[k].length()) {
                    lastIdInArray = middle;
                    le = middle + 1;
                } else {
                    ri = middle - 1;
                }
            }
        }
    }

}

class SuffixArray {
    public int[] s;
    public int n;
    int[] c;
    int[] c2;
    public int[] p;
    public int[] p2;
    public int[] lcp;
    int[] num;
    int[] pos;

    public SuffixArray(String s) {
        char[] cc = s.toCharArray();
        this.s = new int[cc.length];
        for (int i = 0; i < cc.length; ++i) {
            this.s[i] = cc[i];
        }
        n = s.length();
        c = new int[n];
        c2 = new int[n];
        p = new int[n];
        p2 = new int[n];
        lcp = new int[n];
        num = new int[Math.max(n+1, 500)];
        pos = new int[Math.max(1+n, 500)];
        build();
    }

    private void build() {
        for (int i = 0; i < n; ++i) {
            c[i] = s[i];
            p[i] = i;
        }
        for (int k = 0, k1 = 1; k < n; k = k1, k1 <<= 1) {
            Arrays.fill(num, 0);
            for (int i = 0; i < n; ++i) ++num[c[i]];
            pos[0] = 0;
            for (int i = 0; i < num.length-1; ++i) pos[i+1] = pos[i] + num[i];   /// ???
            for (int i = 0; i < n; ++i) {
                int j = (p[i] - k + n) % n;
                p2[pos[c[j]]++] = j;
            }
            int cc = 0;
            for (int i = 0; i < n; ++i) {
                if (i > 0 && (c[p2[i-1]] != c[p2[i]] || c[(p2[i-1]+k)%n] != c[(p2[i]+k)%n])) ++cc;
                c2[p2[i]] = cc;
            }
            for (int i = 0; i < n; ++i) {
                c[i] = c2[i];
                p[i] = p2[i];
            }
        }
        for (int i = 0; i < n; ++i) p2[p[i]] = i;
        int k = 0;
        for (int i = 0; i < n; ++i) {
            if (p2[i] == n-1) {
                lcp[p2[i]] = k = 0;
                continue;
            }
            if (k > 0) --k;
            int j = p[p2[i]+1];
            while (k < n && s[(i + k) % n] == s[(j + k) % n]) ++k;
            lcp[p2[i]] = k;
            if (p2[(i + 1) % n] > p2[(j + 1) % n]) k = 0;
        }
    }
}

class InputReader {
    private BufferedReader reader;
    private StringTokenizer stt;

    public InputReader(InputStream stream) {
        reader = new BufferedReader(new InputStreamReader(stream));
    }

    public String nextLine() {
        try {
            return reader.readLine();
        } catch (IOException e) {
            return null;
        }
    }

    public String nextString() {
        while (stt == null || !stt.hasMoreTokens()) {
            stt = new StringTokenizer(nextLine());
        }
        return stt.nextToken();
    }

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

}

class FenwickTreeSum {
    long[] sum;
    int n;

    public FenwickTreeSum(int n) {
        this.n = n;
        sum = new long[n+1];
        Arrays.fill(sum, 0);
    }

    public void update(int position, long value) {
        ++position;
        for (int i = position; i <= n; i = next(i)) {
            sum[i] += value;
        }
    }

    public long getPrefixSum(int position) {
        ++position;
        long result = 0;
        for (int i = position; i > 0; i = prev(i)) {
            result += sum[i];
        }
        return result;
    }

    private static int prev(int x) {
        return (x & (x - 1));
    }

    private static int next(int x) {
        return (x << 1) - prev(x);
    }
}