頂点に $1$ から $N$ の番号がついた $N$ 頂点 $M$ 辺の単純無向グラフがあり、$i$ 番目の辺は頂点 $u_i$ と頂点 $v_i$ を結んでいます。また、頂点 $i$ $(1 \leq i \leq N)$ にははじめ整数 $A_i$ が書かれており、正整数 $K_i$ が定められています。
あなたは以下の操作を好きな回数（$0$ 回でもよい）行うことができます。

• $1 \leq i \leq N$ を満たす整数 $i$ を一つ選ぶ。頂点 $i$ に書き込まれた整数を、頂点 $i$ に隣接する頂点に書き込まれた整数のうち $K_i$ 番目に大きいものに書き換える。ここで、頂点 $i$ に隣接する頂点の個数は $K_i$ 以上であることが保証される。

各 $i$ $(1 \leq i \leq N)$ について、操作を好きな回数行った後の頂点 $i$ に書き込まれた整数の最大値を求めてください。

• 入力は全て整数
• $1 \leq N, M \leq 2 \times 10^5$
• $1 \leq u_i, v_i \leq N$
• 与えられるグラフは単純
• $1 \leq A_i \leq 10^9$
• $1 \leq K_i$
• $K_i$ は頂点 $i$ に隣接する頂点の個数以下

入力は以下の形式で標準入力から与えられる。

$N\ M$
$u_1\ v_1$
$u_2\ v_2$
$\vdots$
$u_M\ v_M$
$A_1\ A_2\ \ldots\ A_N$
$K_1\ K_2\ \ldots\ K_N$

$N$ 行出力せよ。$i$ 行目には操作を好きな回数行った後の頂点 $i$ に書き込まれた整数の最大値を出力せよ。