题目背景

nodgd 又在玩崩坏星穹铁道，仅仅只是微氪就做到了全角色 6+5。大 $H$ 认真学习玩法后做出了如下简单模型。

有读不懂的，先继续读，配合后面形式化题意及样例解释进行理解。

题目描述

注：下文的敌方和我方统一为玩家视角。

游戏中有一个我方角色和若干敌方角色，敌方角色又分为 $0$ 和 $1$ 两种类型。

行动顺序为：我方角色先行动，然后敌方角色按顺序依次行动，不断重复。将一次我方行动到下一次我方行动之前称为一回合。

我方行动

我方行动时，依次执行如下两个操作：

1. 标记下一个行动的敌方角色。
2. 使一个未标记的敌方角色行动顺序延后（可以不改变）。

注：把一个角色行动顺序延后即改变这个角色行动的顺序，变化后只能在下一次该角色的行动之后且在同一个回合之内，且顺序改变是永久性的。

敌方行动

敌方角色有两种，用 $0$ 和 $1$ 区分。

当轮到某敌方角色行动时，依次执行如下三个判定及操作：

1. 若为 $1$ 角色，则对玩家造成伤害，伤害量为敌方当前存活角色数。
2. 若为 $0$ 角色或为被标记角色，则可以选择一个 $1$ 角色（不为自己），使其行动顺序提前（可以不改变）。
3. 若为被标记角色，则角色死亡，敌方存活角色数减一。其余角色行动顺序不变。若敌方存活角色数为 $0$ 则游戏结束。

注：把一个角色行动顺序提前即改变这个角色行动的顺序，变化后只能在下一次该角色的行动之前，且顺序改变是永久性的。

形式化解释

对于行动模式，形式化地描述就是有一个行动队列，最初包含一个我方角色在开头，敌方角色顺次排队。每次取出开头，根据开头的角色行动后将其放入队尾。将角色顺序提前即为在当前序列中，把一个角色插入到他之前的位置，延后即为把一个角色插入到他之后的位置。每当我方角色到达队列开头，进入新一回合。

游戏目标

我们可以用一个 $01$ 字符串代表敌方行动顺序（从左到右）。

在消灭完所有敌方角色情况下，你希望最小化受到的总伤害，而敌方希望最大化。设 $f(S)$ 表示，敌方顺序为字符串 $S$ 时，双方都采取最优策略情况下，你受到的总伤害值。

现在给出一个 $01$ 字符环 $T$，下标从 $1$ 到 $n$，$m$ 次询问，每次给出三个数 $x,l,r$。先改变位置 $x$ 上的字符后，询问 $f(T[l,r])$ 对 $998244353$ 取模后的结果。询问间不独立，即字符改变为永久性的。若 $l>r$ 则 $T[l,r]=T[l,n]+T[1,r]$，其中“$+$”表示拼接。

输入格式

第一行两个数 $n,m$。

第二行长度为 $n$ 的字符串 $T$。

之后 $m$ 行，每行三个数 $x,l,r$ 表示一次询问。

输出格式

$m$ 行，每次询问的答案对 $998244353$ 取模。

样例 1 输入

5 3
00000
3 2 4
4 4 2
2 1 4

样例 1 输出

6
4
20

样例 2 输入

8 5
00110111
8 3 8
2 1 8
5 1 7
4 1 8
6 8 6

样例 2 输出

68
158
112
158
97

说明与提示

下面为样例一第一次查询的解释（$2$ 为我方角色）：

