//A tree without skin will surely die.
//A man without face will be alive.
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define mid ((l+r)>>1)
#define lowbit(x) (x&-x)
#define all(x) (x).begin(),(x).end()
#define rep(i,j,k) for (int i=j;i<=k;++i)
#define per(i,j,k) for (int i=j;i>=k;--i)
int const N=5e5+10;
int n,q,fa[N],Fa[N],ans[N],rig[N],rk1[N],rk2[N];string s;
struct Tree_Array{
	int c[N];
	inline void clear(){memset(c,0,sizeof(c));}
	inline void update(int x,int v){while (x<N) c[x]+=v,x+=lowbit(x);}
	inline int query(int x){int r=0;while (x) r+=c[x],x-=lowbit(x);return r;}
}T;
inline int find(int x){return (x==fa[x])?(x):(fa[x]=find(fa[x]));}
inline int Find(int x){return (x==Fa[x])?(x):(Fa[x]=Find(Fa[x]));}
vector< pair<int,int> >qry1[N],qry2[N];
inline void solve(){
	cin>>n>>q>>s,s=" "+s;
	rep(i,1,q){
		int l,r,k;cin>>l>>r>>k;
		if (k==0) ans[i]=r-l+1;
		else{
			qry1[k].push_back({i,r});
			qry2[k].push_back({i,l});
		}
	}
	memset(rk1,0x3f,sizeof(rk1));
	{
		set<int>leftpos;
		rep(i,1,n){
			int j=i;
			while (j+1<=n && s[j+1]==s[i]) ++j;
			leftpos.insert(i),i=j;
		}
		rep(i,1,n) T.update(i,1),fa[i]=Fa[i]=i;
		rep(i,1,n){
			if (!leftpos.size()) break;
			set<int>nw;
			for (auto j:leftpos) fa[j]=find(j+1),Fa[j]=Find(j-1),T.update(j,-1);
			for (auto j:leftpos) if (s[find(j)]==s[j] && s[find(j)]!=s[Find(find(j)-1)]) nw.insert(find(j));
			for (auto g:qry1[i])
				rk2[g.first]=T.query(g.second);
			leftpos=nw;
		}
	}
	T.clear();
	{
		set<int>leftpos;
		rep(i,1,n){
			int j=i;
			while (j+1<=n && s[j+1]==s[i]) ++j;
			leftpos.insert(i),rig[i]=j,i=j;
		}
		rep(i,1,n) T.update(i,1);
		rep(i,1,n){
			if (!leftpos.size()) break;
			set<int>nw;
			for (auto j:leftpos){
				auto it=leftpos.find(j);
				if (it==leftpos.end()) T.update(rig[j],-1),--rig[j];
				else{
					++it;
					if (s[*it]!=s[j]) T.update(rig[j],-1),--rig[j];
				}
				if (rig[j]>=j) nw.insert(j);
			}
			for (auto g:qry2[i])
				rk1[g.first]=T.query(g.second-1)+1;
			leftpos=nw;
		}
	}
	rep(i,1,q)
		if (ans[i]) cout<<ans[i]<<'\n';
		else cout<<max(0ll,rk2[i]-rk1[i]+1)<<'\n';
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	int t=1;
	// cin>>t;
	while (t--) solve();
	cerr<<"Time: "<<(double)clock()/CLOCKS_PER_SEC<<" s\n";
	return 0;
}