Бандиты в центральном городе

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

Внезапно бандиты захватили часть домов. Как мэр города Вы очень обеспокоены и хотите выгнать бандитов. Итак, Вы хотите остановить поток воды к домам, захваченным гангстерами. Для этого можно засорить некоторые трубы канализации. Если на пути от резервуара к дому есть хотя бы одна забитая труба, в доме нет доступа к воде.

Вы очень боитесь бандитов, поэтому решили засорить минимальное количество труб, чтобы это выглядело как авария. При этом Вы заботитесь о горожанах, поэтому при выбранном количестве забитых труб Вы хотите минимизировать количество домов без бандитов и доступа к воде.

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

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

Первая строка содержит два целых числа $n$ и $q(2\le n\le 10^5,1\le q\le 10^5)$ — количество вершин в дереве, представляющие канализацию, и количество изменений в местонахождении бандитов.

Вторая строка содержит описание канализации: последовательность из $n-1$ целого числа $p_2,p_3,...,p_n$, где $p_i$ является родителем вершины $i(1\le p_i<i)$. Центральный резервуар находится в вершине $1$.

Следующие $q$ строк описывают изменения в местонахождении гангстеров. Каждое изменение может быть одного из двух разных типов:

• "$+v$" — гангстеры захватывают дом в вершине $v$,

• "$-v$" — гангстеры выходят из дома в вершине $v$.

Сначала все дома свободны от гангстеров. Все изменения образуют правильную последовательность: гангстеры не могут захватить дом, если он уже захвачен, и гангстеры не могут покинуть дом, если он не захвачен.

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

Выведите $2q$ целых числа, по два в каждой строке: $c_i$ — минимальное количество забитых труб и $h_i$ — минимальное количество домов без бандитов и без доступа к воде для выбранного $c_i$.

Примеры