Во Флатландии наступил месяц май, который длится \(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\) дней.
Выходные данные
Выведите последовательность из \(m\) целых чисел \(a_1, a_2, \ldots, a_m\), где \(a_i\) — количество недовольных сотрудников компании в \(i\)-й день.
Примечание
В первом тесте из условия после ухода сотрудника 2 в отпуск в первый день недовольным становится самый главный начальник, который не готов терпеть отпуск ни одного из сотрудников компании кроме себя. В четвёртый день недовольным становится сотрудник 5, у которого в отпуск уходит последний его подчинённый, имеющий номер 7. В пятый день из отпуска возвращается сотрудник 2, но это не меняет число недовольных сотрудников, так как сотрудники 5 и 1 по-прежнему недовольны. В шестой день из отпуска возвращается сотрудник 3, в результате чего сотрудник 5 перестаёт быть недовольным, а в последний день самый главный начальник номер 1 сам уходит в отпуск, в результате чего недовольных людей не остаётся.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
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
|
|
2
|
5 6
1 2 3 4
4 0 0 1 0
1 5 2 3 -5 -1
|
0 2 1 0 0 0
|