New Queries On Segment Deluxe#13021

New Queries On Segment Deluxe

3 seconds
1,024 megabytes
Very hard

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:

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.

Input

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 .

Output

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

Examples

Example 1

Loading
Loading

Note

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 .