Công ty ABC quản lý nhân sự theo cấu trúc phân cấp dạng cây với \(n\) nhân viên, bắt đầu từ Giám đốc (nhân viên số \(1\) là gốc của cây). Ban đầu, hiệu suất làm việc của tất cả nhân viên đều là \(0\). Công ty muốn quản lý hiệu suất làm việc của các nhân viên thông qua hai loại thao tác sau:

• Tăng hiệu suất: Tăng hiệu suất làm việc của toàn bộ nhân viên trong nhóm do một nhân viên quản lý, bao gồm chính nhân viên đó và tất cả nhân viên cấp dưới của họ, thêm một số điểm cố định.
• Truy vấn hiệu suất: Lấy ra hiệu suất làm việc hiện tại của một nhân viên cụ thể.

Nhiệm vụ của bạn là giúp công ty quản lý các thao tác này một cách hiệu quả.

Dữ liệu vào

• Dòng đầu tiên chứa số nguyên \(n,q\) \((1 \le n,q \le 10^5)\) — số lượng nhân viên và số lượng truy vấn.
• \(n - 1\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(u\) và \(v\) \((1 \le u,v \le n, u \neq v)\), biểu diễn rằng nhân viên \(u\) và \(v\) có quan hệ trực tiếp (quản lý và nhân viên).
• Tiếp theo là \(q\) dòng, mỗi dòng chứa một trong hai dạng truy vấn:
• \(1\) \(u\) \(v\): Tăng hiệu suất làm việc của toàn bộ nhân viên trong nhóm do nhân viên \(u\) quản lý (bao gồm cả \(u\)) lên \(v\).
• \(2\) \(u\): Truy vấn hiệu suất hiện tại của nhân viên \(u\).

Dữ liệu ra

• Đối với mỗi truy vấn loại \(2\), in ra hiệu suất hiện tại của nhân viên \(u\).

Ràng buộc

• \(1 \le n,q \le 10^5\)
• \(1 \le u \le n\)
• \(|v| \le 10^9\)

Input 1

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

Output 1

0
5
5
-5

Input 2

5 5
1 2
2 3
2 4
4 5
1 4 -4
2 5
1 2 1
2 5
1 1 -4

Output 2

-4
-3