有 $n$ 条龙，编号从 $1$ 到 $n$。第 $i$ 条龙的年龄为 $a_i$。所有 $a_i$ 的值两两不同。第 $1$ 条龙是龙 Evirir。

Evirir 有一封它想寄给第 $t$ 条龙的信。为了避免因年龄差距造成的尴尬，Evirir 可以先把信寄给另一条龙（不一定是第 $t$ 条龙）。收到信的龙随后又可以把信寄给另一条龙，如此继续。目标是最终把信寄到第 $t$ 条龙手中。

对于所有 $i$（$1 \le i \le n$），当第 $i$ 条龙持有这封信时，它可以在 $|a_i - a_j|$ 的时间内把信寄给第 $j$ 条龙。龙也可以把信“寄”给自己，耗时为 $0$。不过，有 $k$ 对龙是亲密朋友。如果第 $i$ 条龙和第 $j$ 条龙是亲密朋友，那么第 $i$ 条龙把信寄给第 $j$ 条龙（以及反过来）所需时间改为 $0$。

对于每一条龙 $t$（$1 \le t \le n$），独立回答下列问题：第 $1$ 条龙把信寄到第 $t$ 条龙手中所需的最小总时间是多少？

$^1$注：$|x|$ 表示 $x$ 的绝对值。例如，$|9| = 9$，$\lvert -6 \rvert = 6$，以及 $|0| = 0$。更多信息可参见 https://en.wikipedia.org/wiki/Absolute_value 。

输入格式

第一行包含两个用空格分隔的整数 $n$ 和 $k$（$1 \le n \le 2 \cdot 10^5$，$0 \le k \le 2 \cdot 10^5$）——龙的数量以及亲密朋友对数。

第二行包含 $n$ 个两两不同的用空格分隔的整数 $a_1, a_2, \ldots, a_n$（$1 \le a_i \le 10^9$）——各条龙的年龄。

接下来有 $k$ 行。每行包含两个用空格分隔的整数 $u$ 和 $v$（$1 \le u, v \le n$，$u \ne v$），表示第 $u$ 条龙和第 $v$ 条龙是亲密朋友。保证同一对亲密朋友不会出现两次（如果 $(u, v)$ 出现过，那么之后不会再出现 $(u, v)$ 或 $(v, u)$）。

输出格式

输出 $n$ 个用空格分隔的整数 $d_1, d_2, \ldots, d_n$，其中 $d_i$ 表示第 $1$ 条龙把信寄给第 $i$ 条龙所需的最小总时间。

子任务

子任务 1（$18$ 分）：$n, k \le 2000$，$a_i = i$

子任务 2（$14$ 分）：$n, k \le 2000$

子任务 3（$9$ 分）：$k = 0$

子任务 4（$29$ 分）：对所有 $i$（$1 \le i \le n$），都有 $a_i = i$

子任务 5（$16$ 分）：序列 $a$ 单调不减，即对 $1 \le i \le n - 1$，有 $a_i \le a_{i+1}$

子任务 6（$14$ 分）：无额外限制

样例数据

输入样例 1

8 4
50 30 23 10 3 67 69 47
3 7
3 1
2 4
7 1

输出样例 1

0 7 0 7 14 2 0 3

输入样例 2

3 0
2 3 1

输出样例 2

0 1 1

说明

第一个样例的解释：

当 $t = 1$ 时，耗时为 $0$，因为第 $1$ 条龙本来就已经持有这封信。

当 $t = 3$ 时，由于第 $1$ 条龙和第 $3$ 条龙是亲密朋友，第 $1$ 条龙可以直接在 $0$ 时间内把信寄给第 $3$ 条龙。

当 $t = 2$ 时，第 $1$ 条龙可以先在 $0$ 时间内把信寄给第 $3$ 条龙（它们是亲密朋友），然后第 $3$ 条龙在 $|23 - 30| = 7$ 的时间内把信寄给第 $2$ 条龙。总耗时为 $0 + 7 = 7$。

当 $t = 8$ 时，第 $1$ 条龙可以直接把信寄给第 $8$ 条龙，耗时为 $|50 - 47| = 3$。

对于剩余的各个 $t$，下面分别给出一种最优方案（$i \xrightarrow{x} j$ 表示第 $i$ 条龙花费 $x$ 时间把信寄给第 $j$ 条龙）：

• 第 $4$ 条龙：$1 \xrightarrow{0} 3 \xrightarrow{7} 2 \xrightarrow{0} 4$
• 第 $5$ 条龙：$1 \xrightarrow{0} 3 \xrightarrow{7} 2 \xrightarrow{0} 4 \xrightarrow{7} 5$
• 第 $6$ 条龙：$1 \xrightarrow{0} 3 \xrightarrow{0} 7 \xrightarrow{2} 6$
• 第 $7$ 条龙：$1 \xrightarrow{0} 7$