A - Find the Regulars Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 266 点

問題文

高橋君はある図書館の司書です。最近、図書館の利用状況を分析するため、D 日間にわたって来館者の記録を取ることにしました。

この図書館の利用登録者は N 人おり、それぞれ 1 から N までの利用者番号が付いています。高橋君は D 日間の各日について、その日に来館した利用者の番号を記録しました。j 日目 (1 \leq j \leq D) に来館した利用者は M_j 人であり、その利用者番号は S_{j,1}, S_{j,2}, \ldots, S_{j,M_j} です。なお、同じ日に同じ利用者が複数回記録されることはありません。また、各日の来館記録内で利用者番号は特定の順序で並んでいるとは限りません。

高橋君は、D 日間のうち来館した日数が K 日以上である利用者を「常連利用者」と定義し、常連利用者の一覧を作成したいと考えています。ここで、ある利用者の来館した日数とは、その利用者の番号が来館記録に含まれている日の数を指します。

D 日間の来館記録が与えられるので、常連利用者と判定される利用者の番号を昇順にすべて出力してください。常連利用者が 1 人もいない場合は -1 を出力してください。

制約

  • 1 \leq N \leq 100
  • 1 \leq D \leq 100
  • 1 \leq K \leq D
  • 0 \leq M_j \leq N (1 \leq j \leq D)
  • 1 \leq S_{j,i} \leq N (1 \leq j \leq D, \; 1 \leq i \leq M_j)
  • 同じ日の記録内に同じ利用者番号が複数回現れることはない
  • 入力はすべて整数である

入力

N D K
M_1 S_{1,1} S_{1,2} \ldots S_{1,M_1}
M_2 S_{2,1} S_{2,2} \ldots S_{2,M_2}
\vdots
M_D S_{D,1} S_{D,2} \ldots S_{D,M_D}
  • 1 行目には、利用登録者の人数 N、記録日数 D、常連利用者と判定する基準日数 K が、スペース区切りで与えられる。
  • 2 行目から第 (D+1) 行目までの D 行にわたって、各日の来館記録が与えられる。
  • 第 (j+1) 行目 (1 \leq j \leq D) では、j 日目に来館した利用者の人数 M_j と、その利用者の番号 S_{j,1}, S_{j,2}, \ldots, S_{j,M_j} がスペース区切りで与えられる。M_j = 0 の場合は、0 のみが与えられる。

出力

常連利用者と判定された利用者が 1 人以上いる場合は、その利用者の番号を昇順にスペース区切りで 1 行で出力してください。常連利用者が 1 人もいない場合は -1 を 1 行で出力してください。

入力例 1

5 3 2
3 1 2 3
3 2 3 4
2 3 5

出力例 1

2 3

入力例 2

4 3 3
2 1 2
2 3 4
2 1 3

出力例 2

-1

入力例 3

10 5 3
5 1 2 3 4 5
5 2 4 6 8 10
5 1 2 3 6 7
4 2 4 6 8
5 1 3 5 7 9

出力例 3

1 2 3 4 6

入力例 4

15 7 3
8 1 3 5 7 9 11 13 15
7 2 4 6 8 10 12 14
7 1 2 3 4 5 6 7
8 8 9 10 11 12 13 14 15
5 1 4 7 10 13
5 2 5 8 11 14
5 3 6 9 12 15

出力例 4

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

入力例 5

1 1 1
0

出力例 5

-1

Score : 266 pts

Problem Statement

Takahashi is a librarian at a certain library. Recently, he decided to record visitor data over D days in order to analyze the library's usage.

The library has N registered users, each assigned a user ID from 1 to N. For each of the D days, Takahashi recorded the user IDs of the visitors who came that day. On day j (1 \leq j \leq D), there were M_j visitors, and their user IDs are S_{j,1}, S_{j,2}, \ldots, S_{j,M_j}. Note that the same user is never recorded multiple times on the same day. Also, the user IDs within each day's record are not necessarily in any particular order.

Takahashi defines a "regular user" as a user who visited the library on at least K of the D days, and he wants to compile a list of all regular users. Here, the number of days a user visited is the number of days on which that user's ID appears in the visitor records.

Given the visitor records for D days, output all user IDs that are identified as regular users in ascending order. If there are no regular users, output -1.

Constraints

  • 1 \leq N \leq 100
  • 1 \leq D \leq 100
  • 1 \leq K \leq D
  • 0 \leq M_j \leq N (1 \leq j \leq D)
  • 1 \leq S_{j,i} \leq N (1 \leq j \leq D, \; 1 \leq i \leq M_j)
  • The same user ID does not appear multiple times within the same day's record
  • All input values are integers

Input

N D K
M_1 S_{1,1} S_{1,2} \ldots S_{1,M_1}
M_2 S_{2,1} S_{2,2} \ldots S_{2,M_2}
\vdots
M_D S_{D,1} S_{D,2} \ldots S_{D,M_D}
  • The first line contains the number of registered users N, the number of recorded days D, and the threshold number of days K for determining regular users, separated by spaces.
  • The following D lines (from line 2 to line (D+1)) contain the visitor records for each day.
  • Line (j+1) (1 \leq j \leq D) contains the number of visitors on day j, M_j, followed by their user IDs S_{j,1}, S_{j,2}, \ldots, S_{j,M_j}, separated by spaces. If M_j = 0, only 0 is given.

Output

If there is at least one regular user, output their user IDs in ascending order, separated by spaces, on a single line. If there are no regular users, output -1 on a single line.

Sample Input 1

5 3 2
3 1 2 3
3 2 3 4
2 3 5

Sample Output 1

2 3

Sample Input 2

4 3 3
2 1 2
2 3 4
2 1 3

Sample Output 2

-1

Sample Input 3

10 5 3
5 1 2 3 4 5
5 2 4 6 8 10
5 1 2 3 6 7
4 2 4 6 8
5 1 3 5 7 9

Sample Output 3

1 2 3 4 6

Sample Input 4

15 7 3
8 1 3 5 7 9 11 13 15
7 2 4 6 8 10 12 14
7 1 2 3 4 5 6 7
8 8 9 10 11 12 13 14 15
5 1 4 7 10 13
5 2 5 8 11 14
5 3 6 9 12 15

Sample Output 4

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

Sample Input 5

1 1 1
0

Sample Output 5

-1