题目描述

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

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

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

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

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

输入格式

第一行一个整数 $n$ $(2 \leq n \leq 2 \times 10^5)$，多米诺骨牌的数量。

接下来 $n$ 行描述了骨牌的信息。第 $i$ 行 $(1 \leq i \leq n)$ 包含两个整数 $p_i$, $l_i$ $(1 \leq p_i, l_i \leq 10^9)$，依次是骨牌的位置（在 $x$ 轴上的坐标）和长度。数据保证 $p_1 < p_2 < \dots < p_{n - 1} < p_n$。

下一行有一个整数 $q$ $(1 \leq q \leq 2 \times 10^5)$，国王想照的相片的数量。

接下来 $q$ 行描述了照片的信息。第 $j$ 行包含两个整数 $x_j$, $y_j$ $(1 \leq x_j < y_j \leq n)$。这个代表第 $j$ 张照片，国王想拍摄第 $x_j$ 个骨牌到第 $y_j$ 个骨牌倒下的照片（包括第 $y_j$ 个骨牌）。

输出格式

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

样例输入

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

样例输出

0
1
1
2