题目描述

你是一名前端程序员。有一天，同事提出了这样一个问题。

有一张 $n$ 个点、$m$ 条边的简单无向图，每个点都有一个正整数权值。现在按照给定顺序，依次删除这 $n$ 个点。删除一个点时，与它相连的边也会一起删除。初始图不一定连通。

定义一个连通块的权值为其中所有点的权值之和。请在每次删除一个点后，求剩余图中所有连通块权值的最大值。如果已经没有剩余点，则答案为 $0$。

输入格式

从文件 qd.in 中读入数据。

第一行包含两个正整数 $n,m$。

第二行包含 $n$ 个正整数 $a_1,a_2,\ldots,a_n$，表示各点的权值。

接下来 $m$ 行，每行包含两个正整数 $u,v$，表示点 $u$ 与点 $v$ 之间有一条无向边。保证图中没有自环和重边。

最后一行包含一个 $1\sim n$ 的排列 $p_1,p_2,\ldots,p_n$，表示删除点的顺序。

输出格式

输出到文件 qd.out 中。

输出 $n$ 行，每行一个整数。第 $i$ 行表示删除 $p_1,p_2,\ldots,p_i$ 后的答案。

样例1

样例输入1

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

样例输出1

9 
8 
4 
2 
1 
0

样例说明

删除点 $4$ 后，点 $3,5,6$ 构成的连通块权值为 $9$，是所有连通块中的最大值。继续删除点 $5$ 后，点 $3,6$ 仍然连通，答案为 $8$。最后一个点被删除后，答案为 $0$。

样例 2

见选手目录下的 qd/qd2.in 与 qd/qd2.ans。

该组样例满足 $n,m\le1000$。

样例 3

见选手目录下的 qd/qd3.in 与 qd/qd3.ans。

该组样例满足特殊性质 A。

数据范围

对于所有测试点，$1\le n,m,a_i\le10^5$，$1\le u,v\le n$。输入的图是简单无向图，删除顺序是 $1\sim n$ 的排列。

本题共有 $20$ 个测试点，每个测试点 $5$ 分，按测试点独立计分。

测试点编号	$n,m$ 的上界	特殊性质
$1\sim6$	$1000$	无
$7\sim10$	$10^5$	特殊性质 A
$11\sim20$		无

特殊性质 A：所有 $a_i=1$。