403225: GYM101081 H Warsaw University

Warsaw University is one of the most traditional educational institutions in Europe, being almost 200 years old. People like Chopin (musician), Menachen Begin and Itzhak Shamir (prime ministers of Israel) and Leonid Hurwicz (mathematician who won the Nobel prize on Economics in 2007) studied there.

The university is proud to maintain its traditions. Since its foundation, the admission process remains the same. The university has M courses in all fields of knowledge, each of them offer a number of openings, and N candidates who must decide how many courses are of their interest. Furthermore, each candidate must rank the courses he wants, from the ones he wants the most and to the ones he desires the least. The courses that are not ranked by a candidate are not considered when assigning a course to this candidate, even if there are openings remaining.

A series of tests are given to each candidate (the same for everybody), and each one gets a score. This score will be used to decide which course a candidate goes to. The candidates are considered in decreasing order of their score and will be assigned the first course (using their preferences) that has spots left. Ties are broken using the preferences. If two candidates are tied, and both want the same course, but this course is in 3rd place in one list and in 10th place in the other list, the position is given to the one that wants it the most. In case the tie remains, the opening is given to the candidate that signed up first.

Your task is to write a program that makes the selection of the candidates to the Warsaw university.

The first line contains two integers N and M, the number of candidates and the number of courses, respectively. The courses are identified by the integers from 1 to M. The second line contains integers V₁, V₂, ..., V_M where V_i represents the number of openings in course i.

In the following N lines is given the information of the N candidates in the order they signed up. The ith line contains, in this order, an integer P_i indicating the score of candidate i and and integer Q_i indicating the number of courses he is interested in, followed by a list of Q_i space separated distinct integers, the list of courses given in the order of his preference (starting with the most wanted).

Limits

• 1 ≤ N, M ≤ 10³
• 1 ≤ V_i ≤ 10³
• 0 ≤ P_i ≤ 100
• 0 ≤ Q_i ≤ 10³
• Each number in the list is between 1 and M

Print N integers, the ith one is the course chosen for candidate i. If a candidate could not get a spot in any of the course he was interested, print  - 1.

4 2
5 2
87 1 2
89 2 2 1
88 2 2 1
40 2 1 2

-1
2
2
1

3 2
1 1
99 2 1 2
100 1 1
99 2 2 1

-1
1
2

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

1
2
2
3