题目描述

有 $N$ 名选手参加比赛，每名选手的排名均为 $1$ 到 $N$ 之间的一个不同整数。共有 $C$ 个准则用于邀请选手参加决赛，排名第 $i$ 的选手满足其中指定的 $n_i$ 个准则（$1\le n_i\le C$）。

邀请过程如下：首先，邀请满足第 $1$ 个准则的前 $f_1$ 名选手。然后，在所有尚未被邀请的选手中，邀请满足第 $2$ 个准则的前 $f_2$ 名选手（若不足 $f_2$ 名，则邀请所有剩余满足该准则的选手）。该过程对每个 $i$ 从 $1$ 到 $C$ 重复进行（$1\le f_i\le N$）。

然而，一些选手会拒绝参加决赛，在这种情况下，在确定邀请名单时将忽略这些选手。

给定一个 $1 \dots N$ 的排列 $p_1, p_2, \dots, p_N$。对于每个 $i$ 从 $0$ 到 $N-1$，求出当排名为 $p$ 中前 $i$ 个元素的选手拒绝参加时，被邀请选手的排名之和。

输入格式

第一行包含 $N$ 和 $C$（$1\le N,C\le 10^5$）。

第二行包含 $f_1,f_2, \dots, f_C$。

第三行包含 $p_1, \dots, p_N$。

接下来的 $N$ 行，每行包含 $n_i$（$1\le n_i\le C$），随后是 $n_i$ 个 $[1, C]$ 范围内的不同整数，表示排名第 $i$ 的选手满足的准则。保证 $\sum n_i\le 10^6$。

输出格式

输出 $N$ 行，每行表示在每次拒绝发生前被邀请选手的排名之和。

样例

输入 1

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

输出 1

6
6
9
6
4

说明 1

只有一个准则。邀请尚未拒绝的前三名选手。

输入 2

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

输出 2

10
14
12
9
5

说明 2

最初，对于所有 $1\le i\le 4$，排名第 $i$ 的选手在准则 $i$ 下被邀请。

第一次拒绝后，对于所有 $1\le i\le 4$，排名第 $i+1$ 的选手在准则 $i$ 下被邀请。

输入 3

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

输出 3

21
20
16
10
5
3

子任务

• 输入 4-6：$N, C \le 10^3, \sum n_i \le 10^4$
• 输入 7-8：$C=1$
• 输入 9-10：$C=2$
• 输入 11-16：无额外限制。

题目来源：Benjamin Qi