#P18408. Digit DP

Digit DP

Digit DP

工厂中有 2n2^n 台机器,编号从 00 到 2n−12^n-1。第 ii 台机器当前消耗的功率为 pip_i。工厂使用名为 Digit Dynamic Powering(Digit DP)的系统管理这些功率。

初始时给出数组 a0,a1,…,an−1a_0,a_1,\ldots,a_{n-1}。令 SiS_i 为整数 ii 的二进制表示中所有为 11 的位的位置集合,其中最低位的位置是 00,则初始功率为

pi=∑j∈Siaj.p_i=\sum_{j\in S_i}a_j.

系统支持两种操作:

  • 修改:给出 ℓ,r,x\ell,r,x,把闭区间 [ℓ,r][\ell,r] 中每台机器的功率都增加 xx。修改会持续生效。
  • 查询:给出 ℓ,r\ell,r。任意选择区间中三台不同的机器,用它们生产的产品价格为这三台机器功率的乘积。求所有选法的产品价格之和,即
$$\sum_{\ell\le i<j<k\le r}p_i p_j p_k\pmod{998244353}.$$

所有操作中的区间端点均以恰好 nn 位的二进制字符串给出,最左边是最高位。

输入格式

第一行包含两个整数 n,qn,q,其中 1≤n≤1001\le n\le100,1≤q≤5⋅1041\le q\le5\cdot10^4。

第二行包含 nn 个整数 a0,a1,…,an−1a_0,a_1,\ldots,a_{n-1},满足 0≤ai≤1090\le a_i\le10^9。

接下来 qq 行依次描述操作。每行第一个整数为类型 tt:

  • 若 t=1t=1,随后给出 ℓ,r,x\ell,r,x,表示区间增加。满足 0≤ℓ≤r<2n0\le\ell\le r<2^n,0≤x≤1090\le x\le10^9。
  • 若 t=2t=2,随后给出 ℓ,r\ell,r,表示查询。满足 0≤ℓ≤r<2n0\le\ell\le r<2^n。

ℓ,r\ell,r 均使用上述 nn 位二进制格式;n,q,ai,t,xn,q,a_i,t,x 使用十进制。

输出格式

对每次类型 22 操作,输出一行一个整数,表示答案对 998244353998244353 取模后的值。若不存在查询操作,则不输出任何内容。

样例 1

3 3
1 2 4
2 000 111
1 010 101 1
2 000 111
1960
3040

样例 2

2 2
1 1
2 00 10
2 00 11
0
2

帮助理解:样例 1 中初始功率依次为 [0,1,2,3,4,5,6,7][0,1,2,3,4,5,6,7];修改后为 [0,1,3,4,5,6,6,7][0,1,3,4,5,6,6,7]。样例 2 的初始功率为 [0,1,1,2][0,1,1,2],虽然两台机器功率相同,它们仍是不同机器。