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

#pragma GCC optimize("O3,unroll-loops")

using iii = tuple<int, int, int>;

#define pb push_back
#define eb emplace_back

int n, q, ans[500005], prv[500005], del_time[500005];
char s[500005];
vector<iii> qu[500005];
set<int> rem;

struct dat {
	int a{-1}, b{-1}, diff{(int)1e9};
};

dat combine(dat lhs, dat rhs) {
	dat ret;
	ret.diff = min(lhs.diff, rhs.diff);
	if (lhs.b != -1 && rhs.a != -1 && s[lhs.b] != s[rhs.a]) {
		ret.diff = min(ret.diff, rhs.a);
	}
	if (lhs.a == -1) {
		ret.a = rhs.a;
	} else {
		ret.a = lhs.a;
	}
	if (rhs.b == -1) {
		ret.b = lhs.b;
	} else {
		ret.b = rhs.b;
	}
	return ret;
}

struct node {
	node *left, *right;
	int S, E;
	dat val;
	node(int _s, int _e) : S(_s), E(_e) {
		if (S == E) {
			val.a = val.b = S;
			return;
		}
		int M = (S + E) / 2;
		left = new node(S, M);
		right = new node(M + 1, E);
		val = combine(left->val, right->val);
	}
	dat qry(int l, int r) {
		if (l > E || r < S) {
			dat dummy;
			return dummy;
		}
		if (l <= S && E <= r) {
			return val;
		}
		return combine(left->qry(l, r), right->qry(l, r));
	}
	void del(int p) {
		if (S == E) {
			val.a = val.b = -1;
			val.diff = (int)1e9;
			return;
		}
		int M = (S + E) / 2;
		if (p <= M) {
			left->del(p);
		} else {
			right->del(p);
		}
		val = combine(left->val, right->val);
	}
} *root;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> q;
	for (int i = 1; i <= n; i++) {
		cin >> s[i];
	}
	root = new node(1, n);
	for (int i = 1; i <= n; i++) {
		rem.insert(i);
	}
	for (int t = 1; !rem.empty(); t++) {
		vector<int> to_erase;
		for (int st = *rem.begin(); st <= n; st = root->qry(st, n).diff) {
			to_erase.pb(st);
		}
		for (auto i : to_erase) {
			rem.erase(i);
			root->del(i);
			del_time[i] = t;
		}
	}
	for (int i = 1, l, r, k; i <= q; i++) {
		cin >> l >> r >> k;
		qu[l].eb(r, k, i);
	}
	for (int l = n; l >= 1; l--) {
		prv[l] = 0;
		for (int i = l; i <= n; i++) {
			int new_val;
			if (del_time[i] >= prv[i] + 1) {
				new_val = prv[i] + 1;
			} else {
				new_val = prv[i];
			}
			if (prv[i + 1] == new_val) {
				break;
			}
			prv[i + 1] = new_val;
		}
		for (auto [r, k, idx] : qu[l]) {
			int lo = l, hi = r, lim = r + 1;
			while (lo <= hi) {
				int mid = (lo + hi) / 2;
				if (prv[mid] >= k) {
					lim = mid;
					hi = mid - 1;
				} else {
					lo = mid + 1;
				}
			}
			// [lim, r]
			for (int i = lim; i <= r; i++) {
				if (del_time[i] > k) {
					ans[idx]++;
				}
			}
		}
	}
	for (int i = 1; i <= q; i++) {
		cout << ans[i] << '\n';
	}
}