#include <stdio.h>
#include <string.h>

#include <assert.h>

#include <vector>
#include <algorithm>

#define LOG(FMT...) fprintf(stderr, FMT)

#define eb emplace_back

using namespace std;

constexpr int N = 500005;

int n, m;
char str[N];

void prework(int *pr) {
	static int stk[N], tt;
	tt = 0;
	for (int i = 1; i <= n; ++i) {
		int last = 1;
		while (tt && str[stk[tt]] == str[i]) {
			last = pr[stk[tt]] + 1;
			--tt;
		}
		pr[i] = last;
		stk[++tt] = i;
	}
}

int pr[N], sf[N];

struct Req {
	int y, k;
	Req() {}
	Req(int _y, int _k) : y(_y), k(_k) {}
};
vector<Req> ls[N], rs[N];
int res[N];

struct BIT {
	int fw[N];
	void clear() {
		memset(fw, 0, sizeof fw);
	}
	void A(int x) {
		for (; x; x &= x - 1) {
			++fw[x];
		}
	}
	int Q(int x) {
		int ret = 0;
		for (; x <= n; x += x & -x) {
			ret += fw[x];
		}
		return ret;
	}
} fw;

int main() {
	scanf("%d%d%s", &n, &m, str + 1);
	prework(pr);
	reverse(str + 1, str + n + 1);
	prework(sf);
	reverse(sf + 1, sf + n + 1);
	reverse(str + 1, str + n + 1);
	/* for (int i = 1; i <= n; ++i) {
		printf("%d ", pr[i]);
	}
	puts("");
	for (int i = 1; i <= n; ++i) {
		printf("%d ", sf[i]);
	}
	puts(""); */
	for (int i = 0, k, l, r; i < m; ++i) {
		scanf("%d%d%d", &l, &r, &k);
		ls[r].eb(k, i);
		rs[l].eb(k, i);
	}
	for (int i = 1; i <= n; ++i) {
		fw.A(pr[i]);
		for (auto [y, k] : ls[i]) {
			res[k] += fw.Q(y + 1);
		}
	}
	/* for (int i = 1; i <= n; ++i) {
		LOG("%d ", fw.Q(i));
	}
	LOG("\n"); */
	fw.clear();
	for (int i = n; i; --i) {
		fw.A(sf[i]);
		for (auto [y, k] : rs[i]) {
			res[k] += fw.Q(y + 1);
		}
	}
	/* for (int i = 1; i <= n; ++i) {
		LOG("%d ", fw.Q(i));
	}
	LOG("\n"); */
	for (int i = 1; i <= n; ++i) {
		for (auto [y, k] : rs[i]) {
			res[k] -= fw.Q(y + 1);
		}
	}
	for (int i = 0; i < m; ++i) {
		printf("%d\n", max(res[i], 0));
	}
	return 0;
}