#include<bits/stdc++.h>
typedef long long ll;
const int P=998244353;
const int N=1e6+10;
struct pack{
    ll ct[2],sum[2];
    void reverse(){
        std::swap(ct[0],ct[1]);
        std::swap(sum[0],sum[1]);
    }
};
pack operator+(pack a,pack b){
    pack ret;
    ret.ct[0]=a.ct[0]+b.ct[0];
    ret.ct[1]=a.ct[1]+b.ct[1];
    ret.sum[0]=a.sum[0]+b.sum[0];
    ret.sum[1]=a.sum[1]+b.sum[1];
    return ret;
}
int readch(){
    while(true)switch(getchar()){
        case '0':return 0;
        case '1':return 1;
    }
}
int n,m;
namespace ST{
    int son[N][2],node_count;
    bool lazy[N];
    pack data[N];
    void solve_lazy(int t){
        if(!lazy[t])return;
        data[t].reverse();
        lazy[t]=0;
        if(son[t][0])lazy[son[t][0]]^=1;
        if(son[t][1])lazy[son[t][1]]^=1;
    }
    void refresh(int t){
        solve_lazy(son[t][0]);
        solve_lazy(son[t][1]);
        data[t]=data[son[t][0]]+data[son[t][1]];
    }
    void reverse(int l,int r,int t=1,int L=1,int R=n){
        if(l==L&&r==R){
            lazy[t]^=1;
            return;
        }
        solve_lazy(t);
        int mm=L+(R-L)/2;
        if(r<=mm)reverse(l,r,son[t][0],L,mm);
        else if(l>mm)reverse(l,r,son[t][1],mm+1,R);
        else{
            reverse(l,mm,son[t][0],L,mm);
            reverse(mm+1,r,son[t][1],mm+1,R);
        }
        refresh(t);
    }
    pack query(int l,int r,int t=1,int L=1,int R=n){
        solve_lazy(t);
        if(l==L&&r==R)return data[t];
        int mm=L+(R-L)/2;
        if(r<=mm)return query(l,r,son[t][0],L,mm);
        if(l>mm)return query(l,r,son[t][1],mm+1,R);
        return query(l,mm,son[t][0],L,mm)+query(mm+1,r,son[t][1],mm+1,R);
    }
    int build(int L,int R){
        int t=++node_count;
        lazy[t]=0;
        if(L==R){
            son[t][0]=son[t][1]=0;
            int ch=readch();
            data[t].ct[!ch]=0;
            data[t].ct[ch]=1;
            data[t].sum[!ch]=0;
            data[t].sum[ch]=L;
        }else{
            int mm=L+(R-L)/2;
            son[t][0]=build(L,mm);
            son[t][1]=build(mm+1,R);
            refresh(t);
        }
        return t;
    }
    int build(){
        node_count=0;
        return build(1,n);
    }
}

int main(){
    while(scanf("%d%d",&n,&m)==2){
        ST::build();
        for(int i=0;i<m;i++){
            int l,r;
            scanf("%d%d",&l,&r);
            ST::reverse(l,r);
            int k=ST::query(1,n).ct[1];
            ll A=k-1?ST::query(1,k-1).sum[0]:0;
            ll B=ST::query(k,n).sum[1];
            printf("%lld\n",(2*B-2*A-k)%P);
        }
    }
}