Bức thư từ Kid đã được gửi đến và vụ trộm thế kỷ tại thành phố Beika sắp bắt đầu. Nội dung bức thư ghi rằng có tổng cộng ~N~ địa điểm bị nhắm đến. Thanh tra Nakamori và các cộng sự phải tìm cách di dời các bảo vật quý hiếm ở các địa điểm này. Ở mỗi địa điểm thứ ~i~, bảo vật có trọng lượng ~W_i~ và mang giá trị ~V_i~.

Tuy nhiên, sở cảnh sát vừa đưa ra danh sách gồm ~Q~ kế hoạch, mỗi kế hoạch ~j~ yêu cầu chỉ được di dời các bảo vật nằm ở các địa điểm trong khoảng từ ~L_j~ đến ~R_j~, đồng thời do vấn đề vận chuyển nên tổng trọng lượng các bảo vật không được vượt quá ~Z_j~.

Bạn hãy giúp thanh tra Nakamori tính toán rằng với mỗi kế hoạch, tổng giá trị lớn nhất các bảo vật có thể di dời là bao nhiêu.

Input

• Dòng đầu tiên chứa số nguyên ~N~ (~1 \le N \le 2.10^4~).
• ~N~ dòng tiếp theo, dòng thứ ~i~ chứa hai số nguyên ~W_i~ và ~V_i~ ~(1 \le V_i \le 10^9)~.
• Dòng tiếp theo chứa số nguyên ~Q~ (~1 \le Q \le 2.10^5~).
• ~Q~ dòng tiếp theo, dòng thứ ~j~ chứa ba số nguyên ~L_j~, ~R_j~ và ~Z_j~ ~(1 \le L_j \le R_j \le N)~.

Output

• Với mỗi kế hoạch, in ra trên một dòng là tổng giá trị lớn nhất các bảo vật có thể di dời.

Samples

Sample Input 1

4
3 2
1 3
2 6
4 1
3
1 3 3
2 4 7
1 4 7

Sample Output 1

9
10
11

Sample Input 2

5
1 10
2 12
3 13
4 14
5 15
7
1 5 9
1 5 10
1 5 11
1 5 12
1 5 13
1 5 14
1 5 15

Sample Output 2

39
49
50
51
52
54
64

Scoring

• Subtask ~1~ với ~21\%~ số điểm: ~N \le 20~; ~Q \le 10~; ~W_i, Z_j \le 10^9~
• Subtask ~2~ với ~29\%~ số điểm: ~Q \le 10~; ~W_i, Z_j \le 500~
• Subtask ~3~ với ~19\%~ số điểm: ~L_i = 1~ với mọi ~1 \le i \le N~; ~W_i, Z_j \le 500~
• Subtask ~4~ với ~31\%~ số điểm: ~W_i, Z_j \le 500~

Notes

Trong ví dụ đầu tiên, tổng giá trị lớn nhất các bảo vật được xác định như sau:

• Ở kế hoạch đầu tiên, nếu lựa chọn bảo vật thứ ~1~, tổng giá trị sẽ là ~2~, tuy nhiên nếu lựa chọn hai bảo vật thứ ~2~ và thứ ~3~, tổng giá trị sẽ là ~3+6=9~.
• Ở kế hoạch thứ hai, có thể lựa chọn cả ba bảo vật thứ ~2~, ~3~ và ~4~, tổng giá trị là ~3+6+1=10~.
• Ở kế hoạch thứ ba, ba bảo vật thứ ~1~, ~2~ và ~3~ được lựa chọn và tổng giá trị là ~2+3+6=11~.