你知道那些给你一个长度大约为 $10^5$ 的数组，并且你需要处理大约 $10^5$ 个关于区间查询的问题吗？是的，这就是其中之一。而且它应该是可持久化的，因为为什么不呢。

考虑一个 $k \times n$ 的矩阵 $A$（有 $k$ 行 $n$ 列）。对于给定的矩阵，我们可以按如下方式构造数组 $B$：$B_j = \sum_{i=1}^k A_{ij}$。

矩阵最多会有 $q + 1$ 个版本。矩阵 $A$ 的第 $t$ 个版本的第 $i$ 行第 $j$ 个元素记为 $A_{ij}^{(t)}$。与矩阵 $A$ 的第 $t$ 个版本相对应的数组 $B$ 的第 $j$ 个元素记为 $B_j^{(t)}$。

给你矩阵 $A$ 的第 $0$ 个版本。你需要处理 $q$ 个以下 3 种类型的询问：

• 1 t p l r x：对于所有 $l \le i \le r$，将 $A_{pi}^{(t)}$ 加上 $x$，从而创建矩阵的一个新版本。
• 2 t p l r y：对于所有 $l \le i \le r$，将 $A_{pi}^{(t)}$ 的值设为 $y$，从而创建矩阵的一个新版本。
• 3 t l r：输出 $\min_{i=l}^r B_i^{(t)}$。

在第 $i$ 次操作（查询）后创建的矩阵 $A$ 的版本将被称作第 $i$ 个版本。因此，版本号可以是从 $0$ 到 $q$（含）的整数，但 $0$ 到 $q$ 之间的某些整数可能没有对应的版本。

输入格式

输入的第一行包含 3 个整数 $k, n, q$ ($1 \le k \le 4, 1 \le n \le 250\,000, 1 \le q \le 20\,000$) —— 分别表示矩阵的维度和询问的数量。

接下来的 $k$ 行中，第 $i$ 行包含 $n$ 个整数 $A_{i1}^{(0)}, A_{i2}^{(0)}, \dots, A_{in}^{(0)}$ ($|A_{ij}^{(0)}| \le 10^8$)。

接下来的 $q$ 行按前面说明的格式描述询问。保证 $t$ 指向一个已经存在的有效矩阵版本，且 $1 \le p \le k, 1 \le l \le r \le n, |x| \le 10^4, |y| \le 10^8$。

保证至少存在一个第 3 类的询问。

输出格式

按询问给出的顺序，在单独的行中输出第 3 类询问的答案。

样例

输入样例 1

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

输出样例 1

7
2
10
7
4

说明

以下是各个版本矩阵的示意图：

圆圈中的数字表示版本号，菱形中的数字表示第 3 类询问。