矩阵上的操作

题目描述

我们有一个 $N \times M$ 的矩阵，所有元素初始都为 0。

处理给定的 $Q$ 个查询。每个查询是以下格式之一。

• 1 l r x：给第 $l$、$(l+1)$、$\ldots$、$r$ 列的每个元素加上 $x$。
• 2 i x：将第 $i$ 行的所有元素替换为 $x$。
• 3 i j：打印第 $(i, j)$ 个元素。

输入格式

输入按以下格式从标准输入给出：

N M Q
Query_1
⋮
Query_Q

第 $i$ 个查询 $\mathrm{Query}_i$ 是以下格式之一：

1 l r x

2 i x

3 i j

输出格式

对于每个格式 3 i j 的查询，单独打印一行答案。

样例

3 3 9
1 1 2 1
3 2 2
2 3 2
3 3 3
3 3 1
1 2 3 3
3 3 2
3 2 3
3 1 2

1
2
2
5
3
4

矩阵变化过程如下。

$\begin{pmatrix} 0 & 0 & 0 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \\ \end{pmatrix} \rightarrow \begin{pmatrix} 1 & 1 & 0 \\ 1 & 1 & 0 \\ 1 & 1 & 0 \\ \end{pmatrix} \rightarrow \begin{pmatrix} 1 & 1 & 0 \\ 1 & 1 & 0 \\ 2 & 2 & 2 \\ \end{pmatrix} \rightarrow \begin{pmatrix} 1 & 4 & 3 \\ 1 & 4 & 3 \\ 2 & 5 & 5 \\ \end{pmatrix}$

1 1 10
1 1 1 1000000000
1 1 1 1000000000
1 1 1 1000000000
1 1 1 1000000000
1 1 1 1000000000
1 1 1 1000000000
1 1 1 1000000000
1 1 1 1000000000
1 1 1 1000000000
3 1 1

9000000000

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

6
5
5
13
10
0

数据范围

• $1 \le N, M, Q \le 2 \times 10^5$
• 每个查询都是题目描述中列出的格式之一。
• 对于格式 1 l r x 的每个查询，$1 \le l \le r \le M$ 且 $1 \le x \le 10^9$。
• 对于格式 2 i x 的每个查询，$1 \le i \le N$ 且 $1 \le x \le 10^9$。
• 对于格式 3 i j 的每个查询，$1 \le i \le N$ 且 $1 \le j \le M$。
• 至少给出一个格式 3 i j 的查询。
• 输入中的所有值均为整数。