Problem Description

Mirko loves cars and has finally succeeded in starting his own car factory.

Problem Description

The factory has $n$ employees, each with a supervisor (except for Mirko, who is the supervisor for everyone). Mirko is represented by number 1, and the other employees are represented by numbers 2 through $n$. Each employee can increase or decrease the salaries of all their subordinates (both direct and indirect). Mirko's duty is to prevent the abuse of this power, so he occasionally wants to know the salary of a particular employee. He asks you to write a program that, given a series of commands (as described in the Input Format section), helps him monitor the salary changes. Note: At any time, all salaries are positive integers and fit within the standard 32-bit integer type (e.g., int in C/C++, longint in Pascal).

Input Format

The input consists of $n+m+1$ lines.

The first line contains two integers $n$ and $m$, representing the total number of employees and the number of commands, respectively.
Lines 2 through $n+1$ contain two integers each, representing the initial salary and the direct supervisor of the $(i-1)$-th employee (note that Mirko has no supervisor, so the line containing his information only includes his initial salary).
Lines $n+2$ through $n+m+1$ describe the commands, starting with a character indicating the command type, followed by:

• If the character is p, two integers $a$ and $x$ follow, indicating that employee $a$ changes the salary of all their subordinates (both direct and indirect) by $x$.
• If the character is u, one integer $a$ follows, indicating that Mirko wants to know the salary of employee $a$.

Output Format

For each u command, output a single line containing the salary of the queried employee.

Sample Input and Output

Sample Input #1

2 3
5
3 1
p 1 5
u 2
u 1

Sample Output #1

8
5

Sample Input #2

5 5
4
2 1
6 1
7 1
3 4
u 3
p 1 -1
u 3
p 4 5
u 5

Sample Output #2

6
5
7

Sample Input #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

Sample Output #3

7
9
7
5

Notes

[Data Range]

For all data, $1 \leqslant n, m \leqslant 5 \times 10^5$, $1 \leqslant a \leqslant n$, $-10^4 \leqslant x \leqslant 10^4$.

[Problem Source]

This problem is from COCI 2011-2012 CONTEST 3 T5 PLAĆE, configured with the original problem data, with a full score of $140$ points.

Provided by Eason_AC for translation and arrangement.

见题面 Input 部分

见题面 Output 部分