Giải bài trực tuyến Học viện Công nghệ Bưu chính Viễn Thông

Domino là một trò chơi mà ở đây, người chơi sắp xếp các quân domino cạnh nhau sau đó tác động để làm đổ quân domino đầu tiên, quân domino này sẽ tiếp tục làm đổ quân domino thứ 2, .. cho đến khi tất cả các quân domino đổ hết.

Bây giờ, chúng ta sẽ mô phỏng lại trò chơi này trên mặt phẳng 2D.

Có n quân domino trên mặt phẳng, quân thứ i (1<= i <= n) được đại diện bởi một đoạn thẳng song song với trục y và có độ dài là l[i], đặt tại vị trí p[i].  Ta sẽ có p[1] < p[2] < … < p[n].

Người chơi đang muốn quay lại một đoạn video quay lại khi domino bị đổ. VIệc xem domino đổ thực sự rất thích thú. Để làm cho các domino đổ, người chơi đẩy một domino sang bên phải, quân domino sẽ đổ xuống, tại thành một quỹ đạo tròn cho đến khi nó nằm hoàn toàn trên trục x.

Cũng thế, nếu domino s làm đổ domino t thì domino t cũng sẽ đổ xuống về bên phải. Và domino t cũng sẽ lặp lại tương tự mô tả như trên. Domino s làm đổ domino t khi và chỉ khi 2 chúng có điểm tiếp xúc.

Nhìn vào hình phía trên, nếu chúng ta đổ thanh domino trái nhất sang bên phải thì nó sẽ làm đổ các thanh (A), (B), (C). Và theo đó, các thanh domino này cũng sẽ tiếp tục đổ sang phía bên phải.Mặc, domino (D) không bị chạmbởi domino phía trái nhất nhưng nó vấn sẽ đổ bởi bị domino (C) va vào.

Bức ảnh trên là một ví dụ về việc đổ domino. Mỗi vòng tròn màu đỏ biểu thị một điểm va chạm giữa 2 domino.

Người chơi có q kế hoạch làm video, trong đó video thứ i sẽ bắt đầu quay khi domino thứ x bị đẩy cho tới khi domino thứ y đổ xuống. Nhưng đôi khi, kế hoạch quay không thể thực hiện, bởi vậy, người chơi sẽ tăng độ dài của một số domino. Để tăng độ dài của một domino lên 1, chi phí sẽ là 1 $. Vì vậy, người chơi muốn biết rằng, với mỗi kế hoạch quay như vậy, chi phí ít nhất phải bỏ ra là bao nhiêu để có thể thực hiện được video. Việc tăng độ dài của domino ở kế hoạch này sẽ không được áp dụng ở kế hoạch khác.

Input

Dòng đầu tiên chứa một số nguyên n (2<= n<= 2.10^5) – Số quân domino.

n dòng tiếp theo sẽ mô tả các quân domino, dòng thứ i (1<= i<= n) sẽ gồm 2 số nguyên p[i], l[i] (1<= p[i], l[i]<= 10^9). Lần lượt là tọa độ và độ dài của quân domino i. Đầu vào đảm bảo rồi p[1] < p[2] < … < p[n].

Dòng tiếp theo là số nguyên q (1<= q<= 2.10^5) – Số kế hoạch.

q dòng tiếp theo sẽ mô tả các kế hoạch. Dòng thứ I (1<= i<= q) gồm 2 số nguyên x[i], y[i] (1<= x[i] < y[i]<= n) có nghĩa cảnh quay sẽ quay từ lúc domino thứ x[i] bị đẩy sang phải và kết thúc khi domino thứ y[i] đổ xuống.

Output

Với mỗi kế hoạch, in ra một dòng chi phí ít nhất mà người chơi phải trả để thực hiện kế hoạch thành công.

Example

Input:
6
1 5
3 3
4 4
9 2
10 1
12 1
4
1 2
2 4
2 5
2 6

Output:
0
1
1
2

Giải thích:
Các domino sẽ được mô tả như sau.
 
Nhìn vào kế hoạch thứ 4, chúng ta cần làm đổ domino thứ 2 cho tới domino thứ 6.  Ta thấy rằng, cần tăng độ dài của domino thứ 3 và domino thứ 5 lên 1 (Một lựa chọn khác là ta có thể tăng độ dài domino thứ 4 lên 1 thay vì tăng domino thứ 5 lên 1). Ở các hình sau, mỗi gạch chéo sẽ biểu thị va chạm giữa 2 domino.