大学里有 $$$n$$$ 名学生和 $$$m$$$ 俱乐部。俱乐部编号从 $$$1$$$ 到 $$$m$$$。每个学生都有潜在的 $$$p_i$$$,并且是索引为 $$$c_i$$$ 的俱乐部的成员。最初,每个学生都是一个俱乐部的成员。一场技术盛宴在学院开始,并将持续 $$$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$$$),其中 $$$p_i$$$ 是第 $$$i$$$ 个学生的潜力。
第三行包含 $$$n$$$ 整数 $$$c_1, c_2, \ldots, c_n$$$ ($$$1 \leq c_i \leq m$$$),这意味着第 $$$i$$$ 学生最初是索引为 $$$c_i$$$ 的俱乐部成员。
第四行包含一个整数$$$d$$$ ($$$1 \leq d \leq n$$$),主管想要知道团队最大可能实力的天数。
接下来的 $$$d$$$ 行都包含一个整数 $$$k_i$$$ ($$$1 \leq k_i \leq n$$$),这意味着第 $$$k_i$$$ 个学生在第 $$$i$$$ 天离开了俱乐部。可以保证第 $$$k_i$$$ 名学生没有提前离开他们的俱乐部。
输出
对于 $$$d$$$ 的每一天,打印当天团队的最大可能兵力。
示例
输入 #1
5 3 0 1 2 2 0 1 2 2 3 2 5 3 2 4 5 1
输出 #1
3 1 1 1 0
输入 #2
5 3 0 1 2 2 1 1 3 2 3 2 5 4 2 3 5 1
输出 #2
3 2 2 1 0
输入 #3
5 5 0 1 2 4 5 1 2 3 4 5 4 2 3 5 4
输出 #3
1 1 1 1
注意
考虑第一个示例:
第一天,学生 $$$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$$$。