Công ty SUS bao gồm ~N~ bộ phận được tổ chức thành cấu trúc cây, đánh số từ 1 đến ~N~. Bộ phận 1 là gốc. Nếu ~i~ là điểm trong cây con của ~j~, thì ~i~ là bộ phận con của ~j~. Ban đầu công ty có ~K~ nhân viên xuất sắc, mỗi người có mã định danh, bộ phận gốc và giá trị năng lực.

Để tối ưu hóa hiệu suất, Hưng thực hiện điều động nhân sự: nhân viên có thể được điều động đến một bộ phận con của bộ phận gốc hoặc giữ nguyên. Sau đó, tại mỗi bộ phận, nhân viên có năng lực cao nhất sẽ làm lãnh đạo và đóng góp giá trị năng lực đó cho công ty. Nếu bộ phận không có nhân viên, đóng góp là 0. Hiệu suất công ty là tổng đóng góp của tất cả các bộ phận.

Hưng cần mô phỏng quá trình phân bổ nhân sự khi có các sự kiện:

• Sự kiện 1: Thêm một nhân viên mới với mã định danh tăng dần, bộ phận gốc ~x~ và năng lực ~v~.
• Sự kiện 2: Một nhân viên có mã định danh ~id~ bị sa thải.

Yêu cầu: Tính hiệu suất tối đa của công ty tại trạng thái bắt đầu và sau mỗi sự kiện.

Input

• Dòng đầu tiên chứa ~N, K, M~ (~1 \le N \le 10^5, 1 \le K \le 10^5, 0 \le M \le 10^5~).
• Dòng tiếp theo chứa ~N-1~ giá trị, giá trị thứ ~i~ là bộ phận cấp trên của bộ phận ~i+1~.
• ~K~ dòng tiếp theo chứa ~x_i, v_i~ là bộ phận gốc và năng lực của nhân viên thứ ~i~.
• ~M~ dòng tiếp theo, mỗi dòng là một sự kiện: 1 x v hoặc 2 id.

Output

• In ra ~M+1~ dòng, mỗi dòng là hiệu suất tối đa của công ty tại trạng thái tương ứng.