题目
问题描述
小D写完了随机哈夫曼树，凭信仰开始补觉，想起了在ZJOI见过的一个模型：
给出一个长度为$n$的数组$a$，$1 \sim n$标号。
$m$个操作，每个操作有两个参数$l_i, r_i$，表示将区间$[l_i, r_i]$中的所有数修改为这个区间的最大值。
这个问题可以简单地用线段树来完成，现在小D将这个问题扩展了一下。
给出一个长度为$n$的初始数组$a$，以及$m$个操作，需要维护：
- 求依次进行编号为$[L, R]$的这一段操作后$a_k$的值。这些询问互相独立，即可以理解为“假如进行这一段操作后，$a_k$的值会变成多少”。
- 将$a_u$的值修改为$v$，即修改初始数组，这次修改会影响它之后的所有询问。
可以参考输入格式来帮助理解题意。
输入格式
从文件segment.in中读入数据。
第一行，三个正整数$n, m, q$，表示数组长度，操作数和询问数。
第二行，$n$个正整数$a_i$。
接下来$m$行，每行两个正整数$l_i, r_i$，描述一个操作。
接下来$q$行，每行描述一次询问或一次初始数组的修改，格式如下：
- $1\ u\ v$，将$a_u$的值修改为$v$。
- $2\ L\ R\ k$，询问假如进行编号为$[L, R]$的这一段操作后$a_k$的值。
输出格式
输出到文件segment.out中。
对于每次询问输出一行一个正整数，表示“假如进行编号为$[L, R]$的这一段操作后$a_k$的值”。
样例输入1
5 3 6
5 3 1 4 2
2 3
3 4
1 5
2 1 2 3
1 4 5
2 1 2 3
1 4 4
1 1 4
2 1 3 1
样例输出1
4
5
4
样例输入2
样例输出2
数据规模
对于$10\%$的数据，$n, m, q \leq 100$。
对于$30\%$的数据，$n, m, q \leq 10000$。
对于另$20\%$的数据，询问时$L = 1$。
对于$80\%$的数据，$n, m, q \leq 50000$（包含前一档$L = 1$）。
对于$100\%$的数据，$n, m, q \leq 10^5$，$1 \leq a_i, v \leq 10^5$。
题解
（稍后再补）
代码
（稍后再补）