#include "bits/stdc++.h"
#ifdef DEBUG
#include "PrettyDebug.hpp"
#else
#define debug(...) [](){}()
#define debuga(...) [](){}()
#endif
#define For(i,a,b) for(int i=a;i<=b;i++)
#define Rev(i,a,b) for(int i=a;i>=b;i--)
#define Fin(file) freopen(file,"r",stdin)
#define Fout(file) freopen(file,"w",stdout)
using namespace std; typedef long long ll;
namespace FastIO{
    const int BUF_SIZ=1<<16;
    char in_buf[BUF_SIZ],*got_pos=in_buf,*read_pos=in_buf,out_buf[BUF_SIZ],*write_pos=out_buf;
    inline char get_next_char(){if(read_pos==got_pos){got_pos=read_pos=in_buf;got_pos+=fread(got_pos,sizeof(char),BUF_SIZ,stdin);}return*(read_pos++);}
    inline void flush_output(){fwrite(out_buf,sizeof(char),write_pos-out_buf,stdout);write_pos=out_buf;}
    inline void put_char(char ch){*(write_pos++)=ch;if(write_pos==out_buf+BUF_SIZ)flush_output();}
#ifndef FASTIO_READ_NEGATIVE
    template<typename T> inline void read(T& res){char ch;while(!isdigit(ch=get_next_char()));res=ch^'0';while(isdigit(ch=get_next_char()))res=(res<<3)+(res<<1)+(ch^'0');}
#else
    template<typename T> inline void read(T& res){char ch;bool flg=0;while(!isdigit(ch=get_next_char()))flg|=ch=='-';res=ch^'0';while(isdigit(ch=get_next_char()))res=(res<<3)+(res<<1)+(ch^'0');if(flg)res=-res;}
#endif
    template<typename T> inline void write(T x){if(!x){put_char('0');return;}static int lis[25],*lp=lis;while(x){*(++lp)=x%10;x/=10;}while(lp!=lis)put_char((*(lp--))+'0');}
    template<typename T> inline void writeln(const T& x){write(x);put_char('\n');}
    template<typename T> inline void writesp(const T& x){write(x);put_char(' ');}
    class _IO_Flusher{public:~_IO_Flusher(){flush_output();}}__Flusher;
    class IStream{public:
        template<typename T> inline IStream& operator>>(T& x){read(x);return *this;}
        inline IStream& operator>>(char* str){char ch;while(isspace(ch=get_next_char()));(*(str++))=ch;while(!isspace(ch=get_next_char())){if(ch==EOF)break;(*(str++))=ch;}*str=0;return *this;}
    }Cin;
    class OStream{public:
        template<typename T> inline enable_if_t<is_integral<T>::value,OStream&> operator<< (const T& x){write(x);return *this;}
        inline OStream& operator<< (const char& ch){put_char(ch);return *this;}
        inline OStream& operator<< (const char* str){for(const char* p=str;*p;put_char(*(p++)));return *this;}
    }Cout;
}
using namespace FastIO;
#define cin Cin
#define cout Cout
constexpr int N=5e5+5; using ull = unsigned long long;
class Trie{
    int n; ull vis[4][N/64+10];
public:
    void init(int _n) { n=_n; For(o,0,3) For(i,0,n/64) vis[o][i]=0; }
    void insert(int x){
        For(i,0,3){
            int u=x>>6, s=x&63;
            vis[i][u]|=1ull<<s; x=u;
        }
    }
    void erase(int x){
        int flg=1;
        For(i,0,3){
            int u=x>>6, s=x&63;
            if(flg) vis[i][u]^=1ull<<s,flg=!vis[i][u];
            x=u;
        }
    }
    int prev(int x){
        x++;
        For(i,0,3){
            int u=x>>6,s=x&63;
            if(s&&(vis[i][u]<<(64-s))){
                u=u<<6|(__lg(vis[i][u]<<(64-s))-(64-s));
                Rev(j,i-1,0) u=u<<6|__lg(vis[j][u]);
                return u;
            }
            x=u;
        }
        return -1;
    }
};
class FTree{
    int n,c[N];
public:
    void init(int _n) { n=_n; For(i,1,n) c[i]=0; }
    void poke(int x,int y) { while(x<=n) { c[x]+=y; x+=x&(-x); } }
    int peek(int x) { int res=0; while(x) { res+=c[x]; x-=x&(-x); } return res; }
}T;
char str[N]; int n,Q,a[N],s[N],ans[N],cp[N],cv[N],val[N],ql[N],qr[N],qK[N],mn[20][N],fa[20][N]; vector<int> qry[N];
inline int Min(int l,int r) { int k=__lg(r-l+1); return min(mn[k][l],mn[k][r-(1<<k)+1]); }
void solve(){
    For(i,1,n) cp[i]=cv[i]=val[i]=0;
    For(j,0,19) For(i,0,n) fa[j][i]=0;
    static int st[N]; int tp=0;
    For(i,1,n){
        if(a[i]==1) st[++tp]=i;
        else { if(tp) cp[i]=st[tp--],fa[0][cp[i]]=st[tp]; else cp[i]=0; }
    }
    For(j,1,19) For(i,1,n) fa[j][i]=fa[j-1][fa[j-1][i]];
    For(i,1,n) if(cp[i]) cv[cp[i]]=i;
    For(i,1,n) s[i]=s[i-1]+(a[i]==0?1:-1);
    For(i,0,n) mn[0][i]=s[i];
    For(j,1,19) For(i,0,n-(1<<j)+1) mn[j][i]=min(mn[j-1][i],mn[j-1][i+(1<<(j-1))]);
    For(i,1,n) if(cp[i]) val[i]=s[i]-Min(cp[i]-1,i-1);
    static int tmp[N],at[N]; For(i,1,Q) tmp[i]=i;; For(i,1,n) at[i]=i;
    sort(tmp+1,tmp+1+Q,[&](int x,int y){return qK[x]>qK[y];}); sort(at+1,at+1+n,[&](int x,int y){return val[x]>val[y];});
    T.init(n);
    for(int i=1,j=1;i<=Q;i++){
        int u=tmp[i]; while(j<=n&&val[at[j]]>qK[u]) T.poke(at[j++],1);
        ans[u]+=T.peek(qr[u])-T.peek(ql[u]-1);
    }
    For(id,1,Q){
        int l=ql[id],r=qr[id],K=qK[id];
        int t=l; if(a[l]==1) t=fa[0][t]; else t=cp[t];
        if(t==0) continue;
        Rev(i,19,0) if(cv[fa[i][t]]&&cv[fa[i][t]]<=r&&val[cv[fa[i][t]]]<=K) t=fa[i][t];
        if(cv[t]<=r&&val[cv[t]]>K) ans[id]--;
        else { t=fa[0][t]; if(cv[t]<=r&&val[cv[t]]>K) ans[id]--; }
        Rev(i,19,0) if(cv[fa[i][t]]&&cv[fa[i][t]]<=r) ans[id]-=(1<<i),t=fa[i][t];
    }
    priority_queue<int,vector<int>,greater<int>> S0,S1; static Trie S;
    S.init(n+1); T.init(n); For(i,1,n) S1.push(i);
    Rev(l,n,1){
        if(a[l]==0) { int x=S1.top(); S1.pop(); S0.push(x); T.poke(x,1); S.insert(l); }
        else if(S0.size()) { int x=S0.top(); S0.pop(); S1.push(x); T.poke(x,-1); if(cv[l]) S.erase(cv[l]); }
        for(int id:qry[l]){
            int u=S.prev(qr[id]); if(u<l) continue;
            int t=s[u]-Min(l-1,u-1);
            if(t>qK[id]) ans[id]+=T.peek(t)-T.peek(qK[id]);
        }
    }
}
void Mian(){
    cin>>n>>str; For(i,1,n) a[i]=(str[i-1]=='1'),qry[i].clear();
    cin>>Q; For(i,1,Q) { cin>>ql[i]>>qr[i]>>qK[i]; qK[i]=min(qK[i],n); qry[ql[i]].push_back(i); ans[i]=0; }
    solve(); For(i,1,n) a[i]^=1; solve();
    For(i,1,Q) cout<<(qK[i]==0?qr[i]-ql[i]+1:ans[i])<<" \n"[i==Q];
}
signed main(){
    atexit([](){cerr<<"Time = "<<clock()<<" ms"<<endl;});
    int Ti=1; while(Ti--) Mian(),cerr<<Ti<<' '<<clock()<<'\n';
    return 0;
}

// CONTINUE, NON-STOPPING, FOR CHARLIEY
// START TYPING IF YOU DON'T KNOW WHAT TO DO
// STOP TYPING IF YOU DON'T KNOW WHAT YOU'RE DOING

// Started Coding On: April 28 Sun, 09 : 19 : 40