题目描述

$N$ contestants participated in a contest, each placing a distinct rank from $1$ to $N$. There are $C$ criteria used to invite contestants to participate in the final round, and the $i$th-ranked contestant satisfies a specified $n_i$ of them ($1\le n_i\le C$).

The invitation process runs as follows. First, the top $f_1$ students who satisfy the $1$st criteria will be invited. Then, out of all students who haven't yet been invited, the top $f_2$ (or all remaining if there are fewer than $f_2$ remaining) students who satisfy the $2$nd criterion will be invited. This process repeats, for each $i$ from $1$ to $C$ ($1\le f_i\le N$).

However, some contestants will decline to participate in the final round, in which case they will be ignored when determining who to invite.

You are given a permutation $p_1, p_2, \dots, p_N$ of $1\dots N$. For each $i$ from $0$ to $N-1$, determine the sum of the ranks of the contestants who will be invited if the participants with ranks given by the first $i$ elements of $p$ decline to attend.

输入格式

The first line contains $N$ and $C$ ($1\le N,C\le 10^5$).

The next line contains $f_1,f_2, \dots, f_C$.

The next line contains $p_1, \dots, p_N$.

The next $N$ lines each contain $n_i$ ($1\le n_i\le C$), followed by $n_i$ distinct integers in $[1, C]$, representing the criteria that the $i$th-ranked contestant satisfies. It is guaranteed that $\sum n_i\le 10^6$.

输出格式

Output $N$ lines, the sum of ranks of invitees before each declination.

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

6
6
9
6
4

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

10
14
12
9
5

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

21
20
16
10
5
3

提示

Sample 1 Explanation

There is only one criterion. The top three remaining contestants who have not declined will be invited.

Sample 2 Explanation

Initially, the $i$th contestant gets invited under criterion $i$ for all $1\le i\le 4$.

After the first declination, the $i+1$th contestant gets invited under criterion $i$ for all $1\le i\le 4$.

SCORING:

• Inputs 4-6: $N, C \le 10^3, \sum n_i \le 10^4$
• Inputs 7-8: $C=1$
• Inputs 9-10: $C=2$
• Inputs 11-16: No additional constraints.