Background

In the end, Renko managed to rescue Merry without major mishaps. Though Merry herself seemed unfazed and had many opinions about Renko's approach... they quickly reconciled and spent a sweet time together.

But you are neither Renko nor Merry. So at the story's conclusion, you must solve a data structure problem.

Problem Description

You need to maintain an $n \times m$ matrix $A$ where all elements are initially $0$. A sequence $b$ of length $m$ is also given.

There are $q$ operations of two types:

• 1 l r x v: For $l \le i \le r$, set $A_{x,i}$ to $v$.
• 2 l r x y: Query $\max\limits_{i=l}^r \max\limits_{j=x}^y (A_{i,j} \times b_j)$.

Input Format

• The first line contains three integers $n$, $m$, $q$.
• The second line contains $m$ integers describing sequence $b$.
• The next $q$ lines describe operations, each in the format 1 l r x v or 2 l r x y.

Output Format

For each 2 operation, output a single integer representing the query result.

5 5 20
3 2 1 1 1 
1 2 2 1 2
2 2 4 3 4
1 2 4 5 6
1 1 3 4 4
1 1 5 5 4
1 3 4 3 1
1 1 2 4 2
1 5 5 5 8
2 2 4 2 5
2 1 5 3 5
2 3 5 1 3
1 1 4 2 6
2 1 1 1 3
1 2 4 4 10
2 2 5 3 4
2 1 4 1 4
2 4 5 4 5
1 2 2 2 5
1 4 4 4 9
1 2 5 3 6

0
4
8
12
4
10
20
10

Hint

Constraints

Bundled testing is used.

$$\def\arraystretch{1.5} \begin{array}{|c|c|c|c|c|}\hline \textbf{Subtask} & \textbf{Points} & \bm{n,q \leq} & \textbf{Special Property} & \textbf{Subtask Dependencies} \cr\hline 1 & 5 & 100 & - & - \cr\hline 2 & 5 & 5000 & - & - \cr\hline 3 & 20 & 2 \times 10^5 & \mathbf{A} & - \cr\hline 4 & 10 & 2 \times 10^5 & \mathbf{B} & - \cr\hline 5 & 10 & 2 \times 10^5 & \mathbf{C} & - \cr\hline 6 & 10 & 2 \times 10^5 & \mathbf{D} & - \cr\hline 7 & 20 & 2 \times 10^5 & - & 1,2,3,4,5,6 \cr\hline 8 & 20 & 4 \times 10^5 & - & 7 \cr\hline \end{array}$$

Special Properties:

• A: All modifications occur before queries.
• B: For modify operations, $l = r$.
• C: Data is randomly generated (see details below).
• D: All $b_i = 1$.

For all data:

• $1 \leq n, m, q \leq 4 \times 10^5$.
• $1 \leq b_i \leq 10^9$.
• At most $\dfrac{q}{4}$ of the operations are modify operations.
• For modify operations: $1 \leq l \leq r \leq m$, $1 \leq x \leq n$, $1 \leq v \leq 10^9$.
• For query operations: $1 \leq l \leq r \leq n$, $1 \leq x \leq y \leq m$.

Data randomization method:

• $n$, $m$, and $q$ are predetermined (not random).
• Exactly $\left\lfloor \dfrac{q}{4} \right\rfloor$ operations are uniformly randomly selected as modify operations, with the rest as queries.
• All parameters for operations and the $b$ sequence are randomly sampled within their constraints with equal probability.

---

Translated by DeepSeek R1