时空限制

3S/512M

题目描述

给定一个大小为 $2^n \times 2^n$ 的矩阵 $M$，其行、列下标的范围均为 $[0, 2^n - 1]$。矩阵中每个元素 $M_{i,j}$ 的值，都由一个给定的、大小为 $n \times 4$ 的代价矩阵 $A$ 所决定（$A_{i,j}$ 的下标同样从 $0$ 开始）。

具体地，将非负整数 $i$ 和 $j$ 分别用二进制表示为： $(i_{n-1} \dots i_1 i_0)_2$ 和 $(j_{n-1} \dots j_1 j_0)_2$ 其中 $i_k, j_k \in \{0, 1\}$。定义函数：

$$f_k(i, j) = 2 \cdot i_k + j_k$$

则 $M_{i,j}$ 的值由下式给出：

$$M_{i,j} = \sum_{k=0}^{n-1} A_{k,f_k(i, j)}$$

你需要处理 $Q$ 个操作：

• 类型 1 (修改)：给定 $k, c, v$，把 $A_{k,c}$ 的值修改为 $v$。
• 类型 2 (查询)：给定 $r_1 ,c_1 ,r_2 ,c_2$，计算 $(\sum_{i=r_1}^{r_2} \sum_{j=c_1}^{c_2} M_{i,j} )\bmod 998244353$。

格式

输入格式

第一行包含一个整数 $n$。

接下来 $n$ 行，每行包含 $4$ 个整数。其中第 $k$ 行的 $4$ 个整数分别表示 $A_{k-1, 0}, A_{k-1, 1}, A_{k-1, 2}, A_{k-1, 3}$。

接下来一行包含一个整数 $Q$，表示操作的总次数。

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

• 若该行的第一个整数为 $1$，则其后跟有三个整数 $k, c, v$，表示一次修改操作，你需要将 $A_{k,c}$ 修改为 $v$。
• 若该行的第一个整数为 $2$，则其后跟有四个整数 $r_1, c_1, r_2, c_2$，表示一次查询操作。

输出格式

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

样例

样例输入 #1

2 
1 2 3 4
5 6 7 8
3
2 0 0 3 3
1 0 1 10
2 0 0 1 1

样例输出 #1

144
38

样例输出 #1

修改前 $M$ 矩阵为：

$$\begin{pmatrix} 6 & 7 & 7 & 8 \\ 8 & 9 & 9 & 10 \\ 8 & 9 & 9 & 10 \\ 10 & 11 & 11 & 12 \end{pmatrix} $$

• 第一个查询即整个矩阵的和，故输出 $144$。

第二个操作后，$M$ 矩阵变为：

$$ \begin{pmatrix} 6 & 15 & 7 & 16 \\ 8 & 9 & 9 & 10 \\ 8 & 17 & 9 & 18 \\ 10 & 11 & 11 & 12 \end{pmatrix} $$

• 最后一个查询操作查询的范围是左上角 $2 \times 2$ 的子矩阵，答案为 $6 + 15 + 8 + 9 =38$。

数据规模

对于 $20\%$ 的数据，$1 \leq n \leq 10$，$1 \leq Q \leq 10$。

对于 $50\%$ 的数据，$1 \leq n \leq 20$。

对于 $100\%$ 的数据，$1 \leq n \leq 40$，$1 \leq Q \leq 5 \times 10^5$，$0 \leq A_{i,j}, v < 998244353$，， $0 \leq r_1 \leq r_2 < 2^n, 0 \leq c_1 \leq c_2 < 2^n$。