#include <bits/stdc++.h>
using namespace std;

typedef unsigned uint;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<pii> vpii;
typedef complex<double> cpx;
template <typename T> using minPq = priority_queue<T, vector<T>, greater<T>>;
#define ms(a, x) memset(a, x, sizeof(a))
#define pb push_back
#define fs first
#define sn second
#define ALL(v) begin(v), end(v)
#define SZ(v) ((int) (v).size())
#define lbv(v, x) (lower_bound(ALL(v), x) - (v).begin())
#define ubv(v, x) (upper_bound(ALL(v), x) - (v).begin())
template <typename T> inline void UNIQUE(vector<T> &v){sort(ALL(v)); v.resize(unique(ALL(v)) - v.begin());}
const int INF = 0x3f3f3f3f;
const ll LLINF = 0x3f3f3f3f3f3f3f3f;
const double PI = acos(-1);
#define FR(i, n) for(int i = 0; i < (n); i++)
#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define FORR(i, a, b) for(int i = (a); i >= (b); i--)
#define dbg(x) {cerr << #x << ' ' << x << endl;}
#define dbgArr(arr, n) {cerr << #arr; FR(_i, n) cerr << ' ' << (arr)[_i]; cerr << endl;}
template <typename T, typename U>
ostream& operator<<(ostream &os, pair<T, U> p){return os << "(" << p.fs << ", " << p.sn << ")";}

struct Blk {
    bool col;
    deque<int> dq;
};

template <typename T>
void merge(deque<T> &a, deque<T> &b){
    if(SZ(a) >= SZ(b)){
        a.insert(a.end(), ALL(b));
        b.clear();
    }
    else {
        b.insert(b.begin(), ALL(a));
        a = move(b);
    }
}

const int TSZ = 1 << 19;
const int MN = 5e5 + 5;

namespace Tree {
    int tree[TSZ*2];

    void upd(int l, int r){
        for(l += TSZ, r += TSZ; l < r; l >>= 1, r >>= 1){
            if(l & 1) tree[l++]++;
            if(r & 1) tree[--r]++;
        }
    }

    int query(int i){
        int res = 0;
        for(i += TSZ; i; i >>= 1) res += tree[i];
        return res;
    }
}

int n, q;
string str;
Blk blks[MN];
int nb, pref[MN];
int ans[MN];
vector<pair<pii, int>> qrys[MN];

void proc(int t){
    FR(i, nb) pref[i+1] = pref[i] + SZ(blks[i].dq);

    for(auto [pr, ind] : qrys[t]){
        auto [l, r] = pr;
        int li = lower_bound(blks, blks+nb, l, [](const Blk &a, const int &b){
            return a.dq.back() < b;}) - blks;
        int ri = lower_bound(blks, blks+nb, r, [](const Blk &a, const int &b){
            return a.dq.back() < b;}) - blks;

        int lp = lbv(blks[li].dq, l) + Tree::query(l);
        int rp = lbv(blks[ri].dq, r);

        if(li == ri) ans[ind] = max(0, rp - lp);
        else ans[ind] = max(0, SZ(blks[li].dq) - lp) + pref[ri] - pref[li+1] + rp;
    }

    int oldNb = nb;
    nb = 0;
    FR(i, oldNb){
        int l = blks[i].dq.front();
        int r = blks[i].dq.back();
        blks[i].dq.pop_front();
        if(blks[i].dq.empty()) continue;
        Tree::upd(l+1, r+1);
        if(nb && blks[i].col == blks[nb-1].col) merge(blks[nb-1].dq, blks[i].dq);
        else blks[nb++] = move(blks[i]);
    }
}

int main(){
    cin.sync_with_stdio(0); cin.tie(0);
    cin >> n >> q >> str;
    FR(i, q){
        int l, r, t;
        cin >> l >> r >> t;
        l--;
        qrys[t].pb({{l, r}, i});
    }

    FR(i, n){
        if(i && str[i] == str[i-1]) blks[nb-1].dq.pb(i);
        else blks[nb].col = str[i]-'0', blks[nb++].dq.pb(i);
    }

    FR(t, n+1) proc(t);

    FR(i, q) cout << ans[i] << '\n';
}