Digit DP
工厂中有 2n 台机器,编号从 0 到 2n−1。第 i 台机器当前消耗的功率为 pi。工厂使用名为 Digit Dynamic Powering(Digit DP)的系统管理这些功率。
初始时给出数组 a0,a1,…,an−1。令 Si 为整数 i 的二进制表示中所有为 1 的位的位置集合,其中最低位的位置是 0,则初始功率为
pi=j∈Si∑aj.
系统支持两种操作:
- 修改:给出 ℓ,r,x,把闭区间 [ℓ,r] 中每台机器的功率都增加 x。修改会持续生效。
- 查询:给出 ℓ,r。任意选择区间中三台不同的机器,用它们生产的产品价格为这三台机器功率的乘积。求所有选法的产品价格之和,即
$$\sum_{\ell\le i<j<k\le r}p_i p_j p_k\pmod{998244353}.$$
所有操作中的区间端点均以恰好 n 位的二进制字符串给出,最左边是最高位。
输入格式
第一行包含两个整数 n,q,其中 1≤n≤100,1≤q≤5⋅104。
第二行包含 n 个整数 a0,a1,…,an−1,满足 0≤ai≤109。
接下来 q 行依次描述操作。每行第一个整数为类型 t:
- 若 t=1,随后给出 ℓ,r,x,表示区间增加。满足 0≤ℓ≤r<2n,0≤x≤109。
- 若 t=2,随后给出 ℓ,r,表示查询。满足 0≤ℓ≤r<2n。
ℓ,r 均使用上述 n 位二进制格式;n,q,ai,t,x 使用十进制。
输出格式
对每次类型 2 操作,输出一行一个整数,表示答案对 998244353 取模后的值。若不存在查询操作,则不输出任何内容。
样例 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,3,4,5,6,6,7]。样例 2 的初始功率为 [0,1,1,2],虽然两台机器功率相同,它们仍是不同机器。