诡秘之主

题目背景

在《诡秘之主》的世界中，人类想要成为真正的非凡者，只能依靠魔药。在神灵庇佑下与巨人、恶魔、异种等对抗的人类，逐渐摸索出了获得超凡之力的办法，那就是用恶灵，用巨龙，用怪物，用神奇树木、花朵或结晶的对应部位，配合其余材料，调制成魔药，然后服用吸收，掌握不同的能力，这是所有神秘学派系共同的常识。

如果直接服用高品阶、超常规的魔药，很容易得到悲剧的下场，结果只有三种可能。第一，精神死亡，身体崩溃，每一块血肉都变成可怕的怪物，第二，被魔药里蕴含的力量瞬间改变人格，变得冷酷，敏感，易怒，残忍，漠视一切，第三，精神失常，当场发狂，比恶魔还恶魔，这就是失控。

经过漫长的实验和摸索，加上“亵渎石板”的出世，人类终于完善了魔药体系，形成了一些逐阶提升，稳定增长的序列链条，序列数字越低，魔药品阶越高，七大教会各自最少掌握了一个完整的序列途径，另外还有几百年，几千年内搜集到的、不那么完整的“路径”。

在第一块亵渎石板之后出现，通过服食魔药完成生命层次的晋升，最终成神，这种进化的路径称为神之途径。在原书中，共有 $22$ 条神之途径，每条途径有序列 $9$ 到序列 $0$ 共 $10$ 个序列，每个序列都拥有唯一性，代表着神灵的权柄，只有容纳唯一性才能获得成神的机会。

但在许多年后产生的网游《诡秘之主》中，有数不清的神之途径，每条途径都有 $\le {114514^{114514}}^{114514 \cdots }$（共 $114514$ 个 $114514$ ）个序列，但每条途径的终点仍然是序列 $0$ ，每条途径也仍然具有唯一性。游戏玩家在发展到一定地步后可以加入组织互相协助，作为游戏中某组织的领袖，今天你要带领组织中的成员去执行一项任务。

题目描述

这次的任务是探索一处古代遗迹——二叉搜索树。这一遗迹神秘而又危险，但通过预言/占卜相关能力的队员的帮助，你知道这一遗迹由无数个洞穴组成，洞穴之间连边形成了一棵二叉树的形态，每个洞穴都封印着神秘物品，且每个洞穴的左儿子子树中所有洞穴封印的物品都比自己封印的更加危险，右儿子子树中封印的都比自己封印的更安全。

因此，你制订了以下探索方案：当一队人前来探索遗迹时，他们会按顺序依次进入树的根节点，当一位队员来到某个节点时：

• 如果当前节点还没有人，该队员会停在这个节点，以防止此地出现异变影响后续探索。

• 如果当前节点有人，且对方的序列 $\geq$ 自己的序列，则该队员会继续走到当前节点的左儿子节点中进行探索。

• 如果当前节点有人，且对方的序列 $<$ 自己的序列，则该队员会继续走到当前节点的右儿子节点中进行探索。

所有队员都依次进入后，定义这样一次探索的成功度为所有队员最终停留位置与根节点的距离的最大值。在遗迹中距离定义为两点之间的简单路径中的点数 $-1$ 。

现在，你集结了组织中的 $n$ 位成员，他们排成一列等候调遣，依次编号为 $1$ ∼ $n$ 。但不幸的是，你不知道他们的序列确切是多少，因为序列 $0$ 具有唯一性，你知道哪些人的序列为 $0$ ，除此之外的人的序列均 $\ge 1$ 。于是你决定派遣编号为 $l$ ∼ $r$ 的成员，按照编号从小到大排序后进行探索，并粗略的认为这样一次探索的收益为，将所有不确定序列的队员的序列任意指定为 $\le {114514^{114514}}^{114514 \cdots }$ 的正整数时，能获得的探索成功度的最小值。你将它称为区间 $[l, r]$ 的权值。

于是为了能更好的进行探索，他想询问你——一位占卜家，区间 $[x, y]$ 的所有子区间的权值之和是多少？当然，一个严谨的队长不会只询问一次，而是会询问 $q$ 次，你都需要进行回答。

输入格式

第一行两个非负整数 $n, q$ 分别表示队员的数量以及询问的数量。

第二行是一个长为 $n$ 的 $01$ 串，第 $i$ 位为 $0$ 表示第 $i$ 个队员的序列为 $0$ ，为 $1$表示第 $i$ 个队员的序列可能是任意 $\le {114514^{114514}}^{114514 \cdots }$ 的正整数。

接下来 $q$ 行，每行两个正整数 $l, r$ ，表示询问区间 $[l, r]$ 的所有子区间的权值之和对 $998244353$ 取模后的结果。

输出格式

输出 $q$ 行，第 $i$ 行一个正整数表示第 $i$ 个询问的答案对 $998244353$ 取模后的结果。

样例输入1

4 4
1011
1 4
2 2
2 3
1 3

样例输出1

8
0 
1
3

【样例 2】

见选手目录下的 mystery2*.in* 与 mystery2*.ans*。

该样例与子任务 2 满足同样的约束条件。

【样例 3】

见选手目录下的 mystery3*.in* 与 mystery3*.ans*。

该样例与子任务 3 满足同样的约束条件。

【样例 4】

见选手目录下的 mystery4*.in* 与 mystery4*.ans*。

该样例与子任务 4 满足同样的约束条件。

数据规模和约定

对于所有测试数据： $1 \le n, q \le 2 \times 10^5, 1 \le l \le r \le n$ 。

本题评测开启捆绑测试。

子任务编号	$n \le$	$q \le$	特殊性质	子任务分数	子任务依赖
$1$	$500$		无	$10$	无
$2$	$2000$			$15$	$1$
$3$	$2 \times 10^5$	$2 \times 10^5$	$A$	$5$	无
$4$		$1$	$B$	$30$
$5$	$5 \times 10^4$		无	$20$	$2$
$6$	$2 \times 10^5$				$3, 4, 5$

特殊性质 $A$ ：保证所有队员的序列均不为 $0$ 。

特殊性质 $B$ ：对于所有询问有 $l = 1, r = n$ 。