Giải bài trực tuyến

Bờm hiện đang điều hành một công ty có đến N người (N <= 100000). Các nhân viên được đánh số từ 1 đến N (trong đó Bờm được đánh số 1). Để dễ quản lý, mỗi người chỉ có duy nhất một giám sát trực tiếp  (trừ Bờm – giám đốc của công ty), nhưng một người lại có thể có nhiều nhân viên trực tiếp.

Đối với một người bất kì, nhân viên cấp 1 là nhân viên trực tiếp; và nhân viên cấp K (K>1) là tất cả nhân viên cấp 1 của nhân viên cấp (K-1).

Để tăng cường hiệu quả cũng như sự hợp tác và đoàn kết trong công ty, Bờm cho phép mỗi người có thể cùng lúc thưởng (phạt) cho tất cả các nhân cấp k (k>0) của mình.

Do số lượng nhân viên quá đông, nên việc quản lý thưởng-phạt là một việc không dễ dàng.

Input

-          Dòng đầu tiên chứ số N.

-          N-1 dòng tiếp theo là các cặp số (u v) thể hiện u là giám sát trực tiếp của v.

-          Dòng tiếp theo chứa số yêu cầu - M (M<=500000).

-          M dòng tiếp theo là các yêu cầu có dạng:

• 1 u k e : tăng lượng tiền thưởng của tất cả các nhân viên cấp k của u lên e đồng (|e| <= 2000).
• 2 u : nhân viên u muốn biết số tiền thưởng của mình hiện tại.

Output

-          In ra kết quả tương ứng đối với mỗi yêu cầu 2.

Example

Input:

6

1 2

1 3

2 4

3 5

3 6

6

2 6

1 1 2 1000

1 2 1 100

1 3 1 -100

2 4

2 5

Ouput:

0

1100

900