#include<bits/stdc++.h>
#define Gc() getchar() 
#define Me(x,y) memset(x,y,sizeof(x))
#define Mc(x,y) memcpy(x,y,sizeof(x))
#define d(x,y) ((m)*(x-1)+(y))
#define R(n) (rnd()%(n)+1)
#define Pc(x) putchar(x)
#define LB lower_bound
#define UB upper_bound
#define fi first
#define se second
using namespace std;using ll=long long;using db=double;using lb=long db;using ui=unsigned;using ull=unsigned long long;using pii=pair<int,int>;using LL=__int128;
const int N=5e5+5,M=2e3+5,K=31650,mod=998244353,Mod=mod-1;const db eps=1e-9;const int INF=1e9+7;mt19937 rnd(time(0));
int n,m,k,x,y,z;char s[N];
int pre[N],nxt[N];
int dt[N],ds[N];
int ans[N];
int main(){
	int i,j;scanf("%d%d",&n,&m);scanf("%s",s+1);
	for(i=1;i<=n+1;i++) pre[i]=i-1,nxt[i-1]=i;
	vector<int> q1;
	for(i=2;i<=n;i++) if(s[i]^s[pre[i]]) q1.emplace_back(i);
	for(i=1;i<=n;i++){
		for(int j:q1) dt[j]=i,ds[j]=pre[j];
		vector<int> q2;q2.clear();
		reverse(q1.begin(),q1.end());
		for(int j:q1) nxt[pre[j]]=nxt[j],pre[nxt[j]]=pre[j],q2.emplace_back(nxt[j]);
		sort(q2.begin(),q2.end());q2.erase(unique(q2.begin(),q2.end()),q2.end());
		q1.clear();for(int j:q2) if(j<=n&&pre[j]&&s[j]^s[pre[j]]) q1.emplace_back(j);
	}
	for(i=1;i<=n;i++) if(!dt[i]) dt[i]=INF;
	// for(i=1;i<=16;i++) cerr<<dt[i]<<' '<<ds[i]<<'\n';
	// for(i=7;i<=43;i++) cerr<<s[i];cerr<<'\n';
	for(i=1;i<=m;i++){
		scanf("%d%d%d",&x,&y,&z);
		int p=0,q=y+1;
		for(j=x;j<=y;j++){
			if(ds[j]<x) p++;else p=max(p,dt[j]);
			if(p>z){q=j;break;}
		}
		cerr<<q<<'\n';
		for(j=q;j<=y;j++) ans[i]+=(dt[j]>z);
		printf("%d\n",ans[i]);
	}
}