题目描述

当夜，韩魏二军暗中决开水坝，大水倒灌智伯大营。智伯梦中惊醒，未及整军，便被乱军所杀。这场大战杀得天昏地暗。

话说那智伯大营原分作若干营区，每区各有旗色，以示方位。忽被大水一冲，韩、魏、赵三军又轮番更替旗号，营区颜色屡屡更变。待到战事终了，众军士欲知各营最终所树何旗，遂记录如下：

初始状态下，有一排 $n$ 个营区，其中第 $i$ 个营区所悬挂的旗帜颜色为 $a_i$。

接下来有 $q$ 次军令，每次军令给到三个整数 $l, r, v$，表示你要将第 $l$ 个营区到第 $r$ 个营区的颜色全部变成 $v$。

现在问你，$q$ 次军令结束后，每个营区的颜色各变成什么？

输入格式

第一行两个整数 $n, q(1 \le n, q \le 10^4)$。

第二行 $n$ 个整数 $a_1 \sim a_n(1 \le a_i \le n)$。

接下来 $q$ 行，每行三个整数 $l, r, v(1 \le l \le r \le n, 1 \le v \le n)$。

输出格式

一行 $n$ 个整数，其中第 $i$ 个整数表示最后第 $i$ 个营区的颜色，整数之间用一个空格隔开。

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

4 2 5 2 1

额外挑战

数据范围增大：$n, q(1 \le n, q \le 10^5)$。