CF1093G.Multidimensional Queries

You are given an array $a$ of $n$ points in $k$-dimensional space. Let the distance between two points $a_x$ and $a_y$ be $\sum \limits_{i = 1}^{k} |a_{x, i} - a_{y, i}|$ (it is also known as Manhattan distance).

You have to process $q$ queries of the following two types:

• $1$ $i$ $b_1$ $b_2$ ... $b_k$ — set $i$-th element of $a$ to the point $(b_1, b_2, \dots, b_k)$;
• $2$ $l$ $r$ — find the maximum distance between two points $a_i$ and $a_j$, where $l \le i, j \le r$.

给你一个包含 $n$ 个点的数组 $a$，每个点位于 $k$ 维空间中。定义两个点 $a_x$ 和 $a_y$ 之间的距离为 $\sum \limits_{i = 1}^{k} |a_{x, i} - a_{y, i}|$（该距离也称为曼哈顿距离）。

你需要处理 $q$ 个如下两种类型的查询：

• $1$ $i$ $b_1$ $b_2$ ... $b_k$ —— 将数组 $a$ 的第 $i$ 个元素设置为点 $(b_1, b_2, \dots, b_k)$；
• $2$ $l$ $r$ —— 在下标满足 $l \le i, j \le r$ 的所有点对 $a_i$ 和 $a_j$ 中，求它们之间最大的距离。

The first line contains two numbers $n$ and $k$ ($1 \le n \le 2 \cdot 10^5$, $1 \le k \le 5$) — the number of elements in $a$ and the number of dimensions of the space, respectively.

Then $n$ lines follow, each containing $k$ integers $a_{i, 1}$, $a_{i, 2}$, ..., $a_{i, k}$ ($-10^6 \le a_{i, j} \le 10^6$) — the coordinates of $i$-th point.

The next line contains one integer $q$ ($1 \le q \le 2 \cdot 10^5$) — the number of queries.

Then $q$ lines follow, each denoting a query. There are two types of queries:

• $1$ $i$ $b_1$ $b_2$ ... $b_k$ ($1 \le i \le n$, $-10^6 \le b_j \le 10^6$) — set $i$-th element of $a$ to the point $(b_1, b_2, \dots, b_k)$;
• $2$ $l$ $r$ ($1 \le l \le r \le n$) — find the maximum distance between two points $a_i$ and $a_j$, where $l \le i, j \le r$.

There is at least one query of the second type.

第一行包含两个整数 $n$ 和 $k$（$1 \le n \le 2 \cdot 10^5$，$1 \le k \le 5$）—— 分别表示数组 $a$ 的元素个数以及空间的维数。

接下来 $n$ 行，每行包含 $k$ 个整数 $a_{i, 1}$、$a_{i, 2}$、…、$a_{i, k}$（$-10^6 \le a_{i, j} \le 10^6$）—— 表示第 $i$ 个点的坐标。

接下来一行包含一个整数 $q$（$1 \le q \le 2 \cdot 10^5$）—— 表示查询的个数。

随后 $q$ 行，每行描述一个查询。查询分为两类：

• $1$ $i$ $b_1$ $b_2$ … $b_k$（$1 \le i \le n$，$-10^6 \le b_j \le 10^6$）—— 将 $a$ 的第 $i$ 个元素更新为点 $(b_1, b_2, \dots, b_k)$；
• $2$ $l$ $r$（$1 \le l \le r \le n$）—— 求下标满足 $l \le i, j \le r$ 的所有点对 $a_i$ 与 $a_j$ 之间的最大距离。

保证至少存在一个第二类查询。

Print the answer for each query of the second type.

打印每个第二类查询的答案。