工资

坤坤开了一个综艺公司，共有$N$名员工，编号$1 \sim N$（坤坤的编号为$1$），除了坤坤以外每个员工都有一个直接上司。

现在坤坤想要你帮他维护公司的工资系统：

每个人有一个初始工资，一个员工可以对他的所有下属（直接和间接）的工资进行修改，坤坤在一些时候想知道某个员工的工资。

输入格式

第$1$行，$2$个整数$N,M$，表示公司员工数和操作次数。

第$2$行，$1$个整数是坤坤的起始工资。

第$3$行到第$N+1$行，每行两个整数$W_i,S_i$，分别表示第$i$名员工的起始工资和上司。

接下来$M$行，每行表示$1$次操作，分为以下$2$类：

1. p A X – 员工$A$给他/她的所有下属的工资增加$X(|X|≤10000)$

2. u A – 坤坤想知道员工$A$现在的工资是多少（可能为负QAQ）

输出格式

对于每个第二类操作输出$1$行$1$个整数，表示第$A$名员工当时的工资。

提示

对于$30\%$的数据，有$1 \le N,M \le 10^3$

对于$100\%$的数据，有$1 \le N,M \le 5*10^5,1 \le Wi \le 10000$