#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];
struct Node{
	int x,y;
	Node operator +(const Node &B)const{return (Node){x+B.x,max(y+B.x,B.y)};}
}B;

namespace Tree{
	#define ls v<<1
	#define rs v<<1|1
	Node f[M];
	void Up(int v){f[v]=f[ls]+f[rs];}
	void add(int x,int w,int l=1,int r=n,int v=1){
		if(l==r) {f[v].x+=w;return;}int m=l+r>>1;
		x<=m?add(x,w,l,m,ls):add(x,w,m+1,r,rs);Up(v);
	}
	void ins(int x,int y,int l=1,int r=n,int v=1){
		if(l==r) {f[v].y=max(f[v].y,y);return;}int m=l+r>>1;
		x<=m?ins(x,y,l,m,ls):ins(x,y,m+1,r,rs);Up(v);
	}
	int qry(int x,int y,int l=1,int r=n,int v=1){
		if((B+f[v]).y<=y) {B=B+f[v];return -1;}if(l==r) return (B+f[v]).y<=y?l+1:l;
		int m=l+r>>1,p=(x<=m?qry(x,y,l,m,ls):-1);return ~p?p:qry(x,y,m+1,r,rs);
	}
}
struct ques{int x,y,id;};
vector<ques> q[N],qs[N];
vector<int> Is[N];
namespace BIT{
	int f[N];
	void add(int x,int y){while(x<=n) f[x]+=y,x+=x&-x;}
	int qry(int x){int ans=0;while(x) ans+=f[x],x-=x&-x;return ans;}
}
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);
		q[x].emplace_back((ques){y,z,i});
		// 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);
	}
	for(i=1;i<=n;i++) Is[ds[i]].emplace_back(i);
	for(i=n;i;i--){
		Tree::add(i,1);
		for(auto j:Is[i]) Tree::add(j,-1),Tree::add(j,dt[j]);
		for(auto j:q[i]) {
			B=(Node){0,0};int q=Tree::qry(i,j.y);
			if(q<=j.x) qs[q-1].emplace_back((ques){j.y,-1,j.id}),qs[j.x].emplace_back((ques){j.y,1,j.id});
		}
	}
	for(i=1;i<=n;i++){
		BIT::add(dt[i],1);
		for(auto j:qs[i]) ans[j.id]+=(i-BIT::qry(j.x))*j.y;
	}
	for(i=1;i<=m;i++) printf("%d\n",ans[i]);
}