Ресторани#10733

Ресторани

5 секунд

2 048 мегабайтів

Складна

Усі раді повернутися на вулиці та в ресторани Парижа. Проте наразі кількість місць у ресторанах дуже обмежена. Ми хочемо, щоб обидва ресторани могли прийняти якомога більше людей, і щоб клієнти займали бажані ними місця.

Є $n$ клієнтів з номерами від $1$ до $n$ і $m$ ресторанів з номерами від $1$ до $m$ . Кожен клієнт бронює столик у певному підмножині ресторанів і надає свій список бронювань, упорядкований за вподобаннями. Кожен ресторан ранжує отримані бронювання в певному порядку вподобань — наприклад, ресторан може бажати, щоб клієнти, які зареєструвалися першими, мали вищий рейтинг. Кожен ресторан $i$ також має місткість $c_{i}$ c_i, тобто максимальну кількість клієнтів, яку він може обслуговувати.

Ваше завдання — знайти такий розподіл частини відвідувачів у ресторанах, щоб виконувалися наступні умови:

1. Жоден ресторан не вміщує більше відвідувачів, ніж його місткість.

2. Кожному клієнту надається столик не більше ніж в одному ресторані.

3. Не існує ресторану $r$ і клієнта $c$ , який забронював столик у $r$ , такого, що:

$c$ не надали столик або він надає перевагу $r$ ресторану, в якому йому надали столик, і
в $r$ залишилося кілька місць або $r$ заповнений, але надає перевагу $c$ хоча б одному з призначених йому клієнтів.

Інші зауваження, на які слід звернути увагу:

Кожен клієнт зробив хоча б одне бронювання.
Ресторани ранжують лише клієнтів, які зробили у них бронь. Можливо, в ресторані немає клієнтів, які бажають забронювати столик.

Вхідні дані

Перший рядок містить числа $n (1 \leq n \leq 50000)$ n~(1 \le n \le 50000) і $m (1 \leq m \leq 10000)$ m~(1 \le m \le 10000).

Наступні $m$ рядків описують місткості, причому $i$ -й рядок містить ціле число $c_{i} (1 \leq c_{i} \leq n)$ c_i~(1 \le c_i \le n) — місткість ресторану $i$ .

Далі слідують $n$ рядків. $i$ -й рядок описує список резервувань для клієнта $i$ , відсортований за вподобаннями: рядок містить список різних цілих чисел (від $1$ до $m$ ), від найбільш вподобаних до найменш вподобаних.

Далі слідують $m$ рядків. $i$ -й рядок описує відсортовані вподобання ресторану $i$ . Цей рядок містить або число $0$ , коли жоден клієнт не забронював столик у ресторані $i$ , або список різних цілих чисел — список клієнтів, які зробили замовлення в ресторані $i$ , упорядкований від найбільш до найменш вподобаного рестораном.

Загальна кількість варіантів бронювання становить не більше $1 0^{6}$ 10^6.

Вихідні дані

Виведіть набір клієнтів, для яких є можливий розподіл (відповідно до наведених вище правил). Набір задається по одному клієнту в окремому рядку, відсортований за зростанням їх $i d$ .

Приклади

Приклад 1