Robocity 有 $n$ 个十字路口，由双向道路连接。总共有 $m$ 条道路，且所有十字路口之间都是连通的。每个十字路口都被分配了一个从 $1$ 到 $k$ 的等级。任何由道路直接相连的两个十字路口等级都不同。

城市领导层正在计划进行改革。具体来说，他们希望为十字路口重新分配等级，使得每个等级仍然在 $1$ 到 $k$ 之间，相连的十字路口等级不同，并且必须满足一个附加条件：对于每一对十字路口 $u$ 和 $v$，它们之间必须存在一条路径，使得路径上任意两个相邻十字路口的等级之差模 $k$ 等于 $1$。

形式化地，对于每一对十字路口 $(u, v)$，都应该存在一个十字路口序列 $p_1, \dots, p_l$，满足： $p_1 = u$； $p_l = v$； * 对于每个 $i$ 从 $1$ 到 $l-1$，$p_i$ 和 $p_{i+1}$ 是相连的，且它们的等级之差为 $1$，或者其中一个等级为 $1$ 而另一个等级为 $k$。

Robocity 政府确信这样的等级分配方案是存在的，并请求你找到它。

输入格式

第一行包含三个整数 $n, m, k$ ($1 \le n, m, k \le 500\,000$)，分别表示十字路口、道路和等级的数量。

第二行包含 $n$ 个整数 $c_1, c_2, \dots, c_n$ ($1 \le c_i \le k$)，$c_i$ 是十字路口 $i$ 的等级。

接下来 $m$ 行，每行包含两个整数 $u, v$ ($1 \le u, v \le n; u \neq v$)，表示一对由道路连接的十字路口。

保证没有两条道路连接同一对十字路口，且任意一对十字路口之间都存在路径。

输出格式

输出 $n$ 个整数 $d_1, d_2, \dots, d_n$ ($1 \le d_i \le k$)，表示新分配方案中各十字路口的等级。

样例

输入 1

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

输出 1

4 3 2 1