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 ith-ranked contestant satisfies a specified ni of them (1≤ni ≤C).
The invitation process runs as follows. First, the top f1 students who satisfy the 1
st criteria will be invited. Then, out of all students who haven't yet been invited, the top f2 (or all remaining if there are fewer than f2 remaining) students who satisfy the 2nd criterion will be invited. This process repeats, for each i
from 1 to C (1≤fi≤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 p1,p2,…,pN of 1…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.
INPUT FORMAT (input arrives from the terminal / stdin):
The first line contains N and C (1≤N,C≤105).
The next line contains f1,f2,…,fC.
The next line contains p1…,pN.
The next N lines each contain ni (1≤ni≤C), followed by ni distinct integers in [1,C], representing the criteria that the i th-ranked contestant satisfies. It is guaranteed that ∑ni≤106.
OUTPUT FORMAT (print output to the terminal / stdout):
Output N lines, the sum of ranks of invitees before each declination.
SAMPLE INPUT:
5 1
3
5 1 3 2 4
1 1
1 1
1 1
1 1
1 1
SAMPLE OUTPUT:
6
6
9
6
4
There is only one criterion. The top three remaining contestants who have not declined will be invited.
SAMPLE INPUT:
5 4
1 1 1 1
1 2 3 4 5
1 1
2 1 2
2 2 3
2 3 4
1 4
SAMPLE OUTPUT:
10
14
12
9
5
Initially, the ith contestant gets invited under criterion i for all 1≤i≤4.
After the first declination, the i+1th contestant gets invited under criterion i for all 1≤i≤4.
SAMPLE INPUT:
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
SAMPLE OUTPUT:
21
20
16
10
5
3
SCORING:
Inputs 4-6: N,C≤103,∑ni≤104
Inputs 7-8: C=1
Inputs 9-10: C=2
Inputs 11-16: No additional constraints.
Problem credits: Benjamin Qi