Бандити в центральному місті

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

Раптом бандити захопили частину будинків. Як мер міста, Ви дуже стурбовані і хочете вигнати бандитів. Тому Ви вирішили зупинити потік води до будинків, захоплених гангстерами. Для цього можна засмітити деякі труби каналізації. Якщо на шляху від резервуара до будинку є хоча б одна забита труба, у будинку немає доступу до води.

Ви дуже боїтеся бандитів, тому вирішили засмітити мінімальну кількість труб, щоб це виглядало як аварія. При цьому Ви дбаєте про городян, тому при вибраній кількості забитих труб Ви хочете мінімізувати кількість будинків без бандитів і доступу до води.

На жаль, бандити можуть з'являтися і зникати з деяких будинків. Отже, Ви запитуєте вчених про мінімально необхідну кількість забитих труб і мінімально необхідну кількість будинків без бандитів і доступу до води після кожної зміни місцезнаходження бандитів.

Вхідні дані

Перший рядок містить два цілі числа $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$.

Приклади