题目背景

木棍 + 木棍 = 木棍。

题目描述

对于一个 $01$ 串 $S$，定义 $f(S)$ 为：删除 $S$ 中所有的 01 子串，重复若干次直到 $S$ 中不含有 01 子串，此时剩下的字符串即为 $f(S)$。可以证明删除顺序不影响最终结果。

定义价值函数 $V(S)=\sum\limits_T [|S|=|T|][f(S)=f(T)]$。

给定长度为 $n$ 的 $01$ 串 $S$，需要支持以下两种操作：

• 1 l r 对于 $S$ 中第 $l$ 个字符到第 $r$ 个字符中的每一个字符，若其是 $0$ 则修改为 $1$，否则修改为 $0$。

• 2 l r 对于 $S$ 中第 $l$ 个字符到第 $r$ 个字符所组成的子串 $T$，求 $V(T)\bmod 998244353$。

输入格式

第一行一个正整数 $n$，表示 $S$ 的长度。

第二行 $n$ 个字符，表示 $01$ 串 $s$。

第三行一个正整数 $q$，表示操作次数。

接下来 $q$ 行，每行三个正整数 $op,l,r$，表示操作类型和参数。

输出格式

对于每个操作 $2$，输出 $V(T)\bmod 998244353$。

5
00111
2
1 4 5
2 1 4

3

5
11111
2
1 3 3
2 2 5

3

10
1011011001
6
2 2 2
2 1 9
1 2 9
1 4 6
1 7 8
2 3 7

1
27
5

15
001001111010100
8
1 4 15
2 4 12
2 6 11
1 7 8
2 4 4
2 7 10
2 1 9
2 12 13

27
5
1
3
48
1

提示

【数据范围】

本题采用捆绑测试。

对于 $100\%$ 的数据，保证 $1\le n,q\le 5\times 10^5,op\in\{1,2\},1\le l\le r\le n$。

$\text{Subtask}$	$n\le$	$q\le$	特殊性质	分值
$1$	$20$		无	$5$
$2$	$500$	$1$	有	$15$
$3$	$5000$	^
$4$	$5\times 10^5$			$25$
$5$	$5000$		无	$10$
$6$	$10^5$		^
$7$	$5\times 10^5$			$20$

特殊性质：保证存在一次操作 $2$ 满足 $l=1,r=n$。