说明

:::align{center}

:::

所有人都很高兴能够重新外出并去巴黎的餐厅用餐。然而，在一段时间内，餐厅的座位数量非常有限。我们希望确保餐厅能够接待尽可能多的人，并且顾客能够坐在他们偏好的座位上。

我们有 $N$ 个顾客，编号从 $1$ 到 $N$，以及 $M$ 家餐厅，编号从 $1$ 到 $M$。

每个顾客在餐厅的一个子集中进行预订，并按照偏好顺序给出他们的预订列表。每家餐厅按照某种偏好顺序对收到的预订进行排名——例如，餐厅可能希望先报名的顾客排名更高。每家餐厅 $i$ 还有一个容量 $c_i$，即它可以支持的最大顾客数量。

你的任务是找到一种将部分顾客分配到餐厅的方案，使得满足以下条件：

1. 没有餐厅安排的顾客数量超过其容量。
2. 每个顾客最多在一家餐厅获得一个座位。
3. 不存在一家餐厅 $r$ 和一个顾客 $c$（$c$ 曾向 $r$ 预订），使得：
   • $c$ 没有被安排座位，或者 $c$ 更偏好 $r$ 而不是他被安排座位的餐厅，并且
   • $r$ 还有空位，或者 $r$ 已满但更偏好 $c$ 而不是至少一个被分配给它的顾客。

其他注意事项：

• 每个顾客至少进行了一次预订。
• 餐厅只对向其表达预订的顾客进行排名。有可能某家餐厅没有顾客希望向其预订。

输入格式

第一行包含 $N$ 和 $M$。

接下来的 $M$ 行描述容量，第 $i$ 行包含一个整数 $c_i$，表示餐厅 $i$ 的容量。

接下来 $N$ 行。第 $i$ 行描述顾客 $i$ 的预订列表，按偏好排序：该行包含一个由空格分隔的不同整数列表（在 $1$ 到 $M$ 之间），从最偏好到最不偏好。

接下来 $M$ 行。第 $i$ 行描述餐厅 $i$ 的排序偏好。当没有顾客向餐厅 $i$ 预订时，该行包含数字 $0$，否则包含一个空格分隔的不同整数列表，表示向餐厅 $i$ 预订的顾客列表，按餐厅从最偏好到最不偏好的顺序排列。

输出格式

输出一个可能的分配方案中获得座位的顾客集合（根据上述规则）。

该集合每行一个顾客，按 $id$ 升序排序。

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

2
3
4

提示

数据范围

• $1\leq N \leq 50\,000$
• $1\leq M \leq 10\,000$
• 预订选项的总数最多为 $1\,000\,000$
• $1\leq c_i \leq N$

由 Qwen3.5-Plus 翻译。