对于一个包含 $n$ 个比特（即 0 和 1）的字符串 $s_1 \dots s_n$，Bobo 通过进行以下游戏来计算 $s_1 \dots s_n$ 的 $f$-值：

• 如果所有比特均为 0，游戏结束。
• 如果比特串中有 $k$ 个 1，Bobo 翻转第 $k$ 个比特，即 $s_k$。
• 比特串的 $f$-值是游戏结束前 Bobo 执行的翻转次数。

形式化地：

• 如果 $s_1 = \dots = s_n = 0$，$f(s_1 \dots s_n) = 0$。
• 否则，假设 $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$，其中 $\overline{c}$ 表示比特 $c$ 的翻转，即 $\overline{0} = 1$ 且 $\overline{1} = 0$。

现在，Bobo 有一个比特串 $s_1 \dots s_n$，并进行了 $q$ 次修改，其中第 $i$ 次修改是将 $s_{l_i} \dots s_{r_i}$ 范围内的所有比特翻转。请在每次修改后求出该比特串的 $f$-值对 998244353 取模的结果。

输入格式

输入包含多组测试数据，以文件结束符（EOF）结束。对于每组测试数据：

第一行包含两个整数 $n$ 和 $q$。 第二行包含 $n$ 个比特 $s_1 \dots s_n$。 接下来的 $q$ 行中，第 $i$ 行包含两个整数 $l_i$ 和 $r_i$。

数据范围

• $1 \le n \le 2 \times 10^5$
• $1 \le q \le 2 \times 10^5$
• 对于每个 $1 \le i \le n$，$s_i \in \{0, 1\}$
• 对于每个 $1 \le i \le q$，$1 \le l_i \le r_i \le n$
• 在每组输入中，$n$ 的总和不超过 $2 \times 10^5$，$q$ 的总和不超过 $2 \times 10^5$。

输出格式

对于每次修改，输出一个整数，表示 $f$-值对 998244353 取模的结果。

样例

输入 1

3 2
010
1 2
2 3
5 1
00000
1 5

输出 1

1
3
5

说明

对于第一组测试数据，第一次修改后字符串变为 100。$f(100) = f(000) + 1 = 1$。第二次修改后字符串变为 111。$f(111) = f(110) + 1 = f(100) + 2 = f(000) + 3 = 3$。