Dốc Trượt Tuyết

Một ngọn núi có $N$ điểm dừng chân đánh số từ $1$ đến $N$ theo thứ tự tăng dần độ cao. Mỗi điểm $i>1$ có một đường trượt tuyết đến điểm $p_i$ ($p_i<i$) với độ khó $d_i$ và mức vui $e_i$.

Có $M$ người bạn muốn trượt tuyết. Mỗi người bắt đầu tại một điểm và trượt xuống qua các đường cho đến khi đến điểm 1. Người thứ $j$ có kỹ năng $s_j$ và lòng can đảm $c_j$: họ chỉ được đi tối đa $c_j$ đường có $d_i>s_j$.

Tìm tổng mức vui lớn nhất cho mỗi người.

Dữ liệu vào

• Dòng 1: Số nguyên $N$.
• $N-1$ dòng tiếp theo (cho $i$ từ $2$ đến $N$): Ba số nguyên $p_i$, $d_i$, $e_i$.
• Dòng tiếp: Số nguyên $M$.
• $M$ dòng tiếp: Hai số nguyên $s_j$, $c_j$.

Dữ liệu ra

• $M$ dòng, mỗi dòng là tổng mức vui tối đa.

Ràng buộc

• $1\le N\le {10}^5$
• $1\le M\le {10}^5$
• $0\le d_i,e_i,s_j\le {10}^9$
• $0\le c_j\le 10$

Ví dụ