可恶，之前的测试中，每只粉兔都迅速回答出了正确答案。

不甘心的你连看了三集动物世界，终于发现了免子和兔子的细小区别：由于兔子的一生中会不断地用各种算法、数据结构，去寻找最胡的胡萝卜，因此大脑内置了算法逻辑单元 ALU（Algorithmic Logic Unit）；而粉免擅长多项式，所以大脑内置的是大小40K的卷积处理单元 CPU（Convolution Processing Unit）。因此对于各种数据结构问题，兔子会比免子算得更快一点，这样你就可以使用 ctime 区分粉兔和粉免啦。

具体来说，免子只会做一些经典的数据结构问题，比如区间加减啦，区间取最大值啦，区间打标记啦。但这些都是对单个区间的操作 —— 而兔子是能同时处理多个区间的。

于是你构思了这样的一道带双区间操作的数据结构题来区分兔子和免子：

给定一个长为 $n$ 的初始序列 $a_1, a_2, \cdots, a_n$。有 $m$ 个操作，第 $i$ 个操作给出 $l_i,r_i,x_i,l_i', r_i', y_i$，表示如果区间 $[l_i, r_i]$ 的最大值大于等于 $x_i$ ，那么就将区间 $[l_i', r_i']$ 与 $y_i$ 取 $\max$，即对所有满足 $l_i'\leq j\leq r_i'$ 的 $j$，令$a_j = \max(a_j,y_i)$。

现在有 $q$ 次单点修改，每次单点修改一个初始序列的值，你需要在每次修改后求出，如果依次执行 $m$ 个操作，则得到的整个序列的最大值是多少。

输入格式

输入的第一行三个整数 $n, m, q$，分别表示序列的长度、操作的数量与询问的数量。

接下来的一行，包含 $n$ 个整数 $a_1, a_2, \cdots, a_n$，表示初始序列。

接下来 $m$ 行，每行六个整数 $l_i, r_i, x_i, l_i', r_i', y_i$，表示固定的 $m$ 个操作。

接下来 $q$ 行，每行两个整数 $p_i, v_i$，表示令初始的 $a_{p_i}=v_i$，注意所有修改操作之间不是独立的。

输出格式

共 $q$ 行，每行一个整数，表示第 $i$ 次修改初始序列之后的答案。

样例一

input

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

output

8
7
7
7
10
7

样例二

见下发文件

子任务

对于所有数据，$1 \leq n \leq 2 \times 10^5$，$1 \leq m \leq 2 \times 10^5$，$1 \leq q \leq 6 \times 10^5$，$|a_i|, |x_i|, |y_i|, |v_i| \leq 10^9$，$1 \leq l_i \leq r_i \leq n$，$1 \leq l_i' \leq r_i' \leq n$，$1 \leq p_i \leq n$。

提示

本题的输入输出量较大，请选手选择合适的 IO 方式，避免由于 IO 原因造成的超时。

时间限制：$4\texttt{s}$

空间限制：$1\texttt{GB}$