给定一个 $$$a$$$ 数组,其中 $$$n$$$ 个点位于 $$$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$$$ — 求两点 $$$a_i$$$ 和 $$$a_j$$$ 之间的最大距离,其中 $$$l \le i, j \le r$$$。
输入
第一行包含两个数字 $$$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$$$) — 求两点 $$$a_i$$$ 和 $$$a_j$$$ 之间的最大距离,其中 $$$l \le i, j \le r$$$。
至少有一个第二类型的查询。
输出
打印第二类每个查询的答案。
示例
输入 #1
5 2 1 2 2 3 3 4 4 5 5 6 7 2 1 5 2 1 3 2 3 5 1 5 -1 -2 2 1 5 1 4 -1 -2 2 1 5
输出 #1
8 4 4 12 10