题目描述

徐老师最近开了一个新的信息学竞赛班，准备做最后的赛前冲刺！

这个班里一共有 $n$ 个同学，每个同学的实力可以量化成一个数字 $a_i$

现在徐老师将会组织 $m$ 场模拟赛，第 $i$ 场模拟赛会让编号为 $l_i$ 到 $r_i$ 的学生参加，强度为 $s_i$

这里我们可以认为，如果一个学生现在的实力为 $a_x$ ，他参加了第 $i$ 场模拟赛

他的实力将提升到 $s_i$，当然，如果这名学生的实力原本就高于模拟赛难度，那么他的实力将不发生变化（刷水题当然不会有提升）

现在徐老师想知道，在打完 $m$ 场模拟赛以后，每位同学的实力分别为多少？

输入格式

输入第一行包含两个整数 $n,m$ 表示同学人数和模拟赛数量

第二行 $n$ 个整数 $a_i$ 表示每个同学一开始的实力

接下来 $m$ 行，每行包含三个整数 $l_i,r_i,s_i$，含义如题

输出格式

输出共 $n$ 行，分别表示每个学生的最终实力

数据范围

对于 $30\%$ 的数据：$n,m \leq 2 \times 10^3$。

对于 $100\%$ 的数据：$1\leq n,m\leq2\times10^5$，$1\leq a_i,s_j \leq10^9$，$1\leq l_j\leq l_j\leq n$。

样例输入

5 2
1 2 3 4 5
1 4 3
3 5 6

样例输出

3
3
6
6
6