Có \(N\) thí sinh tham gia một cuộc thi, mỗi người có một thứ hạng khác nhau từ \(1\) đến \(N\). Có \(C\) tiêu chí được dùng để mời thí sinh tham dự vòng chung kết, và thí sinh xếp hạng \(i\) thỏa mãn một số lượng \(n_i\) tiêu chí đã cho (\(1\le n_i\le C\)).

Quá trình mời diễn ra như sau. Đầu tiên, \(f_1\) thí sinh có thứ hạng cao nhất trong số những người thỏa mãn tiêu chí thứ \(1\) sẽ được mời. Sau đó, trong số tất cả thí sinh chưa được mời, \(f_2\) người có thứ hạng cao nhất thỏa mãn tiêu chí thứ \(2\) sẽ được mời (hoặc mời tất cả những người còn lại nếu có ít hơn \(f_2\) người). Quá trình này được lặp lại với từng \(i\) từ \(1\) đến \(C\) (\(1\le f_i\le N\)).

Tuy nhiên, một số thí sinh sẽ từ chối tham dự vòng chung kết; khi đó, họ sẽ bị bỏ qua trong lúc xác định những người được mời.

Bạn được cho một hoán vị \(p_1,p_2,\dots,p_N\) của \(1\dots N\). Với mỗi \(i\) từ \(0\) đến \(N-1\), hãy xác định tổng thứ hạng của các thí sinh sẽ được mời nếu những thí sinh có thứ hạng là \(i\) phần tử đầu tiên của \(p\) từ chối tham dự.

Dữ liệu vào

Dòng đầu tiên chứa \(N\) và \(C\) (\(1\le N,C\le 10^5\)).

Dòng tiếp theo chứa \(f_1,f_2,\dots,f_C\).

Dòng tiếp theo chứa \(p_1,\dots,p_N\).

\(N\) dòng tiếp theo, dòng thứ \(i\) chứa \(n_i\) (\(1\le n_i\le C\)), sau đó là \(n_i\) số nguyên phân biệt thuộc \([1,C]\), biểu diễn các tiêu chí mà thí sinh xếp hạng \(i\) thỏa mãn. Đảm bảo \(\sum n_i\le 10^6\).

Dữ liệu ra

In ra \(N\) dòng, mỗi dòng là tổng thứ hạng của những người được mời trước mỗi lần từ chối.

Ví dụ

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

Phân nhóm

• 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: Không có ràng buộc bổ sung.

Nguồn

USACO 2026 Contest 2, Silver — Declining Invitations. Tác giả: Benjamin Qi.

https://usaco.org/index.php?page=viewproblem2&cpid=1567