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

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

#define pb push_back
#define eb emplace_back
#define mp make_pair

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

int ls(int x) {
	return x & -x;
}

void ft_upd(int p) {
	for (; p <= n; p += ls(p)) {
		ft[p]++;
	}
}

int ft_qry(int p) {
	int r = 0;
	for (; p; p -= ls(p)) {
		r += ft[p];
	}
	return r;
}

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;

struct node2 {
	node2 *left, *right;
	int S, E, actives, pv;
	ii val;
	node2(int _s, int _e) : S(_s), E(_e), actives(0), pv(0), val((int)1e9, -1) {
		if (S == E) {
			return;
		}
		int M = (S + E) / 2;
		left = new node2(S, M);
		right = new node2(M + 1, E);
	}
	void prop() {
		left->val.first += pv;
		left->pv += pv;
		right->val.first += pv;
		right->pv += pv;
		pv = 0;
	}
	void activate(int p, int v) {
		if (S == E) {
			val = mp(v, p);
			actives++;
			return;
		}
		prop();
		int M = (S + E) / 2;
		if (p <= M) {
			left->activate(p, v);
		} else {
			right->activate(p, v);
		}
		val = min(left->val, right->val);
		actives = left->actives + right->actives;
	}
	void del(int p) {
		if (S == E) {
			val = mp((int)1e9, -1);
			actives--;
			return;
		}
		prop();
		int M = (S + E) / 2;
		if (p <= M) {
			left->del(p);
		} else {
			right->del(p);
		}
		val = min(left->val, right->val);
		actives = left->actives + right->actives;
	}
	void upd(int l, int r, int v) {
		if (l > E || r < S) {
			return;
		}
		if (l <= S && E <= r) {
			val.first += v;
			pv += v;
			return;
		}
		prop();
		left->upd(l, r, v);
		right->upd(l, r, v);
		val = min(left->val, right->val);
	}
	int kth(int k) {
		if (S == E) {
			return S;
		}
		if (left->actives >= k) {
			return left->kth(k);
		} else {
			return right->kth(left->actives);
		}
	}
} *root2;

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);
	}
	root2 = new node2(1, n);
	for (int l = n; l >= 1; l--) {
		root2->activate(l, del_time[l] + root2->actives);
		if (root2->val.first == root2->actives - 1) {
			// remove root2->val.second
			int x = root2->val.second;
			root2->del(x);
			root2->upd(1, x, -1);
		}
		for (auto [r, k, idx] : qu[l]) {
			int lim;
			if (k == 0) {
				lim = l;
			} else if (k <= root2->actives) {
				lim = root2->kth(k) + 1;
			} else {
				lim = r + 1;
			}
			// [lim, r]
			if (lim <= r) {
				qu2[lim].eb(1, k, idx);
				if (r + 1 <= n) {
					qu2[r + 1].eb(-1, k, idx);
				}
			}
		}
	}
	for (int l = n; l >= 1; l--) {
		ft_upd(del_time[l]);
		for (auto [coeff, k, idx] : qu2[l]) {
			ans[idx] += coeff * (n - l + 1 - ft_qry(k));
		}
	}
	for (int i = 1; i <= q; i++) {
		cout << ans[i] << '\n';
	}
}