B - 奨学金の選考 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 266 点

問題文

高橋君は大学の奨学金選考委員会の担当者です。今年度は N 種類の奨学金があり、それぞれについて応募した学生の中から受給者を決定する必要があります。

大学には M 人の応募者がおり、応募者 j (1 \leq j \leq M) には成績に基づいた評価点 P_j が設定されています。評価点は応募者ごとに固定の値であり、値が大きいほど高評価であることを意味します。異なる応募者の評価点が同じ値であることもあり得ます。

一人の応募者が複数の奨学金に応募することもあり得ます。各奨学金の受給者はそれぞれ独立に決定されるため、一人の応募者が複数の奨学金を受給することもあり得ます。

各奨学金 i (1 \leq i \leq N) には、その奨学金に応募した K_i 人の応募者の番号 C_{i,1}, C_{i,2}, \ldots, C_{i,K_i} が与えられます。受給者は以下のルールで決まります：

  • 応募者がいない場合（K_i = 0）、その奨学金の受給者はいない。
  • 応募者がいる場合、評価点が最も高い応募者がその奨学金を受給する。評価点が最も高い応募者が複数いる場合は、その中で応募者番号が最も小さい応募者が受給する。

各奨学金について、最終的にその奨学金を受給する応募者の番号を求めてください。受給者がいない場合は 0 を出力してください。

制約

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq M \leq 2 \times 10^5
  • 1 \leq P_j \leq 10^9 (1 \leq j \leq M)
  • 0 \leq K_i \leq M (1 \leq i \leq N)
  • 1 \leq C_{i,k} \leq M (1 \leq i \leq N, 1 \leq k \leq K_i)
  • 同じ奨学金に対して同じ応募者が複数回現れることはない（C_{i,1}, C_{i,2}, \ldots, C_{i,K_i} は相異なる）
  • \displaystyle \sum_{i=1}^{N} K_i \leq 2 \times 10^5
  • 入力はすべて整数

入力

N M
P_1 P_2 \ldots P_M
K_1 C_{1,1} C_{1,2} \ldots C_{1,K_1}
K_2 C_{2,1} C_{2,2} \ldots C_{2,K_2}
\vdots
K_N C_{N,1} C_{N,2} \ldots C_{N,K_N}
  • 1 行目には、奨学金の種類数を表す整数 N と、応募者の人数を表す整数 M が、スペース区切りで与えられる。
  • 2 行目には、各応募者の評価点を表す整数 P_1, P_2, \ldots, P_M が、スペース区切りで与えられる。P_j は応募者 j の評価点を表す。
  • 2 + i 行目 (1 \leq i \leq N) には、奨学金 i に応募した学生の情報が与えられる。まず応募した学生の人数を表す整数 K_i が与えられ、続いてその応募者の番号を表す整数 C_{i,1}, C_{i,2}, \ldots, C_{i,K_i} がスペース区切りで与えられる。K_i = 0 の場合、その行には K_i のみが与えられる。

出力

N 行出力せよ。i 行目 (1 \leq i \leq N) には、奨学金 i を受給する応募者の番号を出力せよ。受給者がいない場合は 0 を出力せよ。

入力例 1

3 4
100 80 100 90
2 1 2
3 2 3 4
0

出力例 1

1
3
0

入力例 2

5 6
50 50 50 30 70 70
3 1 2 3
2 5 6
4 1 4 5 6
1 4
0

出力例 2

1
5
5
4
0

入力例 3

8 10
1000000000 999999999 500000000 750000000 1000000000 250000000 750000000 100000000 999999999 500000000
5 1 2 3 4 5
3 6 7 8
4 2 5 9 10
0
2 1 5
6 1 2 3 4 5 6
1 8
10 1 2 3 4 5 6 7 8 9 10

出力例 3

1
7
5
0
1
1
8
1

Score : 266 pts

Problem Statement

Takahashi is a member of the university's scholarship selection committee. This year, there are N types of scholarships, and for each one, a recipient must be determined from among the students who applied.

The university has M applicants, and applicant j (1 \leq j \leq M) has been assigned an evaluation score P_j based on their academic performance. The evaluation score is a fixed value for each applicant, and a higher value means a higher evaluation. It is possible for different applicants to have the same evaluation score.

A single applicant may apply for multiple scholarships. Since the recipient of each scholarship is determined independently, a single applicant may receive multiple scholarships.

For each scholarship i (1 \leq i \leq N), the applicant numbers C_{i,1}, C_{i,2}, \ldots, C_{i,K_i} of the K_i applicants who applied for that scholarship are given. The recipient is determined by the following rules:

  • If there are no applicants (K_i = 0), there is no recipient for that scholarship.
  • If there are applicants, the applicant with the highest evaluation score receives the scholarship. If there are multiple applicants with the highest evaluation score, the one with the smallest applicant number among them receives it.

For each scholarship, determine the applicant number of the person who ultimately receives that scholarship. If there is no recipient, output 0.

Constraints

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq M \leq 2 \times 10^5
  • 1 \leq P_j \leq 10^9 (1 \leq j \leq M)
  • 0 \leq K_i \leq M (1 \leq i \leq N)
  • 1 \leq C_{i,k} \leq M (1 \leq i \leq N, 1 \leq k \leq K_i)
  • The same applicant does not appear multiple times for the same scholarship (C_{i,1}, C_{i,2}, \ldots, C_{i,K_i} are distinct)
  • \displaystyle \sum_{i=1}^{N} K_i \leq 2 \times 10^5
  • All input values are integers

Input

N M
P_1 P_2 \ldots P_M
K_1 C_{1,1} C_{1,2} \ldots C_{1,K_1}
K_2 C_{2,1} C_{2,2} \ldots C_{2,K_2}
\vdots
K_N C_{N,1} C_{N,2} \ldots C_{N,K_N}
  • The first line contains an integer N representing the number of types of scholarships and an integer M representing the number of applicants, separated by a space.
  • The second line contains integers P_1, P_2, \ldots, P_M representing the evaluation scores of each applicant, separated by spaces. P_j represents the evaluation score of applicant j.
  • The (2 + i)-th line (1 \leq i \leq N) contains information about the students who applied for scholarship i. First, an integer K_i representing the number of applicants is given, followed by the integers C_{i,1}, C_{i,2}, \ldots, C_{i,K_i} representing the applicant numbers, separated by spaces. If K_i = 0, only K_i is given on that line.

Output

Output N lines. The i-th line (1 \leq i \leq N) should contain the applicant number of the person who receives scholarship i. If there is no recipient, output 0.

Sample Input 1

3 4
100 80 100 90
2 1 2
3 2 3 4
0

Sample Output 1

1
3
0

Sample Input 2

5 6
50 50 50 30 70 70
3 1 2 3
2 5 6
4 1 4 5 6
1 4
0

Sample Output 2

1
5
5
4
0

Sample Input 3

8 10
1000000000 999999999 500000000 750000000 1000000000 250000000 750000000 100000000 999999999 500000000
5 1 2 3 4 5
3 6 7 8
4 2 5 9 10
0
2 1 5
6 1 2 3 4 5 6
1 8
10 1 2 3 4 5 6 7 8 9 10

Sample Output 3

1
7
5
0
1
1
8
1