题目背景

Mirko 喜欢汽车，他终于成功地开办了自己的汽车工厂。

题目描述

工厂有 $n$ 个员工，每个人都有一个上司（除了 Mirko 默认为每个人的上司）。Mirko 用 $1$ 号表示，其余员工用 $2\sim n$ 号表示。每个员工都可以提高或降低他所有下属（包括直接下属和等级树上的下属）的工资。Mirko 的职责是防止这种权力的滥用，所以他不时地想知道某个雇员的工资。他要求你写一个程序，给定一系列命令（见输入格式部分），帮助他监控工资的变化。注意：在任何时候，所有的工资都是正整数，并适合于标准的 $32$ 位整数类型（C/C++ 中的 int，Pascal 中的 longint）。

输入格式

输入共 $n+m+1$ 行。

第一行，两个整数 $n,m$，分别表示员工的总数和指令的个数。
第 $2\sim n+1$ 行，第 $i$ 行两个整数分别表示第 $i-1$ 号员工的初始工资和他的直属上司（注意，Mirko 并没有上司，因此输入他的信息的那一行仅输入他的初始工资）。
第 $n+2\sim n+m+1$ 行，每行先输入一个字符表示命令类型，接下来的输入如下所述：

• 如果字符为 p，接下来两个整数 $a,x$，表示员工 $a$ 将它的所有下属（包括直系下属和他能够间接控制到的所有下属）的工资变化了 $x$。
• 如果字符为 u，接下来仅一个整数 $a$，表示 Mirko 想知道员工 $a$ 的工资。

输出格式

对于每一个 u 操作，输出一行一个整数，表示被询问的员工的工资。

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

提示

【数据范围】

对于所有数据，$1\leqslant n,m\leqslant 5\times 10^5$，$1\leqslant a\leqslant n$，$-10^4\leqslant x\leqslant 10^4$。

【题目来源】

本题来源自 COCI 2011-2012 CONTEST 3 T5 PLAĆE，按照原题数据配置，满分 $140$ 分。

由 Eason_AC 翻译整理提供。