Bạn được cho ~N~ thùng nước, thùng nước thứ ~i~ nằm ở vị trí ~X[i]~ và chứa ~W[i]~ lít nước ~(1 \le i \le n)~, các vị trí của những thùng nước được sắp xếp tăng dần . Chí phí vận chuyển thùng nước thứ ~i~ về thùng nước thứ ~j~ là ~W[i] \times (X[j] - X[i] ) ~ ~(1 \le i < j \le N)~.

Bạn có ~Q~ truy vấn mỗi truy vấn bạn cần phải tìm tổng chi phí để vận chuyển các thùng nước thứ ~l~ đến ~r-1~ về thùng nước thứ ~r~.

Input

Dòng đầu tiên chứa một số nguyên ~N~ ~(1 \le N \le 10^{6})~. ~N~ dòng tiếp theo, dòng thứ ~i~ ghi hai số cách nhau bới dấu cách là tọa độ ~X[i]~ và lượng nước ~W[i]~ của thùng nước thứ ~i~ ~(1 \le X[i] , W[i] \le 10^{6})~ .

Dòng thứ ~N + 1~ số lượng truy vấn ~Q~ ~(1 \le Q \le 10^{6})~. ~Q~ dòng tiếp theo mỗi dòng chứa hai số ~L~ và ~R~ cách nhau bởi dấu cách là dữ liệu cho từng truy vấn .

Output

Ghi ra ~Q~ dòng lần lượt là câu trả lời của từng truy vấn .

Subtask

• ~50\%~ số test có ~ 1 \le N , Q \le 1000~.
• Còn lại không có điều kiện gì thêm

Sample Input

3 
1 20
2 20
3 20
2 
1 2
1 3

Sample Output

20 
60 

Note

Truy vấn ~1~ ~(2 - 1) \times 20~.

Truy vấn ~2~ ~(3 - 1) \times 20 + (3 - 2) \times 20~.