Trong quá trình tối ưu hóa kiến trúc hạ tầng backend, hệ thống lõi được mô phỏng dưới dạng một mạng lưới gồm ~n~ máy chủ, được đánh số từ ~1~ đến ~N~. Cấu trúc mạng này có dạng một cây có gốc, trong đó máy chủ 1 là máy chủ trung tâm. Máy chủ ~p_i~ là máy chủ cấp trên trực tiếp của máy chủ thứ ~i~ với mọi ~2 \le i \le N~. Ban đầu, tài nguyên phân bổ (tính bằng đơn vị băng thông) tại tất cả máy chủ đều bằng ~0~.

Ban được cấp quyền sử dụng một bộ điều phối đặc biệt có thể tăng lượng tài nguyên cho các máy chủ. Khi cung cấp ba tham số ~X, Y~ và ~K~ cho bộ điều phối, hệ thống sẽ tự động phân bổ thêm tài nguyên cho tất cả các máy chủ nằm trong nhánh mạng do máy chủ ~X~ quản lý. Cụ thể, nếu máy chủ ~X'~ nằm trong cây con gốc ~X~, lượng tài nguyên của ~X'~ sẽ được cộng thêm một lượng là ~\lfloor \frac{Y}{K^d} \rfloor~, trong đó ~d~ là khoảng cách trên đường đi ngắn nhất từ ~X~ đến ~X'~. Nói cách khác, với một thao tác, lượng tài nguyên của bản thân máy chủ ~X~ tăng thêm ~Y~, các máy chủ con trực tiếp của ~X~ tăng thêm ~\lfloor \frac{Y}{K} \rfloor~, các máy chủ là con của các máy chủ con trực tiếp của ~X~ tăng thêm ~\lfloor \frac{Y}{K^2} \rfloor~.

Yêu cầu: Có ~Q~ thao tác cần thực hiện tuần tự trên hệ thống. Mỗi thao tác thuộc một trong hai loại sau:

1. 1 X Y K: Kích hoạt bộ điều phối tại máy chủ ~X~ với tham số ~Y~ và mức độ suy hao là ~K~.

2. 2 X: Cho biết tổng lượng tài nguyên đang được phân bổ cho toàn bộ các máy chủ nằm trong nhánh mạng do máy chủ ~X~ quản lý (tổng tài nguyên của cây con gốc ~X~).

Đầu vào

• Dòng thứ nhất chứa hai số nguyên dương ~N~ và ~Q~ (~1 \le N, Q \le 5 \times 10^5~) - lần lượt là số lượng máy chủ và số lượng thao tác cần thực hiện.
• Dòng thứ hai chứa ~N - 1~ số nguyên ~p_2, p_3, \ldots, p_n~ (~1 \le p_i < i~) - trong đó ~p_i~ là máy chủ cấp trên trực tiếp của máy chủ ~i~.
• ~Q~ dòng tiếp theo, mỗi dòng mô tả một thao tác theo một trong hai định dạng:
  • 1 X Y K (~1 \le X \le N; 1 \le Y, K \le 2 \times 10^5~).
  • 2 X (~1 \le X \le N~).

Đầu ra

Với mỗi thao tác loại 2 theo đúng thứ tự trong đầu vào, in ra một dòng một số nguyên duy nhất là kết quả của truy vấn đó.

Giới hạn

• Subtask ~1~ (~10\%~ số điểm): ~N, Q \le 1000~.
• Subtask ~2~ (~10\%~ số điểm): ~K = 1~ trong mọi thao tác loại ~1~.
• Subtask ~3~ (~15\%~ số điểm): Mỗi máy chủ kết nối trực tiếp với tối đa ~2~ máy chủ khác.
• Subtask ~4~ (~15\%~ số điểm): Cấu trúc mạng là một cây nhị phân hoàn hảo.
• Subtask ~5~ (~20\%~ số điểm): ~N, Q \le 10^5~.
• Subtask ~6~ (~30\%~ số điểm): Không có ràng buộc gì thêm.

Ví dụ

Đầu vào

6 5
1 1 2 2 3
1 1 10 2
2 2
2 1
1 2 20 3
2 2

Đầu ra

9
26
41