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

Во Флатландии наступил месяц май, который длится $$$m$$$ дней. Несмотря на то, что майские праздники давным-давно отменили для повышения производительности трудящихся, работники одной софтверной компании по старой памяти продолжают брать короткие и длинные отпуска в мае, чтобы съездить в путешествие или отметить начало дачно-огородного сезона за городом.

Разумеется, это не может не тревожить руководителей компании. В компании $$$n$$$ сотрудников, объединённых в древовидную структуру подчинения — каждому сотруднику назначен номер $$$i$$$ от $$$1$$$ до $$$n$$$, а также у каждого сотрудника $$$i$$$ (за исключением самого главного начальника, имеющего номер 1) есть ровно один непосредственный руководитель, номер которого есть $$$p_i$$$. В структуре подчинения нет циклов, то есть, если мы начнём переходить от любого сотрудника к его начальнику, затем к его начальнику и так далее, то мы рано или поздно дойдём до самого главного начальника. Будем считать, что сотрудник $$$u$$$ является подчинённым сотрудника $$$v$$$, если $$$v$$$ — непосредственный руководитель $$$u$$$, либо если непосредственный руководитель $$$u$$$ является подчинённым сотрудника $$$v$$$. Обозначим за $$$s_i$$$ количество подчинённых сотрудника $$$i$$$ (например, $$$s_1 = n - 1$$$ в соответствии с данным определением).

У каждого сотрудника $$$i$$$ есть предел терпения $$$t_i$$$, выражающийся целым числом от $$$0$$$ до $$$s_i$$$, обозначающий максимальное количество одновременно пребывающих в отпуске подчинённых сотрудника $$$i$$$, которое тот готов терпеть. Если в какой-то момент времени у сотрудника $$$i$$$ в отпуске находится более, чем $$$t_i$$$ подчинённых, и при этом сотрудник $$$i$$$ не находится в отпуске сам, то он становится недовольным.

В каждый из последующих $$$m$$$ дней случается ровно одно событие одного из двух видов — либо некоторый сотрудник уходит в отпуск с текущего дня, либо возвращается из отпуска с текущего дня. Вам известна последовательность событий, происходящих в каждый из $$$m$$$ майских дней. Ваша задача — определить, сколько сотрудников компании являются недовольными в каждый из $$$m$$$ дней.

Входные данные

В первой строке входных данных находятся два целых числа $$$n$$$ и $$$m$$$ ($$$2 \leq n, m \leq 10^5$$$) — количество сотрудников в компании и количество дней в мае.

Во второй строке находятся $$$n - 1$$$ целых чисел $$$p_2, p_3, \ldots, p_n$$$ ($$$1 \leq p_i \leq n$$$), задающих номер непосредственного руководителя для каждого из сотрудников.

В третьей строке находятся $$$n$$$ целых чисел $$$t_1, t_2, \ldots, t_n$$$ ($$$0 \leq t_i \leq s_i$$$), задающих пределы терпения каждого из сотрудников.

В четвёртой строке находятся $$$m$$$ целых чисел $$$q_1, q_2, \ldots, q_m$$$ ($$$1 \leq |q_i| \leq n$$$, $$$q_i \ne 0$$$), задающих события. Если число $$$q_i$$$ положительно, то это значит, что сотрудник $$$q_i$$$ уходит в отпуск, а если $$$q_i$$$ отрицательно, то это значит, что сотрудник $$$-q_i$$$ вернулся из отпуска. К началу мая никакой из сотрудников не находится в отпуске. Гарантируется, что если сотрудник уходит в отпуск, то до этого он не находится в отпуске и наоборот.

Выходные данные

Выведите последовательность из $$$m$$$ целых чисел $$$a_1, a_2, \ldots, a_m$$$, где $$$a_i$$$ — количество недовольных сотрудников компании в $$$i$$$-й день.

Примеры
Входные данные
7 8
4 5 1 1 5 5
0 0 0 1 2 0 0
2 6 3 7 -2 4 -3 1
Выходные данные
1 1 1 2 2 2 1 0
Входные данные
5 6
1 2 3 4
4 0 0 1 0
1 5 2 3 -5 -1
Выходные данные
0 2 1 0 0 0
Примечание

В первом тесте из условия после ухода сотрудника 2 в отпуск в первый день недовольным становится самый главный начальник, который не готов терпеть отпуск ни одного из сотрудников компании кроме себя. В четвёртый день недовольным становится сотрудник 5, у которого в отпуск уходит последний его подчинённый, имеющий номер 7. В пятый день из отпуска возвращается сотрудник 2, но это не меняет число недовольных сотрудников, так как сотрудники 5 и 1 по-прежнему недовольны. В шестой день из отпуска возвращается сотрудник 3, в результате чего сотрудник 5 перестаёт быть недовольным, а в последний день самый главный начальник номер 1 сам уходит в отпуск, в результате чего недовольных людей не остаётся.