B - Greedy Draft 解説 /

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

配点 : 200 点

問題文

N 人の客がおり、1 から N までの番号が付けられています。また、M 本の缶ジュースがあり、1 から M までの番号が付けられています。

客 i (1 \leq i \leq N) は長さ L_i の希望リストを持っています。客 i の希望リストの先頭から j 番目 (1 \leq j \leq L_i) は缶ジュース X_{i,j} です。任意の客 i に対して、客 i の希望リストに載っている番号 X_{i, 1}, \dots, X_{i, L_i} は相異なります。

これから客 1, \dots, N が番号の小さいほうから順に、以下にしたがって自分が飲む飲料を選びます。

  • その時点で誰にも選ばれていない缶ジュースの番号が自分の希望リストに存在する場合、そのうち先頭に最も近い番号の缶ジュースを選ぶ。そうでない場合は水を選ぶ。

それぞれの客がどの飲料を得るかを求めてください。

制約

  • 1 \leq N \leq 100
  • 1 \leq M \leq 100
  • 1 \leq L_i \leq M (1 \leq i \leq N)
  • 1 \leq X_{i,j} \leq M (1 \leq i \leq N, 1 \leq j \leq L_i)
  • X_{i, 1}, \dots, X_{i, L_i} は相異なる (1 \leq i \leq N)
  • 入力される値はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

N M
L_1
X_{1,1} X_{1,2} \cdots X_{1,L_1}
L_2
X_{2,1} X_{2,2} \cdots X_{2,L_2}
\vdots
L_N
X_{N,1} X_{N,2} \cdots X_{N,L_N}

出力

N 行出力せよ。i 行目 (1 \leq i \leq N) には、客 i が缶ジュースを得る場合はその番号を、水を得る場合は 0 を出力せよ。

入力例 1

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

出力例 1

3
2
0
5

客 1 の希望リストにある番号のうち、対応する缶ジュースが誰にも選ばれていないのは 3,1,2 です。このうち先頭に最も近いのは 3 なので、客 1 は缶ジュース 3 を選びます。

客 2 の希望リストにある番号のうち、対応する缶ジュースが誰にも選ばれていないのは 2,1 です。このうち先頭に最も近いのは 2 なので、客 2 は缶ジュース 2 を選びます。

客 3 の希望リストにある番号について、対応する缶ジュースはすべてその時点で誰かに選ばれています。よって客 3 は水を選びます。

客 4 の希望リストにある番号のうち、対応する缶ジュースが誰にも選ばれていないのは 5,1 です。このうち先頭に最も近いのは 5 なので、客 4 は缶ジュース 5 を選びます。

入力例 2

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

出力例 2

3
5
1
4
2
0

Score : 200 points

Problem Statement

There are N customers numbered 1 to N, and M canned juices numbered 1 to M.

Customer i (1 \leq i \leq N) has a wish list of length L_i. The j-th item (1 \leq j \leq L_i) from the top of customer i's wish list is canned juice X_{i,j}. For any customer i, the numbers X_{i, 1}, \dots, X_{i, L_i} on customer i's wish list are distinct.

Customers 1, \dots, N, in this order, will now choose their beverages, following the procedure below.

  • If the customer's wish list contains a canned juice that has not yet been chosen by anyone at that point, they choose the canned juice whose number appears earliest in their wish list. Otherwise, they choose water.

Determine which beverage each customer gets.

Constraints

  • 1 \leq N \leq 100
  • 1 \leq M \leq 100
  • 1 \leq L_i \leq M (1 \leq i \leq N)
  • 1 \leq X_{i,j} \leq M (1 \leq i \leq N, 1 \leq j \leq L_i)
  • X_{i, 1}, \dots, X_{i, L_i} are distinct. (1 \leq i \leq N)
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

N M
L_1
X_{1,1} X_{1,2} \cdots X_{1,L_1}
L_2
X_{2,1} X_{2,2} \cdots X_{2,L_2}
\vdots
L_N
X_{N,1} X_{N,2} \cdots X_{N,L_N}

Output

Output N lines. The i-th line (1 \leq i \leq N) should contain the number of the canned juice customer i gets if they get one, or 0 if customer i gets water.

Sample Input 1

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

Sample Output 1

3
2
0
5

Among the numbers on customer 1's wish list, the canned juices not yet chosen by anyone are 3, 1, 2. The one appearing earliest in the list is 3, so customer 1 chooses canned juice 3.

Among the numbers on customer 2's wish list, the canned juices not yet chosen by anyone are 2, 1. The one appearing earliest in the list is 2, so customer 2 chooses canned juice 2.

For the numbers on customer 3's wish list, all corresponding canned juices have already been chosen by someone at that point. Thus, customer 3 chooses water.

Among the numbers on customer 4's wish list, the canned juices not yet chosen by anyone are 5, 1. The one appearing earliest in the list is 5, so customer 4 chooses canned juice 5.

Sample Input 2

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

Sample Output 2

3
5
1
4
2
0