1. 最初行动队列为 2010。
2. 我方行动：标记第一个 $0$。将 $1$ 延后或不延后。行动队列变成 0012 或 0102。
3. $0$ 角色行动：若 $1$ 被延后，将 $1$ 提到最前；否则不变化。死亡。行动队列一定变成 102。
4. $1$ 角色行动：造成 $2$ 伤害。行动队列变成 021。
5. $0$ 角色行动：将 $1$ 提前。行动队列变成 120。
6. $1$ 角色行动：造成 $2$ 伤害。行动队列变成 201。
7. 我方行动：标记 $0$。无法进行延后操作。行动队列变成 012。
8. $0$ 角色行动：无法操作。死亡。行动队列变成 12。
9. $1$ 角色行动：造成 $1$ 伤害。行动队列变成 21。
10. 我方行动：标记 $1$。无法进行延后操作。行动队列变成 12。
11. $1$ 角色行动：造成 $1$ 伤害。死亡。游戏结束。

对于所有数据，$n\le 4\times10^6$，$m\le 10^5$。

子任务	分值	$n\le$	$m\le$	特殊性质
1	10	$6$	$500$	无
2		$18$
3		$500$
4		$10^5$
5	15		$10^5$
6		$4\times10^6$		$x=n$
7	30			无

数据范围完全包含的子任务间有依赖关系。

附录（chatgpt 中译中版本，原文附带内容）

1. 游戏流程总览

游戏中有：

• 我方（玩家）：只有 $1$ 个单位，记作“我方角色”。
• 敌方：有若干个单位，每个敌方单位的类型为 $0$ 或 $1$。我们用一个 $01$ 串 $S$（从左到右）表示敌方单位在队列中的相对顺序（不含我方）。

游戏按“队列循环”进行：

• 行动顺序是：我方行动一次，然后敌方单位按当前队列顺序依次行动，之后进入下一回合，又从我方开始。
• 一回合：从某次我方行动开始，到下一次我方行动开始之前为止。

2. 队列与“提前/延后”的精确定义

我们维护一个循环行动队列，队头行动，行动后进入队尾。

• 初始队列：队头是我方角色，其后按 $S$ 的顺序放入所有敌方单位。
• 每次行动：取队头单位执行其规则，然后把它放到队尾。

2.1 “把某个敌方单位行动顺序提前”

等价于：在当前队列中，把该单位拿出来，插入到它原来位置之前的某个位置。

限制：只能插入到“该单位下一次行动之前”（也就是不能插到它已经行动之后的部分）。

2.2 “把某个敌方单位行动顺序延后”

等价于：在当前队列中，把该单位拿出来，插入到它原来位置之后的某个位置。

限制：只能插入到“该单位下一次行动之后”且仍在同一回合内（也就是不能跨到下一个回合的我方行动之后）。

以上两种顺序改变都是永久生效的（会影响之后所有回合），并且允许“不改变”（相当于插回原位）。

3. 我方行动规则（每回合开始时执行）

当轮到我方行动时，依次执行：

1. 标记：标记“接下来将要行动的敌方单位”（即我方行动结束后，队头将出现的第一个敌方单位）。
2. 延后操作：选择一个当前未被标记的敌方单位，将它的行动顺序延后（也可以选择不改变）。

4. 敌方行动规则（敌方单位行动时执行）

敌方单位分为类型 $0$ 和 $1$。当某个敌方单位轮到行动时，依次进行以下判定与操作：

1. 伤害判定：若该单位是 $1$，则对我方造成伤害，伤害值 = 当前敌方存活单位数。
2. 提前操作判定：若该单位是 $0$，或该单位是“被标记”的单位，则敌方可以选择一个 $1$ 单位（且不能选自己），把它的行动顺序提前（也可以不改变）。
3. 死亡判定：若该单位是“被标记”的单位，则它在本次行动结束后死亡，敌方存活数减 $1$。其余单位相对顺序不变。若敌方存活数变为 $0$，游戏立刻结束。

注意：只有“被标记”的单位会在行动后死亡；未被标记的敌方单位不会因为行动而死亡。

5. 对抗目标与函数 $f(S)$

给定敌方初始顺序串 $S$（长度为敌方单位数）：

• 我方希望最小化总受伤害。
• 敌方希望最大化总受伤害。

$f(S)$ 表示：双方都采取最优策略时，我方受到的总伤害。