Mô tả

Trong một khu vườn thần kỳ mọc lên một cổ thụ có n cành, gốc đặt tại cành 1. Mỗi cành được xem như một nhánh con; ban đầu trên mọi cành đều chưa có quả (giá trị 0). Người làm vườn có hai hành động:

• 1 u v - Rải "phân bón" lên cành u; mọi nhánh bên dưới cành đó lập tức ra thêm v quả (có thể âm nếu sâu bệnh làm mất quả).
• 2 u - Hỏi cành u hiện đang có bao nhiêu quả.

Hãy giúp người làm vườn xử lý q hành động và trả lời các câu hỏi loại 2.

Input

• Dòng đầu chứa hai số nguyên n, q (1 ≤ n,q ≤ 105).
• n - 1 dòng tiếp, mỗi dòng gồm hai số u, v - hai cành kề nhau.
• q dòng tiếp, mỗi dòng là:
    • 1 u v - rải phân bón
    • 2 u - truy vấn số quả

Output

Với mỗi truy vấn loại 2, in ra số nguyên duy nhất là lượng quả trên cành được hỏi.

Ràng buộc

• 1 ≤ n,q ≤ 105
• 1 ≤ u ≤ n
• |v| ≤ 109

Ví dụ

Input

3 5
1 2
1 3
1 1 5
2 2
1 3 1
2 3
2 1

Output

5
6
5