题目描述

给定一个长度为 $n$ 的数列，初始时数列中的所有数字均为 $0$。

接下来有 $m$ 次操作。

每次操作表示为三个整数 $l_i, r_i, h_i$，它表示将数列的第 $l_i$ 个数到第 $r_i$ 个数范围内（包含第 $l_i$ 和第 $r_i$ 个数）所有数字都和 $h_i$ 取较大值。即：

对于任意 $l_i \le p \le r_i$，$a_p \leftarrow \max\{ a_p, h_i \}$

你需要输出经过 $m$ 次操作后，数列中的每个元素的数值。

输入格式

第一行，两个整数 $n$ 和 $m$（$1 \le n,m \le 5 \cdot 10^5$）。

接下来 $m$ 行，每行包含三个整数 $l_i, r_i, h_i$，表示一次操作（$1 \le l_i \le r_i \le n, 1 \le h_i \le 10^9$）。

输出格式

输出共一行，包含 $n$ 个整数，两两之间以一个空格分隔，表示最终的每个数字。

样例输入

6 3
1 4 2
2 6 1
2 4 7

样例输出

2 7 7 7 1 1

说明/提示

数据规模与约定

• 对于 $30\%$ 的数据，$n,m \le 50; h_i \le 1000$
• 对于 $60\%$ 的数据，$n,m \le 5000; h_i \le 10^6$
• 对于 $100\%$ 的数据，$n,m \le 5 \cdot 10^5; h_i \le 10^9$