#include"bits/stdc++.h"
using namespace std;
typedef long long ll;
template<class T1,class T2> bool cmin(T1 &x,const T2 &y) { if (y<x) { x=y; return 1; }return 0; }
template<class T1,class T2> bool cmax(T1 &x,const T2 &y) { if (x<y) { x=y; return 1; }return 0; }
#define all(x) (x).begin(),(x).end()
struct node
{
	ll s1,s0;
	int c1,c0;
	void rev() { swap(s1,s0); swap(c1,c0); }
	node operator+(const node &o) const { return {s1+o.s1,s0+o.s0,c1+o.c1,c0+o.c0}; }
};
const int M=8e5+5;
node s[M];
bool lz[M];
int *b;
int z,y;
void build(int x,int l,int r)
{
	lz[x]=0;
	if (l==r)
	{
		if (b[l]) s[x]={l,0,1,0};
		else s[x]={0,l,0,1};
		return;
	}
	int c=x*2,m=l+r>>1;
	build(c,l,m); build(c+1,m+1,r);
	s[x]=s[c]+s[c+1];
}
void modify(int x,int l,int r)
{
	if (z<=l&&r<=y)
	{
		s[x].rev();
		lz[x]^=1;
		return;
	}
	int c=x*2,m=l+r>>1;
	if (lz[x])
	{
		lz[c]^=1;
		lz[c+1]^=1;
		s[c].rev();
		s[c+1].rev();
		lz[x]=0;
	}
	if (z<=m) modify(c,l,m);
	if (y>m) modify(c+1,m+1,r);
	s[x]=s[c]+s[c+1];
}
node tmp;
void ask(int x,int l,int r)
{
	if (z<=l&&r<=y)
	{
		// s[x].rev();
		// lz[x]^=1;
		tmp=tmp+s[x];
		return;
	}
	int c=x*2,m=l+r>>1;
	if (lz[x])
	{
		lz[c]^=1;
		lz[c+1]^=1;
		s[c].rev();
		s[c+1].rev();
		lz[x]=0;
	}
	if (z<=m) ask(c,l,m);
	if (y>m) ask(c+1,m+1,r);
}
mt19937 rnd(2345);
int main()
{
	ios::sync_with_stdio(0); cin.tie(0);
	int n,m,i,j;
	int T=100;
	// while (T--)
	while (cin>>n>>m)
	{
		// n=100; m=1000;
		vector<int> a(n+1);
		{
			string s;
			cin>>s;
			for (i=1; i<=n; i++) a[i]=s[i-1]&1;
			// for (i=1; i<=n; i++) a[i]=rnd()&1;
		}
		b=a.data();
		build(1,1,n);
		while (m--)
		{
			int l,r;
			cin>>l>>r;
			// l=rnd()%n+1,r=rnd()%n+1;
			// if (l>r) swap(l,r);
			z=l; y=r;
			modify(1,1,n);
			int c=s[1].c1;
			ll ans=0;
			{
				z=c; y=n; tmp={0,0,0,0};
				ask(1,1,n);
				ans+=tmp.s1;
			}
			if (c>1)
			{
				z=1; y=c-1; tmp={0,0,0,0};
				ask(1,1,n);
				ans-=tmp.s0;
			}
			// ll ta=0;
			// for (i=l; i<=r; i++) a[i]^=1;
			// for (i=1; i<=n; i++) cerr<<a[i]; cerr<<endl;
			// {
			// 	int c=count(all(a),1);
			// 	for (i=c; i<=n; i++) ta+=a[i]*i;
			// 	for (i=1; i<c; i++) ta-=(!a[i])*i;
			// }
			cout<<ans%998244353<<'\n';
			// assert(ans==ta);
		}
	}
}