Công ty Chim có ~n~ thành viên được phân nhiều quyền hạn khác nhau, trong đó người thứ ~1~ là sếp tổng. Mỗi thành viên trừ sếp tổng đều có chính xác một người ~p_i~ là sếp trực tiếp của họ. Người ~u~ được gọi là nằm dưới quyền hạn của người ~v~ nếu như người ~v~ là sếp trực tiếp của người ~u~, hoặc sếp trực tiếp của người ~u~ nằm dưới quyền hạn của người ~v~. Hay nói cách khác, cách phân quyền hạn của công ty Chim có cấu trúc như một đồ thị dạng cây.

Công ty đang có ~m~ phương án tăng lương cho các thành viên. Ở phương án thứ ~i~, công ty sẽ tăng lương cho người thứ ~u_i~ và tất cả các thành viên nằm dưới quyền hạn của người thứ ~u_i~ lên ~w_i~ đồng. Để đánh giá được độ thích hợp của những phương án này, công ty đặt ra ~q~ khảo sát. Ở khảo sát thứ ~i~, công ty muốn kiểm tra rằng nếu như chỉ có những phương án thứ ~t~ ~\forall t \in [L_i, R_i]~ được thực thi, người thứ ~u_i~ được tăng lương tổng cộng bao nhiêu đồng. Bạn hãy giúp công ty tìm ra câu trả lời cho ~q~ khảo sát này nhé.

Input

• Dòng đầu chứa ba số nguyên dương ~n, m, q~ ~(1 \le n, m, q \le 10^5)~.
• Dòng thứ hai chứa ~n - 1~ số nguyên dương ~p_2, p_3, \ldots, p_n~ ~(1 \le p_i \le n)~.
• ~m~ dòng tiếp theo, dòng thứ ~i~ chứa hai số nguyên dương ~u_i, w_i~ ~(1 \le u_i \le n, \ 1 \le w_i \le 10^9)~.
• ~q~ dòng cuối cùng, dòng thứ ~i~ chứa ba số nguyên dương ~L_i, R_i, u_i~ ~(1 \le L_i \le R_i \le m, \ 1 \le u_i \le n)~.

Dữ liệu bảo đảm cấu trúc phân quyền của công ty là một đồ thị dạng cây.

Output

• In ra ~q~ dòng, dòng thứ ~i~ chứa câu trả lời cho khảo sát thứ ~i~.

Subtask

• Subtask ~1~ (~20\%~ số điểm): ~n, m, q \le 500~
• Subtask ~2~ (~20\%~ số điểm): ~L_i = 1, R_i = m \ \forall i \in [1, q]~
• Subtask ~3~ (~20\%~ số điểm): ~n, m, q \le 5000~
• Subtask ~4~ (~20\%~ số điểm): ~p_i = i - 1 \ \forall i \in [2, n]~
• Subtask ~5~ (~20\%~ số điểm): Không có ràng buộc gì thêm

Sample input 1

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

Sample output 1

17
0
6
6