#include <bits/stdc++.h>
#define int long long
using namespace std;
struct dat
{
	int one,zero,tag,onenum,zeronum;
}tr[1000005<<2];
const long long mod=998244353;
int n,m,a[1000005],one[1000005],zero[1000005];
void update(int p)
{
	tr[p].one=((long long)tr[p<<1].one+tr[p<<1|1].one)%mod;
	tr[p].zero=((long long)tr[p<<1].zero+tr[p<<1|1].zero)%mod;
	tr[p].onenum=tr[p<<1].onenum+tr[p<<1|1].onenum;
	tr[p].zeronum=tr[p<<1].zeronum+tr[p<<1|1].zeronum;
}
void build(int p,int l,int r)
{
	tr[p].tag=0;
	if (l==r)
	{
		tr[p].one=one[l];
		tr[p].zero=zero[r];
		if (tr[p].one!=0) { tr[p].onenum=1; tr[p].zeronum=0; }
		else { tr[p].zeronum=1; tr[p].onenum=0; }
		return;
	}
	int mid=l+r>>1;
	build(p<<1,l,mid);
	build(p<<1|1,mid+1,r);
	update(p);
}
void pushdown(int p)
{
	if (tr[p].tag)
	{
		tr[p].tag=0;
		tr[p<<1].tag^=1;
		tr[p<<1|1].tag^=1;
		swap(tr[p<<1].one,tr[p<<1].zero);
		swap(tr[p<<1|1].one,tr[p<<1|1].zero);
		swap(tr[p<<1].onenum,tr[p<<1].zeronum); 
		swap(tr[p<<1|1].onenum,tr[p<<1|1].zeronum); 
	}
}
void change(int p,int l,int r,int L,int R)
{
	if (l>r) return;
	if (L>R) return;
	if (l==r) { swap(tr[p].one,tr[p].zero); swap(tr[p].onenum,tr[p].zeronum); return; }
	if (l>=L&&r<=R)
	{
		swap(tr[p].one,tr[p].zero);
		swap(tr[p].onenum,tr[p].zeronum);
		tr[p].tag^=1;
		return;	
	}
	pushdown(p);
	int mid=l+r>>1;
	if (L<=mid) change(p<<1,l,mid,L,R);
	if (R>mid) change(p<<1|1,mid+1,r,L,R);
	update(p);
}
struct res
{
	long long one,zero;
};
res ask(int p,int l,int r,int L,int R)
{
	if (l>r) { return {0,0}; }
	if (l==r) { return {tr[p].one,tr[p].zero}; }
	if (l>=L&&r<=R)
	{
		return {tr[p].one,tr[p].zero};
	}
	pushdown(p);
	int mid=l+r>>1;
	res ans={0,0},sum={0,0};
	if (L<=mid) ans=ask(p<<1,l,mid,L,R);
	if (R>mid) sum=ask(p<<1|1,mid+1,r,L,R);
	return {(long long)(ans.one+sum.one)%mod,(long long)(ans.zero+sum.zero)%mod};
}
/*
int query(int p,int l,int r,int L,int R)
{
	if(L<=l&&r<=R) return tr[]
}*/
signed main()
{
	while (scanf("%d%d",&n,&m)!=EOF)
	{
		getchar();
		for (int i=1;i<=n;++i)
		{
			zero[i]=one[i]=0;
		}
		
		for (int i=1;i<=n;++i)
		{
			char ch;
			ch=getchar();
			a[i]=ch-'0';
			if (a[i]==1) one[i]=i;
			if (a[i]==0) zero[i]=i;
		}
		build(1,1,n);
		for (int i=1;i<=m;++i)
		{
			int x,y;
			scanf("%lld%lld",&x,&y);
			change(1,1,n,x,y);
			int k=tr[1].onenum;
			if (k==n) { printf("%lld\n",n); continue; }
			if (k==0) { printf("0\n"); continue; }
			if (ask(1,1,n,k,k).zero==k)
			{
				int lzero=ask(1,1,n,1,k-1).zero;
				int rone=ask(1,1,n,k,n).one;
				if (k==n) { printf("%lld\n",n); continue; }
				if (k==0) { printf("0\n"); continue; }
				printf("%lld\n",(rone*2-(2*lzero+k)+mod)%mod);
			}
			else
			{
				int lzero=ask(1,1,n,1,k-1).zero;
				int rone=ask(1,1,n,k+1,n).one;
				if (k==n) { printf("%lld\n",n); continue; }
				if (k==0) { printf("0\n"); continue; }
				printf("%lld\n",(rone*2+k-2*lzero+mod)%mod);
			}
		}
	}
	return 0;
}