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(s1 \dots s{k - 1} \overline{sk} 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 sn subjecting to q changes, where the i-th change is to flip all the bits among s{li} \dots s{r_i} for given l_i, r_i. Find the f$-value modulo 998244353 of the bit string after each change.

Note from SCNUOJ admin: we don't have the official test data sets, and all tests used here are randomly generated, so expect weak tests and/or even wrong input format. Contact one of the admins if you wish to improve the tests.

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.

• 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 each change, output an integer which denotes the f-value modulo 998244353.

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