Declining Invitations
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 1st 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.
There is only one criterion. The top three remaining contestants who have not declined will be invited.
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.
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
Source: USA Computing Olympiad.
Input Format
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 ith-ranked contestant satisfies. It is guaranteed that ∑ni≤106.
Output Format
Output N lines, the sum of ranks of invitees before each declination.