题目描述

Sample

有 $n$ 个小夫坐成一排，每个小夫有一个真实值 $v_i$。

小夫们有 $m$ 场聚会，第 $i$ 次聚会会在编号为 $[l_i, r_i]$ 的小夫中举办。聚会之后，这些小夫的真实值会变为他们之中真实值的最大值。

但是小夫们的真实值不是一成不变的，并且也不是每场聚会都会举办。将会发生 $q$ 次事件，有两类事件：

1. 第一类事件：第 $x$ 个小夫的真实值变成了 $y$。

2. 第二类事件：小夫们向你提问，假如第 $L$ 次聚会到第 $R$ 次聚会按顺序举办，第 $x$ 个小夫的真实值会变成多少。

输入格式

• 第一行包含两个整数 $n$ 和 $m$，表示小夫的数量和聚会的数量。
• 第二行包含 $n$ 个整数，第 $i$ 个整数 $v_i$ 表示第 $i$ 个小夫的真实值。
• 接下来 $m$ 行，每行包含两个整数 $l_i$ 和 $r_i$，表示第 $i$ 次聚会的小夫编号范围。
• 接下来一行包含一个整数 $q$，表示事件数量。
• 接下来 $q$ 行，每行首先包含一个整数 $op$，表示事件的种类。如果 $op = 1$，接下来两个整数 $x$ 和 $y$；否则接下来三个整数 $L$，$R$ 和 $x$，具体含义见题目描述。

输出格式

对于每个第二种事件，输出一行一个整数表示答案，具体含义见题目描述。

样例输入

4 4
1 2 4 3
1 2
2 3
1 3
1 4
4
2 2 3 4
2 1 1 2
1 2 8
2 1 2 4

样例输出

3
2
3

测试点约束

对于所有测试点：

• $n, m, q \leq 5 \times 10^5$
• $l_i \leq r_i \leq n$
• $x \leq n$
• $L \leq R$
• $op \in \\{1, 2\\}$
• $v_i, y \leq 10^9$

对于每个测试点的约束，$n$、$m$ 和 $q$ 的取值以及特殊限制如下：