#include<bits/stdc++.h>
#define rep(i, l, r) for(int i = (l); i <= (r); i ++)
#define per(i, r, l) for(int i = (r); i >= (l); i --)
#define trv(i, u, v) for(int i = head[u], v = e[i].to; i; v = e[i = e[i].nxt].to)
#define fi first
#define se second
#define all(s) s.begin(), s.end()
#define sz(s) (int)(s.size())
#define lb(s) ((s) & -(s))
#define pb push_back
using namespace std;

typedef long long ll;
typedef pair<int, int> P;
mt19937_64 hua(time(0));
template<typename T> inline bool chkmx(T &x, T y) {return x < y ? x = y, 1 : 0;}
template<typename T> inline bool chkmn(T &x, T y) {return y < x ? x = y, 1 : 0;}
template<int T> using A = array<int, T>;

inline int read() {
	int x = 0, f = 1; char c = getchar();
	for(; !isdigit(c); c = getchar()) if(c == '-')  f = 0;
	for(; isdigit(c); c = getchar()) x = x * 10 + c - '0';
	return f ? x : -x;
}
const int maxn = 2e5;
const int mod = 998244353;
inline int add(int a, int b) {return (a += b) >= mod ? a - mod : a;}
int n, m;
char s[maxn + 5];
struct Segment {
	#define ls u << 1
	#define rs u << 1 | 1 
	struct Node {
		int sum[4], rev;
	}a[maxn + 5 << 2];
	void pushup(int u) {
		rep(c, 0, 3) a[u].sum[c] = add(a[ls].sum[c], a[rs].sum[c]);
	}
	void seta(int u) {
		swap(a[u].sum[0], a[u].sum[1]);
		swap(a[u].sum[2], a[u].sum[3]);
		a[u].rev ^= 1;
	}
	void pushdown(int u) {
		if(a[u].rev) seta(ls), seta(rs), a[u].rev = 0;
	}
	void update(int u, int l, int r, int ql, int qr) {
		if(l >= ql && r <= qr) return seta(u);
		int mid = l + r >> 1; pushdown(u);
		if(qr <= mid) update(ls, l, mid, ql, qr);
		else if(ql > mid) update(rs, mid + 1, r, ql, qr);
		else update(ls, l, mid, ql, qr), update(rs, mid + 1, r, ql, qr);
		pushup(u);
	}
	int query(int u, int l, int r, int ql, int qr, int c) {
		if(l >= ql && r <= qr) return a[u].sum[c];
		int mid = l + r >> 1; pushdown(u);
		if(qr <= mid) return query(ls, l, mid, ql, qr, c);
		else if(ql > mid) return query(rs, mid + 1, r, ql, qr, c);
		else return add(query(ls, l, mid, ql, qr, c), query(rs, mid + 1, r, ql, qr, c));
	}
	int find(int u, int l, int r, int p, ll &cnt, int c) {
		if(l >= p && a[u].sum[c] < cnt) {
			cnt -= a[u].sum[c];
			return -1;
		}
		if(l == r) return l;
		int mid = l + r >> 1; pushdown(u);
		if(p > mid) return find(rs, mid + 1, r, p, cnt, c);
		else {
			int x = find(ls, l, mid, p, cnt, c);
			return x == -1 ? find(rs, mid + 1, r, p, cnt, c) : x;
		}
	}
	void build(int u, int l, int r) {
		a[u].rev = 0;
		if(l == r) {
			rep(i, 0, 3) a[u].sum[i] = 0;
			a[u].sum[s[l] - '0'] = 1;
			a[u].sum[s[l] - '0' + 2] = l;
			return ;
		}
		int mid = l + r >> 1;
		build(ls, l, mid), build(rs, mid + 1, r);
		pushup(u);
	}
}ds;
void solve() {
	cin >> s + 1;
	ds.build(1, 1, n);
	rep(i, 1, m) {
		int l = read(), r = read();
		ds.update(1, 1, n, l, r);
		ll p = ds.query(1, 1, n, 1, n, 1);
		if(!p) {
			cout << 0 << '\n';
			continue;
		}
		ll s1 = ds.query(1, 1, n, 1, p, 2), lcnt = ds.query(1, 1, n, 1, p, 0);
		ll rcnt = lcnt;
		ll ans = - s1 + lcnt * p - rcnt * p;
		ll q = ds.find(1, 1, n, p + 1, rcnt, 1), s2 = p + 1 <= q ? ds.query(1, 1, n, p + 1, q, 3) : 0;
		ans += s2; ans %= mod, ans += mod, ans %= mod;
		cout << (2 * ans + p) % mod << '\n';
	}
}
int main() {
//	freopen("in.txt", "r", stdin);
//	freopen("out.txt", "w", stdout);
ios::sync_with_stdio(0);
cin.tie(0); 
cout.tie(0); 
	while(cin >> n >> m) {
		solve();
	}
	return 0;
}