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 (with rows and columns). For a given matrix we can construct the array as follows: B_{j} = \sum_{i=1}^{k} A_{ij}.
There will be up to q+1 versions of the matrix. The -th element in -th row of -th version of is denoted as A_{ij}^{(t)}. The -th element of the array corresponding to -th version of is denoted as B_{j}^{(t)}.
You are given the -th version of the matrix . You have to process queries of 3 types:
1 t p l r x : add 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 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 created after the -th query will be called the -th version. Thus version numbers can be from to inclusive, but some of the integers from to may not have the correspondent version.
The first line of input contains 3 integers , , (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 -th of the next lines contains integers A_{i1}^{(0)}, A_{i2}^{(0)}, \ldots, A_{in}^{(0)} (|A_{ij}^{(0)}| \le 10^{8}).
The next lines describe the queries in the format explained earlier. It is guaranteed that 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 .
Print the answers to the queries of type in the order in which the queries were given, on separate lines.
Example 1
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 .