Everybody is very happy to go back outside and to restaurants in Paris. However, for a while yet the restaurants have a very limited number of seats. We want to ensure that both restaurants can receive as many people as possible, and that customers go in their preferred seats.
We have customers, numbered from to , and restaurants, numbered from to . Each customer makes reservation in a subset of the restaurants, and give their list of reservations ordered by preference. Each restaurant ranks the reservations it received by some order of preference — for instance, the restaurant might wish customers who have signed up first to be ranked higher. Each restaurant also has a capacity , i.e. the maximal number of customers it can support.
Your task is to find an allocation of some of the customers in restaurants such that the following conditions are fulfilled:
1. No restaurant places more customers than their capacity.
2. Each customer is given a table in at most one restaurant.
3. There is no restaurant and customer having made a reservation for , such that:
has not been given a table or prefers to the restaurant he was given a table in, and
has some seats left or is full but prefers to at least one of the customers assigned to it.
Other remarks to note:
Every customer has made at least one reservation.
Restaurants only rank the customers having expressed a reservation for them. It is possible that a restaurant has no customers wishing to make a reservation.
The first line contains and .
The following lines describe capacities with the -th line containing an integer , the capacity of restaurant .
lines follow. The -th line describes the list of reservations for customer , sorted by preferences: the line contains a list of distinct integers (between and ), from most to least preferred.
lines follow. The -th line describes the sorted preferences of restaurant . This line contains either the number when no customer made a reservation to restaurant or it contains a list of distinct integers, the list of customers who made a reservation to restaurant ordered from most to least preferred by the restaurant.
The total number of reservation options is at most .
The output described the set of customers which have a table in one possible allocation (according to the rules above). The set is given with one customer per line, sorted ascending by .