#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;
typedef long long ll;
const int N = 5e5 + 5;
int n , q , ans[N]; string s;
struct Node
{
	int l; mutable int r; bool c;
	mutable deque<int>v;
	Node(int l = 0 , int r = 0 , bool c = 0):l(l) , r(r) , c(c){}
	bool operator < (const Node &rhs) const
	{
		return l < rhs.l;
	}
};
set<Node>st;
vector<pair<int , int> >qu[N] , q2[N];
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0) , cout.tie(0);
	cin >> n >> q >> s , s = " " + s;
	for(int i = 1 ; i <= q ; i++)
	{
		int l , r , k; cin >> l >> r >> k;
		q2[k].push_back({l - 1 , i});
		qu[k].push_back({r , i});
	}
	auto join = [&](deque<int>&a , const deque<int>&b , bool pos)
	{
		if(pos)for(int x : b)a.push_back(x);
		else for(auto it = b.rbegin() ; it != b.rend() ; it++)a.push_front(*it);
	};
	auto print = [&](string info = "")
	{
		if(!info.empty())cerr << "[" << info << "]:\n";
		for(auto [l , r , c , v] : st)
		{
			cerr << "[" << l << ',' << r << "] " << c << ":";
			for(int x : v)cerr << x << " ";
			cerr << "\n";
		}
	};
	auto it = st.begin();
	for(int i = 1 ; i <= n ; i++)
	{
		if(s[i] != s[i - 1])
			it = st.insert(Node(i , i , s[i] - '0')).first;
		it->r = i , it->v.push_back(i);
	}
	for(int i = 0 ; i <= n && !st.empty() ; i++)
	{
		int j = 0 , m = qu[i].size() , s = 0; 
		sort(qu[i].begin() , qu[i].end());
		for(auto [l , r , c , v] : st)
		{
			for(; j < m && qu[i][j].fi <= r ; j++)
			{
				auto [p , id] = qu[i][j];
				// cerr << "\t" << id << " " << s << "+" << upper_bound(v.begin() , v.end() , p) - v.begin() << "\n";
				ans[id] += (s + upper_bound(v.begin() , v.end() , p) - v.begin());
			}
			s += v.size();
		}
		for(; j < m ; j++)
		{
			auto [p , id] = qu[i][j];
			ans[id] += s;
		}
		// print("query " + to_string(i));
		for(auto &nd : st)nd.v.pop_front();
		for(auto it = next(st.begin()) ; ; it++)
		{
			while(it != st.begin() && prev(it)->v.empty())st.erase(prev(it));
			if(it == st.end())break ;
		}
		// print("pop " + to_string(i));
		for(auto it = st.begin() ; it != st.end() ; it++)
		{
			auto nx = next(it);
			for(; nx != st.end() && nx->c == it->c ; nx = next(it))
			{
				it->r = nx->r;
				if(it->v.size() < nx->v.size())join(it->v , nx->v , 1);
				else join(nx->v , it->v , 0) , swap(it->v , nx->v);
				st.erase(nx);
			}
		}
		// print("merge " + to_string(i));
		// cerr << "\n";
	}
	st.clear() , it = st.begin();
	for(int i = 1 ; i <= n ; i++)
	{
		if(s[i] != s[i - 1])
			it = st.insert(Node(i , i , s[i] - '0')).first;
		it->r = i , it->v.push_back(i);
	}
	for(int i = 0 ; i <= n && !st.empty() ; i++)
	{
		int j = 0 , m = q2[i].size() , s = 0; 
		sort(q2[i].begin() , q2[i].end());
		for(auto [l , r , c , v] : st)
		{
			for(; j < m && q2[i][j].fi <= r ; j++)
			{
				auto [p , id] = q2[i][j];
				// cerr << "\t" << id << " " << s << "+" << upper_bound(v.begin() , v.end() , p) - v.begin() << "\n";
				ans[id] -= (s + upper_bound(v.begin() , v.end() , p) - v.begin());
			}
			s += v.size();
		}
		for(; j < m ; j++)
		{
			auto [p , id] = q2[i][j];
			ans[id] -= s;
		}
		// print("query " + to_string(i));
		for(auto &nd : st)nd.v.pop_back();
		for(auto it = next(st.begin()) ; ; it++)
		{
			while(it != st.begin() && prev(it)->v.empty())st.erase(prev(it));
			if(it == st.end())break ;
		}
		// print("pop " + to_string(i));
		for(auto it = st.begin() ; it != st.end() ; it++)
		{
			auto nx = next(it);
			for(; nx != st.end() && nx->c == it->c ; nx = next(it))
			{
				it->r = nx->r;
				if(it->v.size() < nx->v.size())join(it->v , nx->v , 1);
				else join(nx->v , it->v , 0) , swap(it->v , nx->v);
				st.erase(nx);
			}
		}
		// print("merge " + to_string(i));
		// cerr << "\n";
	}
	for(int i = 1 ; i <= q ; i++)
		cout << ans[i] << "\n";
	return 0;
}