题目背景

莲子最终有惊无险的救下了梅莉，虽然梅莉本人似乎对此不以为意，而且还对莲子的观点有很多看法……不过她们很快就和好如初，然后一起度过了一段甜蜜的时光。

但是你既不是莲子也不是梅莉，所以在故事的结尾，你需要做一道数据结构题。

题目描述

你需要维护一个大小为 $n \times m$ 的矩阵 $A$，初始时其所有元素均为 $0$。题目还给出了一个长度为 $m$ 的序列 $b$。

共有 $q$ 次操作，分为两种：

• 1 l r x v，对于 $l \le i \le r$，将 $A_{x,i}$ 修改为 $v$。

• 2 l r x y，查询 $\max\limits_{i=l}^r \max\limits_{j=x}^y (A_{i,j} \times b_j)$。

输入格式

第一行三个整数 $n,m,q$。

第二行 $m$ 个整数描述序列 $b$。

接下来 $q$ 行，每行描述一次操作，要么格式为 1 l r x v，要么格式为 2 l r x y。

输出格式

对于每次 2 操作，输出一行一个整数表示查询的结果。

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

提示

数据范围

本题采用捆绑测试。

$$\def\arraystretch{1.5} \begin{array}{|c|c|c|c|c|}\hline \textbf{Subtask} & \textbf{\textsf{分值}} & \bm{n,q\le } & \textbf{\textsf{特殊性质}}&\textbf{Subtask \textsf{依赖}}\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} $$

特殊性质 $\mathbf{A}$：保证所有修改在查询之前。
特殊性质 $\mathbf{B}$：对于修改操作保证 $l=r$。
特殊性质 $\mathbf{C}$：保证数据随机（随机方法见下）。
特殊性质 $\mathbf{D}$：保证 $b$ 序列满足所有 $b_i=1$。

对于所有数据满足：$1 \le n,m,q \le 4 \times 10^5$。$1 \le b_i \le 10^9$。

在所有 $q$ 次操作中，修改操作出现不超过 $\dfrac{q}{4}$ 次。

对于一操作，$1 \le l \le r \le m,1 \le x \le n,1 \le v \le 10^9$。

对于二操作，$1 \le l \le r \le n,1 \le x \le y \le m$。

数据随机的方式：$n,m,q$ 事先选定，不是随机的。然后均匀随机取 $\left \lfloor \dfrac{q}{4} \right \rfloor$ 次操作为修改操作，剩下的为查询操作。对于操作的所有参数以及 $b$ 序列在其限制范围内等概率随机。