P10611 The End of the Story

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.

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)$.

- 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`.

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

### 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