#include<bits/stdc++.h>
#define pd push_back
#define all(A) A.begin(),A.end()
#define lb lower_bound
#define ve std::vector
#include <ext/pb_ds/priority_queue.hpp>
typedef long long ll;
typedef __int128 Int;
typedef unsigned long long ul;
typedef long double LD;
bool FileIfstream(std::string name){
	std::ifstream f(name.c_str());
	return f.good();
}
namespace Math{
	ll QP(ll x,ll y,ll mod){ll ans=1;for(;y;y>>=1,x=x*x%mod)if(y&1)ans=ans*x%mod;return ans;}
	ll inv(ll x,ll mod){return QP(x,mod-2,mod);}
}
const int N=5e5+10;
const int mod=998244353;
struct FwT{
	int tr[N];
	void add(int x,int y){for(;x<=N-10;x+=(x&-x))tr[x]+=y;}
	int query(int x){if(x<=0)return 0;int ans=0;for(;x;x-=(x&-x))ans+=tr[x];return ans;}
}Tr;
const int inf=1e9;
void solve(){
	//don't forget to open long long
	int n,m;std::cin>>n>>m;
	std::string s;std::cin>>s;s=" "+s;
	ve<ve<std::array<int,2>>>C(n+1);
	ve<std::array<int,5>>Q(n+1);
	for(int i=1;i<=m;i++)
		std::cin>>Q[i][0]>>Q[i][1]>>Q[i][2],Q[i][0]--;
	for(int i=1;i<=m;i++)
		if(!Q[i][2])Q[i][4]=Q[i][1]-Q[i][0],Q[i][3]=0;
		else C[Q[i][2]].pd({Q[i][1],i});
	for(int i=1;i<=n;i++)Tr.add(i,1);
	std::set<int>st1,st2;
	for(int i=1;i<=n;i++)
		if(s[i]=='0')st1.insert(i);
		else st2.insert(i);
	st1.insert(inf);st2.insert(inf);
	for(int i=1;i<=n;i++){
		if(st1.size()==1&&st2.size()==1){
			for(auto &p:C[i])
				Q[p[1]][4]=0;
		}else{
			int pos=0;
			bool cur=(*st1.begin())>(*st2.begin());
			while((!cur&&st1.size()>1)||(cur&&st2.size()>1)){
				if(!cur){
					pos=*st1.upper_bound(pos);
					if(pos==inf)break;
					Tr.add(pos,-1);
					st1.erase(pos);
					cur^=1;
				}else{
					pos=*st2.upper_bound(pos);
					if(pos==inf)break;
					Tr.add(pos,-1);
					st2.erase(pos);
					cur^=1;
				}
			}
			for(auto &p:C[i])
				Q[p[1]][4]=Tr.query(p[0]); 
		}
	}
	
	for(int i=1;i<=n;i++)C[i].clear();
	st1.clear();st2.clear();
	
	for(int i=1;i<=n;i++)Tr.add(i,1);
	for(int i=1;i<=m;i++)
		if(Q[i][2])C[Q[i][2]].pd({Q[i][0],i});
	for(int i=1;i<=n;i++)
		if(s[i]=='0')st1.insert(n-i+1);
		else st2.insert(n-i+1);
	st1.insert(inf);st2.insert(inf);
	for(int i=1;i<=n;i++){
		if(st1.size()==1&&st2.size()==1){
			for(auto &p:C[i])
				Q[p[1]][3]=0;
		}else{
			int pos=0;
			bool cur=(*st1.begin())>(*st2.begin());
			while((!cur&&st1.size()>1)||(cur&&st2.size()>1)){
				if(!cur){
					pos=*st1.upper_bound(pos);
					if(pos==inf)break;
					Tr.add(n-pos+1,-1);
					st1.erase(pos);
					cur^=1;
				}else{
					pos=*st2.upper_bound(pos);
					if(pos==inf)break;
					Tr.add(n-pos+1,-1);
					st2.erase(pos);
					cur^=1;
				}
			}
			for(auto &p:C[i])
				Q[p[1]][3]=Tr.query(p[0]); 
		}
	}
	
	for(int i=1;i<=m;i++)
		std::cout<<std::max(0,Q[i][4]-Q[i][3])<<'\n';
}
int main(){
#ifndef ONLINE_JUDGE
	if(!FileIfstream("IO.in")){
		freopen("IO.in","w",stdout);
		return 0;
	}
	freopen("IO.in","r",stdin);
	freopen("IO.out","w",stdout);
#endif
	std::ios::sync_with_stdio(false);
	std::cin.tie(0);
	std::cout.tie(0);
	int T=1;
	//std::cin>>T;
	while(T--)solve();

	return 0;
}