该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

给定一个长度为 $n$ 的数组 $\{a_n\}$，再给定一个长度为 $m$ 的指令集 $t_m$。

对于任意一个指令 $t_i$ 有两个参数 $l_i,r_i$，表示将区间 $[l_i,r_i]$ 中的所有数修改为这个区间的最大值。

有 $q$ 次操作，操作为处理指令集中的指令或者对原数组进行修改，具体的操作有以下两种：

• 给定 $L, R, k$，求假设进行 $t_L, t_{L+1},\dots,t_{R}$ 这一段的指令之后，$a_k$ 应该是多少。
• 将 $a_u$ 的值修改为 $v$。

输入格式

在文件 data.in 中读入。

第一行三个整数 $n,m,q$，表示数组长度，指令集长度和询问数。

第二行 $n$ 个整数 $a_i$。

接下来 $m$ 行，每行两个整数 $l_i,r_i$ 表示一个指令 $t_i$。

接下来 $q$ 行，每行表示一次询问，格式如下：

• 1 u v，则我们将 $a_u$ 改成 $v$；
• 2 L R k，请输出假设进行 $t_L, t_{L+1},\dots,t_{R}$ 这一段的指令之后 $a_k$ 的值。

输出格式

在文件 data.out 中输出。

对于每个操作 $2$ 输出一行一个整数表示答案。

样例

样例输入 #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

数据范围

对于 $30\%$ 的数据，满足 $n,m,q \le 100$。

对于另外 $30\%$ 的数据，满足 $L = 1$。

对于另外 $30\%$ 的数据，满足没有操作 $1$。

对于 $100\%$ 的数据，满足 $n,m,q \le 10^5$，$1\le a_i,v \le 10^5$。