Долгое время в центральном городе не было проблем с водой. Канализация города представляет собой укоренившееся дерево: центральный резервуар находится у корня, а дома --- у листьев. Вода из центрального резервуара течет в дома по трубам, идущим по краям дерева. В каждом доме есть доступ к воде. Внезапно бандиты захватили часть домов. Как мэр города Вы очень обеспокоены и хотите выгнать бандитов. Итак, Вы хотите остановить поток воды к домам, захваченным гангстерами. Для этого можно засорить некоторые трубы канализации. Если на пути от резервуара к дому есть хотя бы одна забитая труба, в доме нет доступа к воде. Вы очень боитесь бандитов, поэтому решили засорить минимальное количество труб, чтобы это выглядело как авария. При этом Вы заботитесь о горожанах, поэтому при выбранном количестве забитых труб Вы хотите минимизировать количество домов без бандитов и доступа к воде. К сожалению, бандиты могли появляться и исчезать из некоторых домов. Итак, Вы спрашиваете ученых о минимально необходимом количестве забитых труб и минимально необходимом количестве домов без бандитов и доступа к воде после каждой смены местоположения бандитов. \InputFile Первая строка содержит два целых числа $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$ строк описывают изменения в местонахождении гангстеров. Каждое изменение может быть одного из двух разных типов: \begin{itemize} \item "$+ v$" --- гангстеры захватывают дом в вершине $v$, \item "$- v$" --- гангстеры выходят из дома в вершине $v$. \end{itemize} Сначала все дома свободны от гангстеров. Все изменения образуют правильную последовательность: гангстеры не могут захватить дом, если он уже захвачен, и гангстеры не могут покинуть дом, если он не захвачен. \OutputFile Выведите $2q$ целых числа, по два в каждой строке: $c_i$ --- минимальное количество забитых труб и $h_i$ --- минимальное количество домов без бандитов и без доступа к воде для выбранного $c_i$.