#include <bits/stdc++.h>
using namespace std;
#define N 500005
#define pb push_back
int n,m,st[N],tmp[N],ans[N],rt[N];char a[N];
struct List {int pr,sf;}ls[N];
struct Query {int l,r,id;};vector<Query> vc[N];
struct BitArray
{
	int bt[N];void build() {for(int i=1;i<=n;++i) bt[i]=i&-i;}
	void upd(int x,int vl) {for(;x<=n;x+=x&-x) bt[x]+=vl;}
	int qSm(int x) {int res=0;for(;x;x-=x&-x) res+=bt[x];return res;}
	int qry(int x)
	{
		int res=0;
		for(int i=18;i>=0;--i) if(res+(1<<i)<=n && bt[res+(1<<i)]<x)
			res+=1<<i;return res+1;
	}
}BIT1,BIT2;
int findRt(int u) {return u==rt[u]?u:rt[u]=findRt(rt[u]);}
void merge(int u,int v) {u=findRt(u);v=findRt(v);if(u!=v) rt[u]=v,BIT2.upd(u,-1);}
int main()
{
	scanf("%d %d %s",&n,&m,a+1);iota(rt+1,rt+n+1,1);
	for(int i=1,l,r,x;i<=m;++i)
	{scanf("%d %d %d",&l,&r,&x);if(x) vc[x].pb((Query) {l,r,i});else ans[i]=r-l+1;}
	for(int i=0;i<=n;++i) ls[i].sf=i+1,ls[i+1].pr=i;
	for(int i=1;i<=n;++i) if(a[i]!=a[i-1]) st[++st[0]]=i;BIT1.build();BIT2.build();
	for(int i=1,t,t1;i<=n;++i)
	{
		if(!st[0]) break;t=tmp[0]=0;
		for(int j=1;j<=st[0]+1;++j)
			if(j==1 || j>st[0] || ls[st[j]].pr!=st[j-1])
			{
				if(j>1 && ls[st[j-1]].sf<=n && a[t]!=a[ls[st[j-1]].sf])
					tmp[++tmp[0]]=ls[st[j-1]].sf;t=ls[st[j]].pr;
				if(j>1) t1=BIT1.qSm(st[j]),merge(BIT2.qry(t1),BIT2.qry(t1-1));
			}else t1=BIT1.qSm(st[j]),merge(BIT2.qry(t1),BIT2.qry(t1-1));
		for(int j=1;j<=st[0];++j)
		{
			ls[ls[st[j]].pr].sf=ls[st[j]].sf;
			ls[ls[st[j]].sf].pr=ls[st[j]].pr;BIT1.upd(st[j],-1);
		}copy(tmp,tmp+tmp[0]+1,st);
		for(auto [l,r,id]:vc[i]) ans[id]=max(BIT1.qSm(r)-BIT2.qSm(findRt(l))+1,0);
	}for(int i=1;i<=m;++i) printf("%d\n",ans[i]);return 0;
}