第 41 届彼得罗扎沃茨克训练营即将结束。我们希望你度过了愉快的一周。我们很可能会在即将于一个月后举行的 ICPC 2020 全球总决赛上见到你们中的一些人，而这段时间有不同的度过策略。一种选择是刻苦训练并解决更多问题。另一种相反的选择是清空思绪，在所有这些工作之后好好休息一下。

你可能已经注意到，这次训练营是在线举办的。COVID-19 改变了我们现在的生活方式，也极大地限制了旅行的可能性。

假设有 $n$ 个国家（为了方便起见，编号从 $1$ 到 $n$），它们之间有 $m$ 条双向航班。每个国家 $i$ 都有三个属性：壮观度值 $s_i$、COVID 水平 $c_i$ 和安全阈值 $t_i \ge c_i$。它们的含义如下：如果一个人想要飞往第 $j$ 个国家，且他们曾经去过第 $i$ 个国家，则必须满足 $c_i \le t_j$。

假设一个来自第 $i$ 个国家的人想要访问其他国家，他们的目标是去往最壮观的地方——也就是说，最终访问一个具有最大可能 $s_j$ 的国家 $j$。请为每个起始国家 $i$ 找出这个壮观度值。

注意，始终可以选择待在家里，因此答案总是存在的。为了简单起见，我们不要求在访问了最壮观的国家后必须能够返回家中（假设即使没有航班，你也可以以某种方式回家）。

输入格式

第一行包含两个由空格分隔的整数 $n$ 和 $m$ ($1 \le n, m \le 2 \cdot 10^5$)。接下来 $n$ 行，第 $i$ 行包含三个由空格分隔的整数 $c_i, t_i$ 和 $s_i$ ($1 \le c_i, t_i, s_i \le 10^9, c_i \le t_i$)。

接下来的 $m$ 行描述边，每行包含两个整数 $u$ 和 $v$ ($1 \le u, v \le n$)，表示 $u$ 和 $v$ 之间的一条航班。保证所描述的图中没有自环和重边。

输出格式

输出 $n$ 个整数，其中第 $i$ 个整数表示从第 $i$ 个国家出发所能见到的最大壮观度。

样例

输入 1

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

输出 1

2 4 2 3