Problem 1005. -- 多米诺骨牌

1005: 多米诺骨牌

Time Limit: 2 Sec  Memory Limit: 256 MB
Submit: 4622  Solved: 11
[Submit][Status][Web Board]

Description

新格尔王国的国王,最近非常喜欢玩多米诺骨牌。

可以将多米诺视为2D平面上的一些线段(可以视为在这个王国中多米诺骨牌超级薄),在将骨牌推倒的时候,扫过一个扇形区域,最终覆盖在x轴上,如下图。

当然,如果两个骨牌离得足够的近,在倒下的时候,会将其他的骨牌砸倒,如下图,倒下的骨牌会让(A)(B)(C)(D)倒下。

在骨牌倒下的时候,一个骨牌只要被其他骨牌的顶端碰到,就会倒下,即使是在完全倒下的时候碰到的,如下图,两个红色的圈都表示已经碰到,所以第三个骨牌也会倒下。

最近国王,还有另一项爱好摄影,他打算将某些部分倒下后的状态照下来。他一共想照q张照片,对于第j张照片从 xj个骨牌开始,到yj个骨牌。但是由于一些骨牌短了一些,有些照片里面的骨牌并不能全部倒下。但是如果将其中的某些骨牌延长一段,就可以让这一张照片里的骨牌全部倒下。每延长一个单位长度,需要花费$1,国王想知道,对于每张照片,他需要花费多少钱,使得照片中的骨牌都是倒下的。

Input

第一行一个整数n (2 ≤ n ≤ 2 × 105)多米诺骨牌的数量

接下来n行描述了骨牌的信息。 第i行(1 ≤ in) 包含两个整数 pili (1 ≤ pi, li ≤ 109) ,依次是骨牌的位置(在x轴上的坐标)和长度。数据保证 p1 < p2 < ... < pn - 1 < pn.

下一行有一个整数 q (1 ≤ q ≤ 2 × 105) 国王想照的相片的数量。

接下来q行描述了照片的信息。第j行包含两个整数, xjyj (1 ≤ xj < yjn). 这个代表第j张照片,国王想拍摄第xj个骨牌到第yj.个骨牌倒下的照片(包括第yj.个骨牌)。

 

Output

共q行。对于每个输出一行,包含一个整数,表示完成拍摄该照片的最小花费,如果无花费,输出0。

Sample Input

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

Sample Output

0
1
1
2

HINT

Source

[Submit][Status]