Maximum Merit Move

問題文

長さ $N$ の正整数列 $S=(S_1,S_2,\ldots,S_N)$ と、$N$ 頂点 $M$ 辺の単純連結無向グラフが与えられます。 頂点には $1$ から $N$ までの番号が付いています。

このグラフ上で、頂点 $x$ から頂点 $y$ へ $K$ 回で移動する方法とは、長さ $K+1$ の整数列 $A=(A_0,A_1,\ldots,A_K)$ が次の条件を全て満たすことを指します。

• $A_0=x$
• $A_K=y$
• $0 \leq i < K$ を満たすすべての整数 $i$ について、頂点 $A_i$ と頂点 $A_{i+1}$ は辺で結ばれている
• $0 \leq i < K-1$ を満たすすべての整数 $i$ について、$A_i \neq A_{i+2}$

最後の条件は、$1$ 回前にいた頂点へ直ちに戻ることができないことを意味します。

このような列 $A$ 全体の集合を $\mathcal{A}_{x,y,K}$ とします。

頂点 $x$ から頂点 $y$ へ $K$ 回で移動する方法の最大スコアを、$\mathcal{A}_{x,y,K}$ を用いて、

と定めます。ただし、$\mathcal{A}_{x,y,K}$ が空集合である場合、最大スコアは $0$ とします。

各頂点 $X=1,2,\ldots,N$ に対して、頂点 $1$ から頂点 $X$ へちょうど $T$ 回で移動する方法の最大スコアを $P_X$ としたとき、長さ $N$ の整数列 $P=(P_1,P_2,...,P_N)$ を出力してください。

なお、与えられるグラフには必ず $1$ つ以上のサイクルが含まれることが保証されます。

制約

• $3 \leq N \leq 5 \times 10^3$
• $N \leq M \leq 2 \times 10^4$
• $1 \leq T \leq 150$
• $-10^9 \leq S_i \leq 10^9$
• $1 \leq u_i < v_i \leq N$
• 与えられるグラフは単純連結無向グラフ
• 入力はすべて整数

入力

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

出力

求めた整数列 $P$ の各要素を、空白で区切って$1$行で出力してください。

入力例 1

5 6 3
1 2 3 4 5
1 2
1 3
1 5
2 3
2 4
3 4

出力例 1

6 9 9 9 0

頂点 $1$ から頂点 $1$ へ $3$ 回で移動する方法は $1 \to 2 \to 3 \to 1$ と、$1 \to 3 \to 2 \to 1$ の $2$ つであり、得られる最大スコアは $2+3+1=6$ です。

また、頂点 $1$ から頂点 $5$ へ $3$ 回で移動する方法はありません。この場合、最大スコアは $0$ です。

入力例２

3 3 1
-1 -10 -100
1 2
1 3
2 3

出力例２

0 -10 -100

最大スコアが負になる場合もあります。