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

样例文件

题目描述

Farmer John 的 N 头奶牛排成一排，从前往后进行编号，第 i 头奶牛的编号为 $R_i$。奶牛的编号两两不同，且均为不超过 N 的正整数。

现在要选拔其中的若干头奶牛参加合唱比赛。

选拔条件共有 T 个，比如身高、体重、力量、音色等等，这些条件被依次编号为 1 ~ T。

经过评定，得知编号为 $r$ 的奶牛符合其中的 $M_r$ 个选拔条件：$X_1, X_2, …, X_{M_r}$，其中 $1 ≤ X_j ≤ T (1 ≤ j ≤ M_r)$ 且 $X_j$ 两两不同。

选拔过程将按以下 T 个步骤进行：

第一步：所有满足条件 1 的奶牛按编号从小到大排序，编号最小的前 $K_1$ 头奶牛被选中（如果满足条件的奶牛不足 $K_1$ 头，则全部被选中）；

第二步：所有满足条件 2 且在之前未被选中的奶牛按编号从小到大排序，编号最小的前 $K_2$ 头奶牛被选中（如果满足条件的奶牛不足 $K_2$ 头，则全部被选中）；

……

第 T 步：所有满足条件 T 且在之前未被选中的奶牛按编号从小到大排序，编号最小的前 $K_T$ 头奶牛被选中（如果满足条件的奶牛不足 $K_T$ 头，则全部被选中）。

不过，在选拔过程中，有些奶牛可能会放弃参赛，那么这些奶牛将不会被选中，其他满足条件的奶牛会进行递补。

现在需要你求的是，对于每一个 t ( 0 ≤ t < N )，如果前 t 头奶牛均放弃参加比赛，最终被选中参加比赛的所有奶牛的编号之和是多少？注意：这里的前 t 头不是指编号前 t 头，而是指原队伍中的前 t 头。

输入格式

第一行：两个整数 $N, T$

第二行：$T$ 个整数 $K_1,K_2, …, K_T$。

第三行：$N$ 个整数 $R_1, …, R_N$。

接下来的 $N$ 行：第 $r$ 行描述编号为 $r$ 的奶牛满足的条件——首先是一个整数 $M_r$（$1 ≤ M_r ≤ T$），接着是 $M_r$ 个两两不同的整数 $X_1, X_2, …, X_{M_r}$。数据保证 $\sum M_r ≤ 10^6$。

输出格式

共 $N$ 行，每行一个整数，依次表示 t = 0, 1, ……, N-1 时的答案。

输入样例1

3 1
2
1 2 3
1 1
1 1
1 1

输出样例1

3
5
3

样例1解释

t=0：没有奶牛放弃参赛

满足条件 1 的编号前 2 小的奶牛为 1,2, 则 1+2=3.

t=1：前 1 头奶牛放弃参赛，其编号为 1

满足条件 1 的编号前 2 小的奶牛为 2,3, 则 2+3=5.

t=2：前 2 头奶牛放弃参赛，其编号为 1, 2

满足条件 1 的编号前 2 小的奶牛只剩余一头，编号为 3.

输入样例2

3 2
2 1
1 3 2
1 2
1 1
2 2 1

输出样例2

6
5
2

样例2解释

t=0：没有奶牛放弃参赛

满足条件 1 的编号前 2 小的奶牛为 2,3, 则 2+3=5.

满足条件 2 的编号前 1 小的奶牛为 1

则输出 5+1=6.

t=1：前 1 头奶牛放弃参赛，其编号为 1

满足条件 1 的编号前 2 小的奶牛为 2,3, 则 2+3=5.

满足条件 2 且未被选中的奶牛已经没有了

则输出 5

t=2：前 2 头奶牛放弃参赛，其编号为 1, 3

满足条件 1 的编号前 2 小的奶牛只剩余一头，编号为 2

满足条件 2 且未被选中的奶牛已经没有了

则输出 2

数据范围

100% 的数据：$1 ≤ N, T ≤ 10^5$, $\sum M_r ≤ 10^6$. 其中

• 20% 的数据：$N, T ≤ 10^3$, $\sum M_r ≤ 10^4$
• 10% 的数据：$T=1$
• 10% 的数据：$T=2$