题目内容

流域调度中心要在一次夜间联调后，给出每个监测断面的最终浊度。值班员必须按稀释闸和回灌泵同时生效后的规则计算，并把整条河段的结果写入调度日志。

沿河依次有 $w$ 个监测断面，编号 $1 \sim w$，第 $i$ 个断面的初始浊度是整数 $v_i$。当晚有两类覆盖连续断面的调度指令会一起执行：

• 稀释闸：给定区间 $[L,R]$ 和上界 $c$，表示该区间内浊度不能超过 $c$。
• 回灌泵：给定区间 $[L,R]$ 和下界 $d$，表示该区间内浊度不能低于 $d$。

对每个断面 $i$，把覆盖它的所有回灌泵下界取最大值，记为 $lo_i$（没有回灌泵则 $lo_i=0$）；把覆盖它的所有稀释闸上界取最小值，记为 $hi_i$（没有稀释闸则 $hi_i=+\infty$）。最终浊度

请输出 $e_1,e_2,\dots,e_w$。

断面个数 $w$ 满足 $1 \le w \le$ 200000，稀释闸条数 $x$ 与回灌泵条数 $y$ 满足 $0 \le x,y \le$ 200000，初始浊度与指令中的上界、下界均满足 $0 \le v_i,c,d \le$ 1000000000。

输入描述

第一行三个整数 $w$、$x$、$y$（$1 \le w \le$ 200000，$0 \le x,y \le$ 200000），表示断面数、稀释闸数和回灌泵数。

第二行 $w$ 个整数 $v_1,v_2,\dots,v_w$（$0 \le v_i \le$ 1000000000），表示初始浊度。

接下来 $x$ 行，每行三个整数 $L$、$R$、$c$（$1 \le L \le R \le w$，$0 \le c \le$ 1000000000），表示一条稀释闸。

接下来 $y$ 行，每行三个整数 $L$、$R$、$d$（$1 \le L \le R \le w$，$0 \le d \le$ 1000000000），表示一条回灌泵。

输出描述

输出一行 $w$ 个整数，即各断面的最终浊度，相邻数之间用空格分隔。

样例1

输入

4 1 1
2 9 1 6
2 4 5
1 2 4

输出

4 5 1 5

说明

回灌泵覆盖 1 到 2，下界数组为 $lo=[4,4,0,0]$；稀释闸覆盖 2 到 4，上界数组为 $hi=[+\infty,5,5,5]$。

• $e_1=\min(\max(2,4),+\infty)=4$
• $e_2=\min(\max(9,4),5)=5$
• $e_3=\min(\max(1,0),5)=1$
• $e_4=\min(\max(6,0),5)=5$

样例2

输入

3 0 0
1 0 7

输出

1 0 7

说明

当晚没有调度指令，最终浊度就是初始浊度。

样例3

输入

3 1 1
5 5 5
1 3 2
1 3 8

输出

2 2 2

说明

三个断面都被下界 8 和上界 2 同时覆盖。先被抬到 8，再被上界压到 2，因此三个位置都是 2。