在 JOI 王国中，有 $N$ 个岛屿，编号为 $1$ 到 $N$。每个岛屿都有一个不安全等级。岛屿 $i$ ($1 \le i \le N$) 的不安全等级为 $S_i$。

在 JOI 王国中，岛屿之间的船只运输是主要的交通方式。共有 $M$ 艘船，编号为 $1$ 到 $M$。船只 $j$ ($1 \le j \le M$) 连接岛屿 $A_j$ 和岛屿 $B_j$。我们可以在必要时运行这些船只。通过乘坐若干艘船，可以从任意岛屿到达其他任何岛屿。

在 JOI 王国中，有一个引入新船只的计划。我们可以选择任意一对岛屿作为新船只的连接点。

一天，发生了一起事故。一艘停泊的船只遭到了袭击。JOI 王国的首相 K 决定引入新船只。他还要求 JOI 王国的船只必须满足以下安全条件：

• 当一艘船停泊在岛屿 $i$ ($1 \le i \le N$) 时，船上的保安人数必须大于或等于 $S_i$。

然而，由于雇佣保安的费用昂贵，我们希望最小化雇佣的保安总数。只要满足“可以通过乘坐若干艘船从任意岛屿到达其他任何岛屿”这一条件，就可以废弃当前正在运行的船只。

因此，我们将按如下方式运行船只。此处，$k$ 是新引入船只的数量。

1. 对于 $k$ 艘新引入的船只中的每一艘，我们选择它所连接的两个岛屿。
2. 我们选择若干（大于或等于 $0$）艘船，并将它们废弃。允许废弃新引入的船只。
3. 对于每一艘船，我们将其停泊在它所连接的两个岛屿之一。我们让一定数量的保安上船。此外，必须满足以下条件。

条件：对于每一对岛屿 $u, v$ ($1 \le u \le N, 1 \le v \le N$)，可以通过重复以下操作若干次，将乘客从岛屿 $u$ 运输到岛屿 $v$。在此过程中，必须始终满足安全条件。

• 让乘客或保安登上停泊在乘客或保安所在岛屿的船只。
• 让乘客或保安在船只当前停泊的岛屿下船。
• 将船只从当前停泊的岛屿移动到该船连接的另一个岛屿。

由于预算有限，我们最多可以引入 $Q$ 艘新船。对于每个 $k$ ($0 \le k \le Q$)，首相 K 想知道如果新引入的船只数量为 $k$，雇佣保安的最小可能总数。

编写一个程序，在给定岛屿信息、船只航线以及我们可以引入的新船只数量的情况下，计算每个 $k$ 对应的最小雇佣保安总数。

输入格式

从标准输入读取以下数据：

$N \ M \ Q$ $S_1 \ S_2 \ \dots \ S_N$ $A_1 \ B_1$ $A_2 \ B_2$ $\vdots$ $A_M \ B_M$

输出格式

向标准输出写入 $Q+1$ 行。第 $(k+1)$ 行（$0 \le k \le Q$）应包含新引入船只数量为 $k$ 时，雇佣保安的最小可能总数。

数据范围

• $2 \le N \le 200\,000$
• $N - 1 \le M \le 400\,000$
• $0 \le Q \le 200\,000$
• $1 \le S_i \le 10^9$ ($1 \le i \le N$)
• $1 \le A_j < B_j \le N$ ($1 \le j \le M$)
• $(A_x, B_x) \neq (A_y, B_y)$ ($1 \le x < y \le M$)
• 可以通过乘坐若干艘船从任意岛屿到达其他任何岛屿。
• 给定值均为整数。

子任务

1. (12 分) $M = N - 1, Q = 0, S_i \le 2$ ($1 \le i \le N$), $A_j = j, B_j = j + 1$ ($1 \le j \le M$)。
2. (13 分) $M = N - 1, Q = 0, A_j = j, B_j = j + 1$ ($1 \le j \le M$)。
3. (12 分) $M = N - 1, Q = 0$。
4. (13 分) $Q = 0$。
5. (8 分) $N \le 16$。
6. (18 分) $N \le 3\,000$。
7. (24 分) 无附加限制。

样例

样例输入 1

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

样例输出 1

7

样例输入 2

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

样例输出 2

7
5

样例输入 3

3 3 0
1 1 1
1 2
1 3
2 3

样例输出 3

2

样例输入 4

8 7 0
2 2 2 2 2 2 2 2
1 2
2 3
3 4
4 5
5 6
6 7
7 8

样例输出 4

14

样例输入 5

8 7 0
16 39 36 23 15 48 23 56
1 2
1 3
2 4
2 5
3 6
3 7
7 8

样例输出 5

245

样例输入 6

10 13 4
314 159 265 358 979 323 846 264 338 327
1 2
1 4
2 3
2 5
3 6
4 5
4 7
5 6
5 8
6 9
7 8
8 9
9 10

样例输出 6

3139
2901
2722
2567
2461