Vương quốc JOI có \(N\) thành phố được đánh số từ \(1\) đến \(N\), nối với nhau bởi \(N-1\) con đường một chiều. Với mỗi \(i=2,3,\ldots,N\), có một con đường đi từ thành phố \(i\) đến thành phố \(P_i\), trong đó \(1\le P_i<i\).

Mỗi thành phố có một mức độ nguy hiểm. Thủ đô, tức thành phố \(1\), có mức độ nguy hiểm bằng \(0\). Với thành phố \(i\) (\(2\le i\le N\)), mức độ nguy hiểm là số con đường trên đường đi từ thành phố \(i\) đến thành phố \(1\). Cấu trúc của vương quốc bảo đảm rằng đường đi này là duy nhất.

Hiện có \(K_i\) con hải ly sống tại thành phố \(i\) (\(1\le i\le N\)). Tổng thống Bitaro lập một kế hoạch di cư kéo dài \(Q\) ngày. Vào ngày thứ \(j\) (\(1\le j\le Q\)), một trong ba sự kiện sau xảy ra:

• Di dời: Tất cả hải ly đang sống tại các thành phố có mức độ nguy hiểm \(X_j\) di chuyển đến thành phố có mức độ nguy hiểm \(Y_j\) mà chúng có thể đến bằng cách đi qua một hoặc nhiều con đường từ thành phố hiện tại. Bảo đảm \(0\le Y_j<X_j\). Với mỗi con hải ly, thành phố đích được xác định duy nhất.
• Nhập cư: Số hải ly ở thành phố \(A_j\) tăng thêm \(L_j\) do có hải ly từ ngoài vương quốc đến sinh sống.
• Khảo sát: Khảo sát số hải ly hiện đang sống tại thành phố \(B_j\).

Là cấp dưới của Bitaro, bạn nhận ra có thể tính kết quả của mọi lần khảo sát chỉ từ thông tin kế hoạch mà không cần đến tận nơi. Cho cấu trúc vương quốc, số hải ly ban đầu tại mỗi thành phố và các sự kiện trong kế hoạch, hãy tính kết quả của từng lần khảo sát.

Dữ liệu vào

• Dòng đầu chứa số nguyên \(N\).
• Dòng thứ hai chứa \(N-1\) số nguyên \(P_2,P_3,\ldots,P_N\).
• Dòng thứ ba chứa \(N\) số nguyên \(K_1,K_2,\ldots,K_N\).
• Dòng thứ tư chứa số nguyên \(Q\).
• Trong \(Q\) dòng tiếp theo, dòng thứ \(j\) mô tả sự kiện của ngày \(j\). Số nguyên đầu tiên là \(T_j\):
  • 1 X_j Y_j: xảy ra sự kiện di dời từ mức độ nguy hiểm \(X_j\) đến mức độ nguy hiểm \(Y_j\) theo mô tả trên.
  • 2 A_j L_j: xảy ra sự kiện nhập cư, số hải ly ở thành phố \(A_j\) tăng thêm \(L_j\).
  • 3 B_j: xảy ra sự kiện khảo sát tại thành phố \(B_j\).

Các số trên cùng một dòng được ngăn cách bởi dấu cách.

Dữ liệu ra

Với mỗi ngày \(j\) có \(T_j=3\), in số hải ly ở thành phố \(B_j\) tại thời điểm đó trên một dòng, theo thứ tự các sự kiện.

Ràng buộc

• \(2\le N\le 2000000\).
• \(1\le P_i<i\) (\(2\le i\le N\)).
• \(0\le K_i\le 100\) (\(1\le i\le N\)).
• \(1\le Q\le 2000000\).
• \(T_j\in\{1,2,3\}\) (\(1\le j\le Q\)).
• Nếu \(T_j=1\), thì \(0\le Y_j<X_j\le N-1\).
• Nếu \(T_j=2\), thì \(1\le A_j\le N\) và \(1\le L_j\le 100\).
• Nếu \(T_j=3\), thì \(1\le B_j\le N\).
• Có ít nhất một ngày \(j\) thỏa mãn \(T_j=3\).
• Tất cả giá trị trong dữ liệu vào đều là số nguyên.

Chấm điểm

Gọi \(D\) là mức độ nguy hiểm lớn nhất trong các thành phố.

1. \(4\) điểm: \(D=1\).
2. \(8\) điểm: \(N\le 20\).
3. \(13\) điểm: \(D\le 20\).
4. \(15\) điểm: Không có sự kiện \(T_j=2\) và có nhiều nhất \(5\) sự kiện \(T_j=3\).
5. \(15\) điểm: Có nhiều nhất \(5\) sự kiện \(T_j=3\).
6. \(27\) điểm: Không có sự kiện \(T_j=2\).
7. \(18\) điểm: Không có ràng buộc bổ sung.

Ví dụ

4
1 1 2
1 3 4 3
6
3 1
1 1 0
3 1
3 2
1 2 1
3 2

1
8
0
3

3
1 1
3 1 4
11
2 2 5
1 2 0
3 1
1 1 0
3 1
3 2
2 3 4
3 3
1 1 0
3 3
3 1

3
13
0
4
0
17

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

6
18
19
6
0

Nguồn

Bài Migration Plan, JOI 2024/2025, kỳ thi thứ tư của vòng tuyển chọn mùa xuân, do Ủy ban Olympic Tin học Nhật Bản (Japanese Committee for the International Olympiad in Informatics, JCIOI) công bố theo giấy phép CC BY-SA 4.0. Đây là bản dịch tiếng Việt của đề chính thức.