题目描述

给定一个长度为 $n$ 的数组 $a$，再给定一个长度为 $m$ 的指令集。

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

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

1. 1 u v：将 $a_u$ 的值修改为 $v$。
2. 2 L R k：求假设依次执行指令 $t_L,t_{L+1},\dots,t_R$ 之后，位置 $k$ 的值是多少。（注意：这只是假想执行，不会真正修改数组和指令集）

输入格式

第一行三个整数 $n,m,q$，表示数组长度，指令集长度，询问数。 第二行 $n$ 个整数 $a_i$。 接下来 $m$ 行，每行两个整数 $l_i,r_i$，表示指令 $t_i$。 接下来 $q$ 行，每行一次操作：

• 1 u v：单点修改
• 2 L R k：假想执行 $L\sim R$ 的指令，查询位置 $k$ 的结果。

输出格式

对于每个类型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

数据范围

• 部分数据：$n,m,q \le 100$
• 部分数据：所有询问满足 $L=1$
• 部分数据：没有操作1（没有单点修改）
• 100%数据：$n,m,q \le 10^5,\ 1\le a_i,v \le 10^5$。