Все очень рады вернуться на улицу и в рестораны Парижа. Однако пока что в ресторанах очень ограниченное количество мест. Мы хотим, чтобы оба ресторана могли принять как можно больше людей и чтобы клиенты занимали предпочитаемые ими места.
Имеются n клиентов с номерами от 1 до n и m ресторанов с номерами от 1 до m. Каждый клиент бронирует столик в определенном подмножестве ресторанов и предоставляет свой список бронирований, упорядоченный по предпочтениям. Каждый ресторан ранжирует полученные бронирования в определенном порядке предпочтения — например, ресторан может желать, чтобы клиенты, которые зарегистрировались первыми, имели более высокий рейтинг. Каждый ресторан i также имеет вместимость ci, то есть максимальное количество клиентов, которое он может обслужить.
Ваша задача — найти такое распределение части посетителей в ресторанах, чтобы выполнялись следующие условия:
1. Ни один ресторан не вмещает больше посетителей, чем его вместимость.
2. Каждому клиенту предоставляется столик не более чем в одном ресторане.
3. Не существует ресторана r и клиента c, забронировавшего столик в r, такого, что:
c не предоставили столик или он предпочитает r ресторану, в котором ему предоставили столик, и
в r осталось несколько мест или r заполнен, но предпочитает c хотя бы одному из назначенных ему клиентов.
Другие замечания, на которые следует обратить внимание:
Каждый клиент сделал хотя бы одно бронирование.
Рестораны ранжируют только клиентов, сделавших у них бронь. Возможно, в ресторане нет клиентов, желающих забронировать столик.
Первая строка содержит числа n (1≤n≤50000) и m (1≤m≤10000).
Следующие m строк описывают вместимости, причем i-я строка содержит целое число ci (1≤ci≤n) — вместимость ресторана i.
Далее следуют n строк. i-я строка описывает список резервирований для клиента i, отсортированный по предпочтениям: строка содержит список различных целых чисел (от 1 до m), от наиболее предпочтительных до наименее предпочтительных.
Далее следуют m строк. i-я строка описывает отсортированные предпочтения ресторана i. Эта строка содержит либо число 0, когда ни один клиент не забронировал столик в ресторане i, либо список различных целых чисел — список клиентов, сделавших заказ в ресторане i, упорядоченный от наиболее к наименее предпочитаемому рестораном. .
Общее количество вариантов бронирования составляет не более 106.
Выведите набор клиентов, для которых имеется возможное распределение (в соответствии с приведенными выше правилами). Набор задается по одному клиенту в отдельной строке, отсортирован по возрастанию их id.