JOI-kun có nhiều năm kinh nghiệm trồng rau trong vườn nhà. Giờ đây, cậu dự định quản lý trang trại IOI.

Trang trại IOI gồm \(N\) mảnh đất, đánh số từ \(1\) đến \(N\), và \(N-1\) con đường, đánh số từ \(1\) đến \(N-1\). Con đường thứ \(i\) nối hai mảnh đất \(A_i,B_i\) theo cả hai chiều. Có thể đi từ bất kỳ mảnh đất nào đến bất kỳ mảnh đất nào khác qua các con đường. Mỗi mảnh đất có một vòi phun nước để tưới các mảnh đất xung quanh.

JOI-kun muốn trồng kê JOI trong trang trại. Đây là một loài cây kỳ lạ: chiều cao thay đổi ngay khi được tưới nước. Tuy nhiên, cây rất yếu; mỗi khi chiều cao lớn hơn hoặc bằng \(L\), phần ngọn dài \(L\) lập tức gãy ra. JOI-kun thu hoạch những phần bị gãy này.

Ban đầu, trên mảnh đất thứ \(j\) có một cây kê JOI cao \(H_j\). Trong \(Q\) ngày tiếp theo, mỗi ngày thứ \(k\) (\(1\le k\le Q\)), JOI-kun thực hiện một trong hai thao tác:

• Loại 1: Dùng vòi phun tại mảnh đất \(X_k\) để tưới tất cả mảnh đất cách \(X_k\) không quá \(D_k\). Chiều cao của mỗi cây được tưới được nhân với \(W_k\). Do phần ngọn dài \(L\) liên tục gãy ra ngay khi chiều cao đạt hoặc vượt \(L\), một cây ban đầu cao \(h\) cuối cùng có chiều cao bằng phần dư của \(hW_k\) khi chia cho \(L\).
• Loại 2: Đo chiều cao của cây kê trên mảnh đất \(X_k\).

Khoảng cách giữa hai mảnh đất là số con đường ít nhất cần đi qua để di chuyển từ mảnh đất này đến mảnh đất kia.

Để kiểm tra cây có phát triển đúng kế hoạch không, JOI-kun muốn tính trước chiều cao đo được trong từng thao tác loại 2. Hãy viết chương trình tính những chiều cao đó từ thông tin trang trại và kế hoạch chăm sóc.

Dữ liệu vào

Dữ liệu được cho theo định dạng sau. Mọi giá trị đều là số nguyên.

N L
A_1 B_1
A_2 B_2
...
A_{N-1} B_{N-1}
H_1
H_2
...
H_N
Q
(Truy vấn 1)
(Truy vấn 2)
...
(Truy vấn Q)

Truy vấn thứ \(k\) bắt đầu bằng số nguyên \(T_k\) và có một trong hai dạng:

• 1 X_k D_k W_k: tưới tất cả mảnh đất cách \(X_k\) không quá \(D_k\), nhân chiều cao mỗi cây được tưới với \(W_k\), rồi áp dụng quy tắc gãy ngọn nêu trên.
• 2 X_k: đo chiều cao cây trên mảnh đất \(X_k\).

Dữ liệu ra

Với mỗi truy vấn loại 2, theo thứ tự xuất hiện, in chiều cao cây trên mảnh đất được hỏi. Mỗi kết quả nằm trên một dòng.

Ràng buộc

• \(2\le N\le200000\).
• \(2\le L\le10^9\).
• \(1\le A_i<B_i\le N\) với mọi \(1\le i\le N-1\).
• Có thể đi từ bất kỳ mảnh đất nào đến bất kỳ mảnh đất nào khác qua các con đường.
• \(0\le H_j\le L-1\) với mọi \(1\le j\le N\).
• \(1\le Q\le400000\).
• \(T_k\in\{1,2\}\) với mọi \(1\le k\le Q\).
• Nếu \(T_k=1\): \(1\le X_k\le N\), \(0\le D_k\le40\), \(0\le W_k\le L-1\).
• Nếu \(T_k=2\): \(1\le X_k\le N\).

Phân nhóm

• Nhóm 1 (3 điểm): \(N\le1000\) và \(Q\le1000\).
• Nhóm 2 (9 điểm): \(D_k\le1\) với mọi truy vấn có \(T_k=1\).
• Nhóm 3 (29 điểm): \(D_k\le2\) với mọi truy vấn có \(T_k=1\).
• Nhóm 4 (12 điểm): \(W_k=0\) với mọi truy vấn có \(T_k=1\).
• Nhóm 5 (30 điểm): \(W_k=2\) với mọi truy vấn có \(T_k=1\).
• Nhóm 6 (17 điểm): Không có ràng buộc bổ sung.

Ví dụ

4 7
1 2
2 3
3 4
1
1
1
1
11
1 2 1 2
1 1 0 2
2 1
2 2
2 3
2 4
1 4 10 2
2 1
2 2
2 3
2 4

4
2
2
1
1
4
4
2

6 10
5 6
1 2
1 4
2 6
3 6
9
2
3
4
9
1
10
1 5 1 7
2 4
1 4 1 9
1 5 0 7
2 1
1 1 1 3
1 6 1 4
2 5
2 4
2 3

4
1
4
8
2

8 10
1 3
3 5
4 7
6 7
4 5
7 8
2 4
5
8
6
4
6
2
9
3
11
1 2 2 0
2 1
1 6 1 0
2 4
2 6
1 5 2 0
2 8
1 7 2 0
2 6
2 7
2 4

5
0
0
3
0
0
0

Nguồn

JOI 2021/2022, kỳ thi tuyển chọn mùa xuân, ngày thi thứ ba (22/03/2022). Đề của Ủy ban Olympic Tin học Nhật Bản (JCIOI). Bản dịch tiếng Việt theo giấy phép CC BY-SA 4.0.