eolymp
bolt
Try our new interface for solving problems

Place

Zaman məhdudiyyəti 1.5 saniyə
Yaddaşı istafadə məhdudiyyəti 64 MiB

Rashad loves cars and he finally managed to start his own carfactory! Factory has N employees, each of them has exactly one superior (except Rashad - he is by default everybody’s superior) . Rashad is denotedby number 1, and the rest of the employees with numbers 2 to N. Every employee can raise or lower the wages of all of his subordinates (both direct subordinates and those lower in the hieararchy tree). Rashad’s role is to prevent abuse of such power, so from time to time he wants to know wage of a particular employee. He is asking you to write a program which will help him monitor wage changes, given a sequence of commands described in the input section.

####Input:First line of input contains two space-separated positiveintegers N (1N500 000), number of employees, and M (1M500 000), number of wage changes and wage queries.Next N lines contain the information about employees 1, 2, ..., N (respectively): starting wage and the identifier of his direct supervisor. Remark: Rashad has no supervisor, so his line will contain only his starting wage.

Next M lines contain one of the following:

    1. p A X - employee A increases (or decreases in case of anegative X) wage of all his subordinates by the amount X(-10 000 ≤ X ≤ 10 000);

    1. u A - Rashad wants to know the wage of employee A.

####Output:Output should contain one line for each ‘2’ query in the input - the current wage of the given employee.

Nümunə

Giriş verilənləri #1
2 3
5
3 1
p 1 5
u 2
u 1
Çıxış verilənləri #1
8
5
Giriş verilənləri #2
5 5
4
2 1
6 1
7 1
3 4
u 3
p 1 -1
u 3
p 4 5
u 5
Çıxış verilənləri #2
6
5
7
Giriş verilənləri #3
6 7
5
4 1
3 2
7 3
2 3
3 5
p 3 2
p 2 4
u 3
u 6
p 5 -2
u 6
u 1
Çıxış verilənləri #3
7
9
7
5
Mənbə IATI2019 Azerbaijan Selection based on Croatian Open Olympiad Round 3 2011/2012