#include<bits/stdc++.h>
using namespace std;
int n,q;
char s[500005];
int ql[500005],qr[500005],ans[500005];
vector<int> qu[500005];
struct bit{
	#define lowbit(x) (x&-x)
	int tree[500005];
	void add(int x,int k)
	{
		for(int i=x;i<=n;i+=lowbit(i))
		{
			tree[i]+=k;
		}
	}
	int query(int x)
	{
		int res=0;
		for(int i=x;i;i^=lowbit(i))
		{
			res+=tree[i];
		}
		return res;
	}
}T1,T2;
struct seg{
	int l,r,v;
	bool operator <(const seg &b) const
	{
		return l<b.l;
	}
};
set<int> s1,s3;
set<seg> s2,s4;
int lst1[500005],nxt1[500005],lst2[500005],nxt2[500005];
int main()
{
	cin>>n>>q>>s+1;
	for(int i=1;i<=q;i++)
	{
		int k;
		cin>>ql[i]>>qr[i]>>k;
		if(k==0) ans[i]=qr[i]-ql[i]+1;
		qu[k].emplace_back(i);
	}
	s1.insert(0);
	s3.insert(n+1);
	for(int i=1;i<=n;i++)
	{
		s1.insert(i),s3.insert(i);
		s2.insert({i,i,s[i]});
		s4.insert({i,i,s[i]});
		lst1[i]=i-1;
		lst2[i]=i-1;
		nxt1[i]=i+1;
		nxt2[i]=i+1;
		T1.add(i,1);
		T2.add(i,1);
	}
	for(int i=1;i<=n;i++)
	{
		set<seg> st;
		seg lst={n+1,0,-1};
		for(auto [l,r,v]:s2)
		{
			// cerr<<l<<" "<<r<<" "<<v<<"\n";
			if(v!=lst.v)
			{
				if(lst.l<=lst.r) st.insert(lst);
				s1.erase(l);
				lst1[nxt1[l]]=lst1[l];
				nxt1[lst1[l]]=nxt1[l];
				T1.add(l,-1);
				lst={nxt1[l],r,v};
			}
			else
			{
				lst.l=min(lst.l,l);
				lst.r=max(lst.r,r);
			}
		}
		if(lst.l<=lst.r) st.insert(lst);
		s2=st;
		st.clear();
		lst={n+1,0,-1};
		// cerr<<"\n";
		for(auto i=s4.rbegin();i!=s4.rend();i++)
		{
			auto [l,r,v]=*i;
			// cerr<<l<<" "<<r<<" "<<v<<"\n";
			if(v!=lst.v)
			{
				if(lst.l<=lst.r) st.insert(lst);
				s3.erase(r);
				lst2[nxt2[r]]=lst2[r];
				nxt2[lst2[r]]=nxt2[r];	
				T2.add(r,-1);		
				lst={l,lst2[r],v};
			}
			else
			{
				lst.l=min(lst.l,l);
				lst.r=max(lst.r,r);
			}
		}
		if(lst.l<=lst.r) st.insert(lst);
		s4=st;
		// cerr<<"\n";
		for(auto j:qu[i])
		{
			int l=*s3.lower_bound(ql[j]),r=*prev(s1.upper_bound(qr[j]));
			// cerr<<"!!!"<<ql[j]<<" "<<qr[j]<<" "<<l<<" "<<r<<"\n";	
			if(l>r) ans[j]=0;
			else ans[j]=max(0,T1.query(r)-T2.query(l)+1);
		}
	}
	for(int i=1;i<=q;i++)
	{
		cout<<ans[i]<<"\n";
	}
}