Game Theory

For a string $s_1\dots s_n$ of $n$ bits (i.e., zeros and ones), Bobo computes the $f$-value of $s_1\dots s_n$ by playing the following game.

• If all the bits are zero, the game ends.
• If there are $k$ ones in the bit string, Bobo flips the $k$-th bit, i.e., $s_k$.
• The $f$-value of the bit string is the number of flips Bobo has performed before the game ends.

Formally,

• If $s_1 = \dots = s_n = 0$, $f(s_1 \dots s_n) = 0$.
• Otherwise, assuming that $k = s_1 + \dots + s_n$, $f(s_1 \dots s_n) = f(s_1 \dots s_{k - 1} \overline{s_k} s_{k + 1} \dots s_n) + 1$ where $\overline{c}$ denotes the flip of the bit $c$ such as $\overline{0} = 1$ and $\overline{1} = 0$.

Now, Bobo has a bit string $s_1 \dots s_n$ subjecting to $q$ changes, where the $i$-th change is to flip all the bits among $s_{l_i} \dots s_{r_i}$ for given $l_i$, $r_i$. Find the $f$-value modulo $998244353$ of the bit string after each change.

The input consists of several test cases terminated by end-of-file. For each test case,

The first line contains two integers $n$ and $q$.

The second line contains $n$ bits $s_1 \dots s_n$.

For the following $q$ lines, the $i$-th line contains two integers $l_i$ and $r_i$.

For each change, output an integer which denotes the $f$-value modulo $998244353$.

• $1 \le n \le 2 \times 10^5$
• $1 \le q \le 2 \times 10^5$
• $s_i \in \{0, 1\}$ for each $1 \leq i \leq n$
• $1 \leq l_i \leq r_i \leq n$ for each $1 \leq i \leq q$
• In each input, the sum of $n$ does not exceed $2 \times 10^5$. The sum of $q$ does not exceed $2 \times 10^5$.

For the first test case, the string becomes "100" after the first change. $f($100$) = f($000$) + 1 = 1$. And it becomes "111" after the second change. $f($111$) = f($110$) + 1 = f($100$) + 2 = f($000$) + 3 = 3$.