Cârnați 的意思是香肠，所以这里没有太多需要解释的。根据地区和家庭传统的不同，在罗马尼亚，我们有许多不同种类的 Cârnați，它们在肉类类型、制作方法、大小、产地等方面各不相同。所有这些加起来有 100 多种，所以你可以想象选择你最喜欢的一种有多么困难。

圣诞节就要到了，cârnați 正在路上！你的 ogradă（罗马尼亚语，意为后院）可以表示为一个由 $n$ 个顶点和 $m$ 条边组成的有向图，里面装满了长长的 cârnați。

每个顶点 $i$ 都有一根长度为 $\ell_i$ 的 cârnat。将每个顶点作为起点，你想找出沿着边的方向所能到达的最长的 cârnat 的长度。

输入格式

输入的第一行包含两个整数 $n$ 和 $m$（$2 \le n \le 10^5$，$1 \le m \le 2 \cdot 10^5$）。

第二行包含 $n$ 个整数 $\ell_1, \ell_2, \dots, \ell_n$：cârnați 的长度（$1 \le \ell_i \le 10^9$）。

接下来的 $m$ 行，每行包含两个整数 $a$ 和 $b$，表示存在一条从顶点 $a$ 到顶点 $b$ 的有向边（$1 \le a, b \le n$，$a \ne b$）。图中没有重边。

输出格式

输出一行，包含 $n$ 个整数：分别表示从顶点 $1, 2, \dots, n$ 出发，所能到达的最长 cârnat 的长度。

样例

输入样例 1

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

输出样例 1

7 4 5 5 4

说明

在给定的样例中，从顶点 1 出发，你能到达的最长 Cârnat 是位于该顶点自身的、长度为 7 的 Cârnat。从顶点 5 出发，你可以到达顶点 2，该顶点包含一个长度为 4 的 Cârnat。