問題
0と1からなる長さ$N$の数列$A=(A_1,A_2,\dots,A_N)$が与えられます。以下の$Q$個のクエリ順に処理してください。
- クエリタイプ1:$1$ $L$ $R$ L番目からR番目までの要素の0と1を反転させる
- クエリタイプ2:$2$ $L$ $R$ L番目からR番目までの区間における、連続でなくてもよい部分列$1,1,0$の個数を$998244353$で割った余りを求めて出力する
入力
入力は以下の形式で標準入力から与えられる。
$N$ $A_1$ $A_2$ ... $A_N$ $Q$ $query_1$ $query_2$ $\vdots $ $query_Q$
1行目に整数$X$が与えられる。 2行目に整数$Y$が与えられる。
出力
出力の最後に改行を入れること。
制約
全ての入出力ケースについて以下を満たす。
- $1 \leq N,Q \leq 2*10^{5}$
- $A_i \in {0,1}$
- $1 \leq L \leq R \leq N$
入出力例
入力例1
7 0 0 1 1 0 1 0 5 2 1 7 1 1 4 2 1 7 1 3 6 2 1 7
出力例1
4 6 20