Matrix Maintenance and Query

You are given an \(n \times m\) matrix \(A\) with all elements initially \(0\), and a sequence \(b\) of length \(m\). You need to perform \(q\) operations on \(A\). There are two types of operations:

• 1 l r x v: For the row \(x\), update every element in columns \(i\) (where \(l \le i \le r\)) to \(v\), i.e. set \(A_{x,i} = v\).
• 2 l r x y: Query the value \(\max_{i=l}^{r} \max_{j=x}^{y} (A_{i,j} \times b_j)\). That is, for rows from \(l\) to \(r\) and columns from \(x\) to \(y\), compute the product \(A_{i,j} \times b_j\) and output the maximum over all such pairs.

All formulas are given in \(\LaTeX\) format.

inputFormat

The first line contains three integers \(n\), \(m\) and \(q\) representing the number of rows, the number of columns of the matrix, and the number of operations respectively.

The second line contains \(m\) integers representing the sequence \(b\).

Each of the next \(q\) lines represents an operation in one of the following two formats:

• 1 l r x v: For row \(x\), set every element \(A_{x,i}\) for \(l \le i \le r\) to \(v\).
• 2 l r x y: Query and output \(\max_{i=l}^{r} \max_{j=x}^{y}(A_{i,j} \times b_j)\).

outputFormat

For each query operation (starting with a 2), output the result on a separate line.

sample

2 2 3
1 2
2 1 2 1 2
1 1 2 1 5
2 1 2 1 2

0
10