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.net.*;
import java.io.*;
import java.util.*;

public class Main {
	public static void main(String[] args) throws IOException {
		new TaskE().solve();
	}
}

class TaskE {
	final int N = 423456;
	void solve() throws IOException{

		Reader in = new Reader();
		StringBuilder res = new StringBuilder("");
		in.init(System.in);
		int n = in.nextInt();
		int Q = in.nextInt();
		
		int[] str = new int[N];
		int[] off = new int[N];
		int[] len = new int[N];
		int[] wh  = new int[N];
		Arrays.fill(wh, -1);
		
		for (int i = 0; i < n; i++) {
			String s = in.next();
			off[i]   = i == 0 ? 0 : off[i-1] + len[i-1] + 1;
			len[i]   = s.length();
			for (int j = 0; j < s.length(); j++) {
				wh[off[i]+j] = i;
				str[off[i]+j] = s.charAt(j) - 'a';
			}
			str[off[i]+len[i]] = 30;
		}
		int size = off[n-1] + len[n-1] + 1;
		
		SuffixArray sa = new SuffixArray();
		sa.makeSA(str, size + 1, 50);
		
		ArrayList[] query = new ArrayList[size];
		for (int i = 0; i < size; i++)
			query[i] = new ArrayList<Query>();

		for (int q = 0; q < Q; q++) {
			int l = in.nextInt() - 1;
			int r = in.nextInt() - 1;
			int K = in.nextInt() - 1;
			int M = sa.rank[off[K]];
			int L = 0, R = size - 1;
			int left = L, right = M;
			while (left < right) {
				int mid = (left + right) >> 1;
				if (sa.lcpInSA(mid, M) >= len[K])
					right = mid;
				else
					left = mid + 1;
			}
			L = left;
			left = M; right = R;
			while (left < right) {
				int mid = (left + right + 1) >> 1;
				if (sa.lcpInSA(mid, M) >= len[K])
					left = mid;
				else
					right = mid - 1;
			}
			R = right;


			query[R].add(new Query(q, r, true));
			query[R].add(new Query(q, l-1, false));
			if (L > 0) {
				query[L-1].add(new Query(q, r, false));
				query[L-1].add(new Query(q, l-1, true));
			}
		}

		int[] ans = new int[Q];
		BIT bit = new BIT(n + 10);
		for (int i = 0; i < size; i++) {
			if (wh[sa.SA[i]] != -1) 
				bit.add(wh[sa.SA[i]], 1);
			for (Query que : (ArrayList<Query>) query[i]) 
				ans[que.id] += bit.get(que.m) * (que.plus ? 1 : -1);
		}

		for (int i = 0; i < Q; i++)
			res.append(ans[i] + "\r\n");
		System.out.print(res);
	}
}

class Query {
	int id, m;
	boolean plus;
	Query(int id, int m, boolean plus) {
		this.id = id;
		this.m = m;
		this.plus = plus;
	}
}

class BIT {
	int n;
	int[] sum;
	BIT(int n) {
		this.n = n;
		sum = new int[n + 10];
	}

	void add(int w, int x) {
		w++;
		while (w <= n) {
			sum[w] += x;
			w += w & (-w);
		}
	}
	int get(int x) {
		x++;
		int ret = 0;
		while (x > 0) {
			ret += sum[x];
			x -= x & (-x);
		}
		return ret;
	}
}

class SuffixArray {
	int n;
	int[] SA, rank, height, cnt;

	void radixSort(int[] digit, int[] osa, int[] nsa, int n, int m) {
		Arrays.fill(cnt, 0);
		for (int i = 0; i < n; i++)
			cnt[digit[i]]++;
		for (int i = 1; i <= m; i++)
			cnt[i] += cnt[i-1];
		for (int i = n - 1; i >= 0; i--)
			nsa[--cnt[digit[osa[i]]]] = osa[i];
	}
	
	int[] first, second, log;
	int[][] rmq;
	void makeSA(int[] str, int n, int m) {
		this.n = n;
		SA     = new int[n + m];
		rank   = new int[n + m]; 
		height = new int[n + m];
		cnt    = new int[n + m];
		first  = new int[n + m];
		second = new int[n + m];

		for (int i = 0; i < n; i++)
			rank[i] = i;
		radixSort(str, rank, SA, n, m);

		rank[SA[0]] = 0;
		for (int i = 1; i < n; i++)
			rank[SA[i]] = rank[SA[i-1]] + (str[SA[i]] == str[SA[i-1]] ? 0 : 1);

		for (int i = 0; (1 << i) < n; i++) {
			for (int j = 0; j < n; j++) {
				first[j] = rank[j];
				second[j] = (j+(1<<i)) < n ? rank[j+(1<<i)]+1 : 0;
			}
			radixSort(second, SA, rank, n, n);
			radixSort(first, rank, SA, n, n);
			
			rank[SA[0]] = 0;
			for (int j = 1; j < n; j++)
				rank[SA[j]] = rank[SA[j-1]] + (first[SA[j]]==first[SA[j-1]]&&second[SA[j]]==second[SA[j-1]] ? 0 : 1);
		}


		
		int len = 0;
		str[n] = -1;
		for (int i = 0; i < n; i++) {
			if (len > 0)
				len--;
			if (rank[i] == n - 1)
				continue;
			while (str[i+len] == str[SA[rank[i]+1]+len]) {
				len++;
			}
			height[rank[i]] = len;
		}
		
		log = new int[n + 1];
		for (int i = 0; (1 << i) < n+1; i++)
			for (int j = 0; j < (1 << i); j++) {
				if ((1 << i) + j >= n+1)
					break;
				log[(1 << i) + j] = i;
			}
		
		
		int J = log[n];
		rmq = new int[n+1][J+1];
		for (int i = 0; i < n; i++)
			rmq[i][0] = height[i]; 
		for (int j = 1; j <= J; j++) {
			for (int i = 0; i < n; i++) {
				rmq[i][j] = rmq[i][j-1];
				if (i + (1 << (j-1)) < n)
					rmq[i][j] = Math.min(rmq[i][j], rmq[i+(1<<(j-1))][j-1]);
			}
		}
	}
		
	int lcpInSA(int a, int b) {
		if (a == b)
			return n - SA[a];
		if (a > b) {
			int tmp = b;
			b = a;
			a = tmp;
		}
		b--;
		int J = log[b - a + 1];
		return Math.min(rmq[a][J], rmq[b-(1<<J)+1][J]);
	}
	
	int lcpInStr(int a, int b) {
		return lcpInSA(rank[a], rank[b]);
	}

}
class Reader {
    static BufferedReader reader;
    static StringTokenizer tokenizer;
    static void init(InputStream input) {
        reader = new BufferedReader(new InputStreamReader(input));
        tokenizer = new StringTokenizer("");
    }
    static String next() throws IOException {
        while (!tokenizer.hasMoreTokens()) {
            tokenizer = new StringTokenizer(reader.readLine());
        }
        return tokenizer.nextToken();
    }
    static int nextInt() throws IOException {
        return Integer.parseInt(next());
    }
    static double nextDouble() throws IOException {
        return Double.parseDouble(next());
    }
    static long nextLong() throws IOException {
        return Long.parseLong(next());
    }
    static boolean isend() throws IOException {
    	if (tokenizer.hasMoreTokens())
    		return false;
		do {
			String s = reader.readLine();
			if (s == null)
				return true;
			tokenizer = new StringTokenizer(s);
		} while (!tokenizer.hasMoreTokens());
		return false;
    }
}