Time Limit: 1000 MS Memory Limit: 512M


Description

Cxh的三星月骑就差一个了,只有做出下面这个题才能祈祷发牌员来一手神抽。
月骑住在一棵有根有权树上,接下来月骑有一些动作,动作分为两类:
1 y b,把y的权值增加b。
2 y,求y的子树上所有结点的权值之和。

Input

输入:第一行有三个整数 N,M和R根节点编号。(1<=n,m<=1e6,b<=1e6)
第二行有 N 个整数,第 i 个整数表示结点i的权值。
接下来的 N?1 行中,每行两个整数,表示一条边。
接下来的 M 行中,每行一组操作。

Output

输出:对于每组 2 y 操作,输出一个整数

Sample Input

10 14 9
12 -6 -4 -3 12 8 9 6 6 2
8 2
2 10
8 6
2 7
7 1
6 3
10 9
2 4
10 5
1 4 -1
2 2
1 7 -1
2 10
1 10 5
2 1
1 7 -5
2 5
1 1 8
2 7
1 8 8
2 2
1 5 5
2 6

Sample Output

21
34
12
12
23
31
4