Місце
Рашад захоплюється автомобілями, і нарешті йому вдалося відкрити власний автомобільний завод! На заводі працює N працівників, кожен з яких має рівно одного керівника (крім Рашада - він є керівником усіх за замовчуванням). Рашад позначений номером 1, а решта працівників - номерами від 2 до N. Кожен працівник може змінювати зарплату всіх своїх підлеглих (як прямих, так і тих, що нижче в ієрархічному дереві). Завдання Рашада - запобігти зловживанню такою владою, тому він час від часу хоче знати зарплату конкретного працівника. Він просить вас створити програму, яка допоможе йому відстежувати зміни зарплат, враховуючи послідовність команд, описаних у розділі вводу.
Ввід:
Перша строка вводу містить два розділених пробілом додатних числа N (1 ≤ N ≤ 500 000), кількість працівників, та M (1 ≤ M ≤ 500 000), кількість змін зарплат та запитів про зарплати. Наступні N рядків містять інформацію про працівників 1, 2, ..., N (відповідно): початкова зарплата та ідентифікатор його прямого керівника. Примітка: Рашад не має керівника, тому його рядок міститиме лише його початкову зарплату.
Наступні M рядків містять одну з наступних команд:
p A X - працівник A збільшує (або зменшує у випадку від'ємного X) зарплату всіх своїх підлеглих на величину X (-10 000 ≤ X ≤ 10 000);
u A - Рашад хоче знати зарплату працівника A.
Вивід:
Вивід повинен містити один рядок для кожного запиту типу ‘2’ у вводі - поточну зарплату вказаного працівника.