有一个包含 $n$ 个顶点和 $m$ 条边的连通无向图。顶点编号从 $1$ 到 $n$。 在顶点 $i$ ($2 \le i \le n$) 处有无限多的珠宝，每件珠宝的价值为 $a_i$。Grammy 从顶点 $1$ 出发。经过每条边消耗 $1$ 个单位时间。她可以在顶点 $i$ 拾取一件珠宝，并将其放在顶点 $1$。拾取和放下珠宝的操作瞬间完成。此外，她任何时候最多只能携带 $1$ 件珠宝。当她在顶点 $1$ 放下一件价值为 $x$ 的珠宝时，她获得该价值。现在，对于每个 $k$ ($1 \le k \le T$)，她想知道在 $k$ 个单位时间内她能获得的最大价值。

输入格式

输入仅包含一组测试数据。 第一行包含三个整数 $n, m, T$ ($1 \le n, m, T \le 3\,000$)。 第二行包含 $n - 1$ 个整数 $a_2, a_3, \dots, a_n$ ($1 \le a_i \le 3\,000$)。 接下来的 $m$ 行描述 $m$ 条边。每行包含两个整数 $x_i$ 和 $y_i$ ($1 \le x_i, y_i \le n$)，表示顶点 $x_i$ 和 $y_i$ 之间的一条双向边。 注意：图中可能包含自环或重边。

输出格式

在一行中输出 $T$ 个整数，其中第 $k$ 个整数 ($1 \le k \le T$) 表示在 $k$ 个单位时间内她能获得的最大价值。

样例

输入 1

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

输出 1

0 3 3 6 6