该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

裂缝谱（gap）

题目描述

猪猪正在研究一种特殊的整数生成过程。

给定正整数 $n$ 以及正整数序列 $c_1,c_2,\ldots,c_n$ 。定义 $S_0=0$ ，并对 $1\le i\le n$ 依次生成

a_i=S_{i-1}+c_i,\qquad S_i=S_{i-1}+a_i。

对于每个 $i$ ，任选一个符号 $\varepsilon_i\in\{-1,1\}$ ，可以得到一个整数

x=\sum_{i=1}^{n}\varepsilon_i a_i。

在上述生成规则下，全部 $2^n$ 种符号方案得到的整数互不相同。将这些整数从小到大排列为

x_1<x_2<\cdots<x_{2^n}。

对于 $1\le j<2^n$ ，定义第 $j$ 条裂缝的宽度为

d_j=x_{j+1}-x_j。

猪猪有 $q$ 次询问。每次给定两个二进制整数 $L,R$ 和一个十进制整数 $K$ ，设 $L,R$ 表示的整数分别为 $\ell,r$ ，你需要求出满足

\ell\le j\le r,\qquad d_j\le K

的裂缝数量，以及这些裂缝宽度之和。

由于答案可能很大，输出时均对 $998244353$ 取模。

第一行包含两个整数 $n,q$ 。

第二行包含 $n$ 个正整数 $c_1,c_2,\ldots,c_n$ 。

接下来 $q$ 行，每行包含两个二进制字符串 $L,R$ 和一个十进制整数 $K$ ，表示一次询问。

输入保证 $L,R$ 不含前导 $0$ ，且其表示的整数 $\ell,r$ 满足 $1\le \ell\le r\le 2^n-1$ 。

对于每次询问，输出一行两个整数，分别表示满足条件的裂缝数量与裂缝宽度之和，均对 $998244353$ 取模。

4 4
2 5 1 4
1 1111 4
10 1000 9
100 1100 2
1001 1111 100

对于 $100\%$ 的数据，保证 $1\le n,q\le 2\times 10^5$ ， $1\le c_i\le 10^9$ ， $1\le K\le 2\times 10^9$ ，所有询问中 $L,R$ 的长度之和不超过 $6\times 10^5$ 。

测试点编号	分值	$n\le$	$q\le$	二进制总长 $\le$	特殊性质
$1\sim2$	$10$	$20$		$400$	无
$3\sim5$	$15$	$200$		$5000$	特殊性质 A
$6\sim8$	$15$	$5000$	$5000$	$2\times 10^4$	特殊性质 B
$9\sim12$	$20$	$5000$	$2\times 10^5$	$6\times 10^5$	无
$13\sim20$	$40$	$2\times 10^5$	$2\times 10^5$	$6\times 10^5$	无