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

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

#define pb push_back

int n, q, del_time[500005];
char s[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;
		int cur = 0;
		for (int j = l, prv = 0; j <= r; j++) {
			int tmp = min(del_time[j], prv + 1);
			prv = max(del_time[j], prv);
			if (tmp > k) {
				cur++;
			}
		}
		cout << cur << '\n';
	}
}