该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

在之前，我们知道徐老师已经尝试给一道图论题进行了数据构造

现在他已经构造出了一个包含 $n$ 个点的有向图，其中每个点的权值为 $a_i$

并且其中包含 $m$ 条有向边 $(u_i,v_i)$，表示存在一条有向边从 $u_i$ 出发连向 $v_i$，并且徐老师为了偷懒，在生成数据时保证了 $u_i < v_i$

现在题目是这样的，枚举 $k = 1 \sim n$

对于每个 $k$ 询问：在图中选出 $k$ 个点，保证存在一条 简单路径 能够经过这 $k$ 个点（路径上可以经过其他点），请问能选出的这 $k$ 个点的最大权值和为多少？

若对于有的 $k$ 无法满足选出 $k$ 个点，则答案为 $0$

输入格式

输入第一行包含两个整数 $n,m$，表示这个图有 $n$ 个点 $m$ 条边

输入第二行包含 $n$ 个整数 $a_i$，表示每个点的权值

接下去 $m$ 行，每行包含两个整数 $u_i,v_i$ 表示存在一条有向边从 $u_i$ 连向 $v_i$

输出格式

输出一行包含 $n$ 个整数，分别表示 $k=1 \sim n$ 时的答案

数据范围

对于所有数据，满足 $1\le n\le 5\times 10^3$，$0\le m\le 5\times 10^3$，$1\le a_i\le 10^5$，$1\le u_i < v_i\le n$。

保证图中无重边、自环。

样例输入1

3 3
1 3 5
1 2
2 3
1 3

样例输出1

5 8 9

样例解释1

$k=1$：选择点 $3$，路径 $3$ 包含 $3$，答案为 $5$。

$k=2$：选择点 $2,3$，路径 $1\to 2\to 3$ 同时包含 $2,3$，答案为 $3+5=8$。

$k=3$：选择点 $1,2,3$，路径 $1\to 2\to 3$ 同时包含 $1,2,3$，答案为 $1+3+5=9$。

样例输入2

10 9
8 2 9 7 4 6 7 9 7 4
1 2
1 3
3 4
4 5
5 6
5 7
7 8
6 9
9 10

样例输出2

9 18 26 33 40 44 45 0 0 0