31147번 - New Queries On Segment Deluxe 다국어

문제

You know those problems where you are given an array of length roughly 10ドル^5$ and you have to process roughly 10ドル^5$ queries about something on a segment? Yes, this is one of those problems. And it should be persistent, because why not.

Consider $k \times n$ matrix $A$ (with $k$ rows and $n$ columns). For a given matrix we can construct the array $B$ as follows: $B_{j} = \sum_{i=1}^{k} A_{ij}$.

There will be up to $q+1$ versions of the matrix. The $j$-th element in $i$-th row of $t$-th version of $A$ is denoted as $A_{ij}^{(t)}$. The $j$-th element of the array $B$ corresponding to $t$-th version of $A$ is denoted as $B_{j}^{(t)}$.

You are given the 0ドル$-th version of the matrix $A$. You have to process $q$ queries of 3 types:

• 1 t p l r x : add $x$ to $A_{pi}^{(t)}$ for $l \le i \le r,ドル thus creating a new version of the matrix
• 2 t p l r y : set $A_{pi}^{(t)}$ to be equal to $y$ for $l \le i \le r,ドル thus creating a new version of the matrix
• 3 t l r : print $\min_{i=l}^{r} B_{i}^{(t)}$

The version of the matrix $A$ created after the $i$-th query will be called the $i$-th version. Thus version numbers can be from 0ドル$ to $q$ inclusive, but some of the integers from 0ドル$ to $q$ may not have the correspondent version.

입력

The first line of input contains 3 integers $k,ドル $n,ドル $q$ (1ドル \le k \le 4,ドル 1ドル \le n \le 250,000円,ドル 1ドル \le q \le 20,000円$) --- the dimensions of the matrix and the number of queries respectively.

The $i$-th of the next $k$ lines contains $n$ integers $A_{i1}^{(0)}, A_{i2}^{(0)}, \ldots, A_{in}^{(0)}$ ($|A_{ij}^{(0)}| \le 10^{8}$).

The next $q$ lines describe the queries in the format explained earlier. It is guaranteed that $t$ refers to a valid already existing version of the matrix, 1ドル \le p \le k,ドル 1ドル \le l \le r \le n,ドル $|x| \le 10^{4},ドル $|y| \le 10^{8}$.

It is guaranteed that there exists at least one query of type 3ドル$.

출력

Print the answers to the queries of type 3ドル$ in the order in which the queries were given, on separate lines.

제한

노트

Here is how the versions of the matrix will look like:

The number in a circle is the version, the numbers in rhombuses are queries of type 3ドル$.