Restaurants#10733

Restaurants

5 seconds

2,048 megabytes

Hard

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 $n$ customers, numbered from $1$ to $n$ , and $m$ restaurants, numbered from $1$ to $m$ . 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 $i$ also has a capacity $c_{i}$ c_i, 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 $r$ and customer $c$ having made a reservation for $r$ , such that:

$c$ has not been given a table or prefers $r$ to the restaurant he was given a table in, and
$r$ has some seats left or $r$ is full but prefers $c$ 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.

Input

The first line contains $n (1 \leq n \leq 50000)$ n~(1 \le n \le 50000) and $m (1 \leq m \leq 10000)$ m~(1 \le m \le 10000).

The $m$ following lines describe capacities with the $i$ -th line containing an integer $c_{i} (1 \leq c_{i} \leq n)$ c_i~(1 \le c_i \le n), the capacity of restaurant $i$ .

$n$ lines follow. The $i$ -th line describes the list of reservations for customer $i$ , sorted by preferences: the line contains a list of distinct integers (between $1$ and $m$ ), from most to least preferred.

$m$ lines follow. The $i$ -th line describes the sorted preferences of restaurant $i$ . This line contains either the number $0$ when no customer made a reservation to restaurant $i$ or it contains a list of distinct integers, the list of customers who made a reservation to restaurant $i$ ordered from most to least preferred by the restaurant.

The total number of reservation options is at most $1 0^{6}$ 10^6.

Output

Output the set of customers who have a table in one possible allocation (according to the rules above). The set is given with one customer per line, sorted ascending by $i d$ .

Examples

Example 1