Description

The factory has $n$ employees. Each employee has a boss (except that Mirko is considered the boss of everyone by default). Mirko is labeled as employee $1$, and the other employees are labeled $2 \sim n$. Each employee can increase or decrease the salaries of all of their subordinates (including direct subordinates and all subordinates in the hierarchy tree). Mirko’s duty is to prevent abuse of this power, so from time to time he wants to know the salary of some employee. He asks you to write a program that, given a sequence of commands (see the Input Format section), helps him monitor salary changes. Note: At any time, all salaries are positive integers and fit in a standard 32-bit integer type (int in C/C++, longint in Pascal).

Input Format

The input has a total of $n + m + 1$ lines.

The first line contains two integers $n, m$, representing the total number of employees and the number of commands.

Lines $2 \sim n + 1$: on line $i$, two integers are given, representing the initial salary of employee $i - 1$ and their direct boss (note that Mirko has no boss, so on the line containing his information, only his initial salary is given).

Lines $n + 2 \sim n + m + 1$: each line first contains a character indicating the command type, followed by the input described below:

• If the character is p, then two integers $a, x$ follow, meaning that employee $a$ increases the salaries of all of their subordinates (including direct subordinates and all subordinates they can indirectly control) by $x$ (if $x$ is negative, it means decreasing salaries).
• If the character is u, then only one integer $a$ follows, meaning that Mirko wants to know the salary of employee $a$.

Output Format

For each u operation, output one line with one integer, representing the salary of the queried employee.

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

8
5

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

6
5
7

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

7
9
7
5

Hint

Constraints

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

Source

This problem is from COCI 2011-2012 CONTEST 3 T5 PLAĆE, and with the original testdata configuration, the full score is $140$ points.

Translated and organized by Eason_AC, with minor adjustments by 123asdf123.

Translated by ChatGPT 5