게임 이론

0과 1로 이루어진 $n$비트 문자열 $s_1 \dots s_n$에 대해, Bobo는 다음 게임을 진행하여 $f$값을 계산합니다.

• 모든 비트가 0이면 게임이 끝납니다.
• 비트 문자열에 1이 $k$개 있으면, Bobo는 $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$번째 변경은 주어진 $l_i$, $r_i$에 대해 $s_{l_i} \dots s_{r_i}$의 모든 비트를 뒤집습니다. 각 변경 후 비트 문자열의 $f$값을 $998244353$으로 나눈 나머지를 구하세요.

입력은 여러 개의 테스트 케이스로 구성되며, 파일 끝(EOF)에서 끝납니다. 각 테스트 케이스는 다음 형식입니다.

첫 번째 줄에 정수 $n$과 $q$가 주어집니다.

두 번째 줄에 $n$개의 비트 $s_1 \dots s_n$이 주어집니다.

이어지는 $q$개의 줄에는 각각 정수 $l_i$와 $r_i$가 주어집니다.

각 변경 후 비트 문자열의 $f$값을 $998244353$으로 나눈 나머지를 한 줄에 하나씩 출력하세요.

• $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$을 넘지 않습니다.

첫 번째 테스트 케이스에서 첫 번째 변경 후 문자열은 100이 됩니다. 따라서 $f(\texttt{100}) = f(\texttt{000}) + 1 = 1$입니다. 두 번째 변경 후에는 111이 되며, $f(\texttt{111}) = f(\texttt{110}) + 1 = f(\texttt{100}) + 2 = f(\texttt{000}) + 3 = 3$입니다.