时空限制

2.5S/512M

题目描述

给定一个整数 $n$ 和一个长度为 $2^n$ 的数组 $f$（下标从 $0$ 到 $2^n-1$）。

定义了一个 $2^n \times 2^n$ 的矩阵 $W$（下标从 $0$ 到 $2^n-1$），其中矩阵元素 $W_{i,j} = f_{i \oplus j}$，这里 $\oplus$ 表示按位异或（XOR）运算。

现在需要支持以下两种操作：

1. 修改操作：给定下标 $i$ 和整数值 $v$，将 $f_i$ 的值增加 $v$。
2. 查询操作：给定两个坐标 $(x_1, y_1)$ 和 $(x_2, y_2)$，计算矩阵 $W$ 中以这两点为对角顶点的子矩阵元素之和。即计算：$$\sum_{i=x_1}^{x_2} \sum_{j=y_1}^{y_2} W_{i,j}$$

由于查询结果可能很大，需要将结果对 $998244353$ 取模。

格式

输入格式

第一行包含两个整数 $n$ 和 $Q$，分别表示数组大小参数和操作的总次数。

第二行包含 $2^n$ 个整数，表示数组 $f$ 的初始值 $f_0, f_1, \ldots, f_{2^n-1}$。

接下来 $Q$ 行，每行描述一个操作：

• 若该行为 $1 \; i \; v$，表示一个修改操作。
• 若该行为 $2 \; x_1 \; y_1 \; x_2 \; y_2$，表示一个查询操作。具体意义见题目描述。

输出格式

对于每个查询操作，输出一行，包含一个整数，表示所求的和模 $998244353$ 的结果。

样例

样例输入 #1

2 3
10 20 30 40
2 1 1 2 2
1 3 5
2 1 1 2 2

样例输出 #1

100
110

数据规模

对于 $20\%$ 的数据，$1 \le n \le 10$，且仅有查询操作。

对于 $100\%$ 的数据，$1 \le n \le 20$，$1 \le Q \le 2 \times 10^5$，$0 \le f[i], v < 998244353$。对于查询操作：$0 \le x_1 \le x_2 < 2^n$ 且 $0 \le y_1 \le y_2 < 2^n$。对于修改操作：$0 \le i < 2^n$。