#include<bits/stdc++.h>
using namespace std;
using ll=long long;
template<typename T>
ostream& operator << (ostream &out,const vector<T>&x){
	if(x.empty())return out<<"[]";
	out<<'['<<x[0];
	for(int len=x.size(),i=1;i<len;i++)out<<','<<x[i];
	return out<<']';
}
template<typename T>
ostream& operator << (ostream &out,const deque<T>&x){
	if(x.empty())return out<<"[]";
	out<<'['<<x[0];
	for(int len=x.size(),i=1;i<len;i++)out<<','<<x[i];
	return out<<']';
}
template<typename T>
vector<T> ary(const T *a,int l,int r){
	return vector<T>{a+l,a+1+r};
}
template<typename T>
void debug(T x){
	cerr<<x<<'\n';
}
template<typename T,typename ...S>
void debug(T x,S ...y){
	cerr<<x<<' ',debug(y...);
}
const int N=5e5+10,INF=1e9;
int n,m,nex[N],pre[N];
char a[N];
mt19937 rnd(0);
struct tree{
	int rnd,ls,rs,siz,mn,sum;
	deque<int>A;
}t[N];
int root;
void pushup(int rt){
	t[rt].siz=t[t[rt].ls].siz+t[t[rt].rs].siz+1;
	t[rt].mn=min({t[t[rt].ls].mn,t[t[rt].rs].mn,(int)t[rt].A.size()});
	t[rt].sum=t[t[rt].ls].sum+t[t[rt].rs].sum+(int)t[rt].A.size();
}
void split_r(int rt,int R,int &x,int &y){
	if(!rt){
		x=y=0;return;
	}
	if(t[rt].A.back()<=R)x=rt,split_r(t[rt].rs,R,t[rt].rs,y);
	else y=rt,split_r(t[rt].ls,R,x,t[rt].ls);
	pushup(rt);
}
// void split_l(int rt,int L,int &x,int &y){
// 	if(!rt){
// 		x=y=0;return;
// 	}
// 	if(t[rt].A.front()<=L)x=rt,split_l(t[rt].rs,L,t[rt].rs,y);
// 	else y=rt,split_l(t[rt].ls,L,x,t[rt].ls);
// 	pushup(rt);
// }
int merge(int x,int y){
	if(!x||!y)return x|y;
	if(t[x].rnd<t[y].rnd){
		t[x].rs=merge(t[x].rs,y);
		return pushup(x),x;
	}else{
		t[y].ls=merge(x,t[y].ls);
		return pushup(y),y;
	}
}
int cnt,cur[N];
void rebuild(int rt){
	if(!rt)return;
	rebuild(t[rt].ls);
	cur[++cnt]=rt;
	rebuild(t[rt].rs);
	t[rt].ls=t[rt].rs=0;
}
struct ques{
	int l,r,k,id;
}o[N];
int ans[N];
void init(){
	t[0].mn=INF;
	int k=0;
	root=0;
	for(int l=1,r;l<=n;l=r){
		for(r=l+1;r<=n&&a[l]==a[r];r++);
		for(int i=l;i+1<r;i++)nex[i]=i+1,pre[i+1]=i;
		pre[l]=nex[r-1]=0;
		t[++k]={(int)rnd(),0,0,1,r-l,r-l,{}};
		// debug(t[k].A);
		for(int i=l;i<r;i++)t[k].A.push_back(i);
		root=merge(root,k);
	}
}
void print(int rt=root){
	if(!rt)return;
	print(t[rt].ls);
	vector<int>A;
	cerr<<t[rt].A<<' ';
	print(t[rt].rs);
}
void solve1(){
	init();
	// debug("OK1");
	// debug(ary(nex,1,n));
	// debug(ary(pre,1,n));
	for(int now=0,x=1;root;){
		// print(),cerr<<endl;
		int mn=t[root].mn;
		// debug(now,mn);
		for(;x<=m&&o[x].k<now+mn;x++){
			int r1,r2,r3;
			split_r(root,o[x].r-1,r1,r2);
			for(r3=r2;t[r3].ls;r3=t[r3].ls);
			// debug("ques",t[r1].sum,t[r1].siz,o[x].k,now);
			int ans=t[r1].sum-t[r1].siz*(o[x].k-now);
			// debug("ans",ans,o[x].r);
			if(r3){
				// debug("A",t[r3].A);
				int cnt=upper_bound(t[r3].A.begin(),t[r3].A.end(),o[x].r)-t[r3].A.begin();
				ans+=max(cnt-(o[x].k-now),0);
			}
			// debug("ans",ans);
			::ans[o[x].id]+=ans;
			root=merge(r1,r2);
		}
		cnt=0,rebuild(root),root=0;
		// debug("cur",cnt,ary(cur,1,cnt));
		int tot=0;
		for(int i=1;i<=cnt;i++){
			int rt=cur[i];
			if(t[rt].A.size()==mn)continue;
			for(int j=1;j<=mn;j++)t[rt].A.pop_front();
			if(!tot||a[t[cur[tot]].A.back()]!=a[t[rt].A.front()]){
				cur[++tot]=rt;
			}else{
				int las=cur[tot];
				if(t[las].A.size()<t[rt].A.size()){
					for(int i=t[las].A.size()-1;~i;i--){
						t[rt].A.push_front(t[las].A[i]);
					}
					cur[tot]=rt;
				}else{
					for(int x:t[rt].A){
						t[las].A.push_back(x);
					}
				}
			}
		}
		for(int i=1;i<=tot;i++){
			int rt=cur[i];
			pushup(rt);
			root=merge(root,rt);
		}
		// if(now==1)return;
		now+=mn;
		// print(),cerr<<endl;
		// return;
	}
	// debug("ans1",ans[1]);
}
void solve2(){
	init();
	// debug("OK1");
	// debug(ary(nex,1,n));
	// debug(ary(pre,1,n));
	for(int now=0,x=1;root;){
		// print(),cerr<<endl;
		int mn=t[root].mn;
		// debug(now,mn);
		for(;x<=m&&o[x].k<now+mn;x++)if(o[x].l>1){
			int r1,r2,r3;
			split_r(root,o[x].l-2,r1,r2);
			for(r3=r2;t[r3].ls;r3=t[r3].ls);
			// debug("ques",t[r1].sum,t[r1].siz,o[x].k,now);
			int ans=t[r1].sum-t[r1].siz*(o[x].k-now);
			// debug("ans",ans,o[x].r);
			if(r3){
				// debug("A",t[r3].A);
				int cnt=upper_bound(t[r3].A.begin(),t[r3].A.end(),o[x].l-1)-t[r3].A.begin();
				ans+=max(cnt-(o[x].k-now),0);
			}
			// debug("ans",ans);
			::ans[o[x].id]-=ans;
			root=merge(r1,r2);
		}
		cnt=0,rebuild(root),root=0;
		// debug("cur",cnt,ary(cur,1,cnt));
		int tot=0;
		for(int i=1;i<=cnt;i++){
			int rt=cur[i];
			if(t[rt].A.size()==mn)continue;
			for(int j=1;j<=mn;j++)t[rt].A.pop_back();
			if(!tot||a[t[cur[tot]].A.back()]!=a[t[rt].A.front()]){
				cur[++tot]=rt;
			}else{
				int las=cur[tot];
				if(t[las].A.size()<t[rt].A.size()){
					for(int i=t[las].A.size()-1;~i;i--){
						t[rt].A.push_front(t[las].A[i]);
					}
					cur[tot]=rt;
				}else{
					for(int x:t[rt].A){
						t[las].A.push_back(x);
					}
				}
			}
		}
		for(int i=1;i<=tot;i++){
			int rt=cur[i];
			pushup(rt);
			root=merge(root,rt);
		}
		// if(now==1)return;
		now+=mn;
		// print(),cerr<<endl;
		// return;
	}
}
int main(){
	scanf("%d%d%s",&n,&m,a+1);
	for(int i=1;i<=m;i++){
		scanf("%d%d%d",&o[i].l,&o[i].r,&o[i].k);
		o[i].id=i;
	}
	sort(o+1,o+1+m,[](ques x,ques y){return x.k<y.k;});
	solve1();
	solve2();
	for(int i=1;i<=m;i++)printf("%d\n",ans[i]);
	return 0;
}