CF1139E Maximize Mex

某学院有 $n$ 名学生和 $m$ 个社团，社团编号为 $1$ 到 $m$。每位学生有一个潜力值 $p_i$，并且是编号为 $c_i$ 的社团成员。最初，每位学生恰好属于一个社团。学院举办了一场技术节，持续接下来的 $d$ 天。技术节期间每天都会举办一次编程比赛。 每天早上，恰好有一名学生离开其所属的社团。一旦学生离开社团，就不会再加入任何社团。每天中午，院长会从每个社团中各选出一名学生（如果某个社团没有成员，则不选人），组成当天编程比赛的队伍。队伍的实力定义为队伍中所有学生潜力值的 mex。院长希望知道在接下来的 $d$ 天里，每天队伍的最大可能实力。因此，每天院长都会选择一种方案，使得队伍实力最大。 集合 $S$ 的 mex 定义为不在 $S$ 中的最小非负整数。例如，$\{0, 1, 1, 2, 4, 5, 9\}$ 的 mex 是 $3$，$\{1, 2, 3\}$ 的 mex 是 $0$，空集 $\varnothing$ 的 mex 是 $0$。

第一行包含两个整数 $n$ 和 $m$（$1 \leq m \leq n \leq 5000$），分别表示学生人数和社团数。 第二行包含 $n$ 个整数 $p_1, p_2, \ldots, p_n$（$0 \leq p_i < 5000$），表示第 $i$ 位学生的潜力值。 第三行包含 $n$ 个整数 $c_1, c_2, \ldots, c_n$（$1 \leq c_i \leq m$），表示第 $i$ 位学生最初所在的社团编号。 第四行包含一个整数 $d$（$1 \leq d \leq n$），表示院长需要知道队伍最大实力的天数。 接下来的 $d$ 行，每行包含一个整数 $k_i$（$1 \leq k_i \leq n$），表示第 $i$ 天离开社团的学生编号。保证每个 $k_i$ 对应的学生此前没有离开过社团。

对于接下来的 $d$ 天，每天输出一行，表示当天队伍的最大可能实力。

考虑第一个样例： 第一天，学生 $3$ 离开社团。现在剩下的学生是 $1$、$2$、$4$ 和 $5$。我们可以选择学生 $1$、$2$ 和 $4$，得到最大实力 $3$。注意，不能选择学生 $1$、$2$ 和 $5$，因为学生 $2$ 和 $5$ 属于同一个社团。也不能选择学生 $1$、$3$ 和 $4$，因为学生 $3$ 已经离开社团。 第二天，学生 $2$ 离开社团。现在剩下的学生是 $1$、$4$ 和 $5$。我们可以选择学生 $1$、$4$ 和 $5$，得到最大实力 $1$。 第三天，剩下的学生是 $1$ 和 $5$。我们可以选择学生 $1$ 和 $5$，得到最大实力 $1$。 第四天，剩下的学生只有 $1$。我们可以选择学生 $1$，得到最大实力 $1$。 第五天，所有社团都没有学生，因此最大实力为 $0$。 由 ChatGPT 4.1 翻译