E. Максимизировать mex
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

В колледже учатся $$$n$$$ студентов, также в колледже есть $$$m$$$ клубов, пронумерованных от $$$1$$$ до $$$m$$$. У каждого студента известен его потенциал $$$p_i$$$ и номер клуба $$$c_i$$$, членом которого он является. Изначально каждый студент является членом ровно одного клуба. Скоро в колледже состоится технический фестиваль, который продлится $$$d$$$ дней. Каждый день в рамках фестиваля будет проведено соревнование по программированию.

Каждый день утром, ровно один студент решает покинуть свой клуб. После того как студент покинул свой клуб, он больше не присоединится ни к какому клубу снова. Каждый день в полдень, директор колледжа выбирает по одному студенту из каждого клуба (в случае если в каком-то клубе нет ни одного студента, из этого клуба не будет выбран никто) и составляет из них команду на этот день. Силой команды называется mex потенциалов студентов, которые в неё входят. Директор хочет выяснить наибольшую возможную силу команды в каждый из следующих $$$d$$$ дней. Таким образом, каждый день директор выбирает команду так, чтобы максимизировать силу команды. Для мультимножества $$$S$$$, его mex определён как наименьший неотрицательный элемент не входящий в $$$S$$$. Например, mex мультимножества $$$\{0, 1, 1, 2, 4, 5, 9\}$$$ равн $$$3$$$, mex мультимножества $$$\{1, 2, 3\}$$$ равен $$$0$$$, а mex $$$\varnothing$$$ (пустого множества) равен $$$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$$$ дней, выведите наибольшую возможную силу команды в этот день.

Примеры
Входные данные
5 3
0 1 2 2 0
1 2 2 3 2
5
3
2
4
5
1
Выходные данные
3
1
1
1
0
Входные данные
5 3
0 1 2 2 1
1 3 2 3 2
5
4
2
3
5
1
Выходные данные
3
2
2
1
0
Входные данные
5 5
0 1 2 4 5
1 2 3 4 5
4
2
3
5
4
Выходные данные
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$$$.