Місце#9432

Місце

1,5 секунди

64 мегабайти

Легка

Рашад захоплюється автомобілями, і нарешті йому вдалося відкрити власний автомобільний завод! На заводі працює $N$ працівників, кожен з яких має рівно одного керівника (крім Рашада - він є керівником усіх за замовчуванням). Рашад позначений номером $1$ , а решта працівників - номерами від $2$ до $N$ . Кожен працівник може змінювати зарплату всіх своїх підлеглих (як прямих, так і тих, що нижче в ієрархічному дереві). Завдання Рашада - запобігти зловживанню такою владою, тому він час від часу хоче знати зарплату конкретного працівника. Він просить вас створити програму, яка допоможе йому відстежувати зміни зарплат, враховуючи послідовність команд, описаних у розділі вводу.

Вхідні дані

Перша строка вводу містить два розділених пробілом додатних числа $N$ ( $1 \leq N \leq 500000$ 1 \le N \le 500000), кількість працівників, та $M$ ( $1 \leq M \leq 500000$ 1 \le M \le 500000), кількість змін зарплат та запитів про зарплати. Наступні $N$ рядків містять інформацію про працівників $1$ , $2$ , ..., $N$ (відповідно): початкова зарплата та ідентифікатор його прямого керівника. Примітка: Рашад не має керівника, тому його рядок міститиме лише його початкову зарплату.

Наступні $M$ рядків містять одну з наступних команд:

1. p A X - працівник $A$ збільшує (або зменшує у випадку від'ємного $X$ ) зарплату всіх своїх підлеглих на величину $X$ ( $- 10000 \leq X \leq 10000$ -10000 \le X \le 10000);
1. u A - Рашад хоче знати зарплату працівника $A$ .

Вихідні дані

Вивід повинен містити один рядок для кожного запиту типу '2' у вводі - поточну зарплату вказаного працівника.

Приклади

Приклад 1

Приклад 2

Приклад 3