Cho một cây gồm \(n\) đỉnh có gốc \(1\). Đỉnh thứ \(i\) có nhẵn \(a_i\). Ban đầu các nhãn đều bằng \(0\). Có \(q\) truy vấn, mỗi truy vấn có 2 dạng:

• \(1 u x\): tăng tất cả các đỉnh trong cây con gốc \(u\) lên \(x (|x|≤10^9).\)

• \(2 u\): Tìm giá trị nhãn trên đỉnh \(u\).

Input

• Dòng 1 chứa 2 số \(n,q (1≤n,q≤10^5).\)

• \(n-1\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(u,v\) thể hiện cạnh \(u,v (1≤u,v≤n).\)

• \(q\) dòng tiếp theo, mỗi dòng chứa một truy vấn thuộc dạng trên.

Output

• Với truy vấn loại 2, in ra nhãn của đỉnh tương ứng.

Sample Input

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

Sample Output

0
5
5
-5