#include <bits/stdc++.h>
#include <math.h>
			
using namespace std;

// c++ short types
#define Int long long
#define vt vector
typedef unsigned long long ull;

const int mod = 1e9 + 123, base = 519;
struct Hash {
	static vt<int> pow1;
	static vt<ull> pow2;
	static inline int diff(int a, int b) {
		return (a-=b) < 0 ? a + mod : a;
	}
	vt<int> pref1;
	vt<ull> pref2;
	Hash() {}
	Hash(const string &s) : pref1(s.size() + 1), pref2(s.size() +1) {
		assert(base < mod);
		const int n = s.size();
		while((int)pow1.size()<=n) {
			pow1.push_back(pow1.back() * 1ll * base % mod);
			pow2.push_back(pow2.back() * base);
		}
		for(int i = 0; i < n; ++i) {
			pref1[i+1] = (pref1[i] + s[i] * 1ll * pow1[i]) % mod;
			pref2[i+1] = pref2[i] + s[i] * pow2[i];
		}
	}
	inline std::pair<int, ull> operator()(const int pos, const int len, const int mxPow = 0) const {
		int hash1 = diff(pref1[pos+len], pref1[pos]);
		ull hash2 = pref2[pos+len] - pref2[pos];
		if(mxPow != 0) {
			hash1 = 1ll * hash1 * pow1[mxPow-(pos+len-1)] % mod;
			hash2 = hash2 * pow2[mxPow - (pos+len-1)];
		}
		return {hash1, hash2};
	}
};
vt<int> Hash::pow1{1};
vt<ull> Hash::pow2{1};

const int k = 451;

void solver() {
	int n, q; cin >> n >> q;
	vt<string> s(n);
	vt<Hash> hash;
	for(auto &S: s) {
		cin >> S;
		hash.push_back({S});
	}
	vt<int> res(q, 0);
	vt<vt<pair<string, array<int, 3>>>> queries(k);
	for(int i = 0; i < q; ++i) {
		int l, r; cin >> l >> r;
		--l, --r;
		string p; cin >> p;
		if(p.size() < k) {
			queries[p.size()].push_back({p, {l, r, i}});
		} else {
			Hash h(p);
			for(int j = l; j <= r; ++j) {
				for(int start = 0; start + p.size() - 1 < (int)s[j].size(); ++start) {
					int mxPow = max(p.size(), s[j].size());
					if(h(0, p.size(), mxPow) == hash[j](start, p.size(), mxPow)) {
						++res[i];
						break;
					}
				}
			}
		}
		Hash h(p);
	}
	int mx = 0;
	for(auto &x: s) {
		mx = max(mx, (int)x.size());
	}
	for(int sz = 1; sz < k; ++sz) {
		int mxPow = max(mx, sz);
		map<pair<int, ull>, vt<int>> ids;
		for(int i = 0; i < n; ++i) {
			for(int j = 0; j + sz - 1 < s[i].size(); ++j) {
				auto hh = hash[i](j, sz, mxPow);
				if(!ids.count(hh)) {
					ids[hh] = {};
				}
				if(ids[hh].empty() || ids[hh].back() != i) {
					ids[hh].push_back(i);
				}
			}
		}
		for(auto [p, v] : queries[sz]) {
			auto [l, r, i] = v;
			Hash h(p);
			auto hh = h(0, sz, mxPow);
			if(!ids.count(hh)) {
				continue;
			}
			auto &arr = ids[hh];
			if(!arr.empty() || arr.back() < l || arr[0] > r) {
				auto left = lower_bound(arr.begin(), arr.end(), l);
				auto right = lower_bound(arr.begin(), arr.end(), r);
				if(right == arr.end() || *right > r) {
					--right;
				}
				res[i] = distance(left, right) + 1;
			}
		}
	}
	for(auto x: res) {
		cout << x << " ";
	}
}

int main()
{
	ios::sync_with_stdio(false); cin.tie(nullptr);
	int tt = 1;
	for(int t = 0; t < tt; ++t) {
    solver();
	}
	return 0;
}