CF500E.New Year Domino

Celebrating the new year, many people post videos of falling dominoes; Here's a list of them: https://www.youtube.com/results?search_query=New+Years+Dominos

User ainta, who lives in a 2D world, is going to post a video as well.

There are n dominoes on a 2D Cartesian plane. i-th domino (1 ≤ i ≤ n) can be represented as a line segment which is parallel to the y-axis and whose length is l__i. The lower point of the domino is on the x-axis. Let's denote the x-coordinate of the i-th domino as p__i. Dominoes are placed one after another, so _p_1 < _p_2 < ... < p__n - 1 < p__n holds.

User ainta wants to take a video of falling dominoes. To make dominoes fall, he can push a single domino to the right. Then, the domino will fall down drawing a circle-shaped orbit until the line segment totally overlaps with the x-axis.

Also, if the s-th domino touches the t-th domino while falling down, the t-th domino will also fall down towards the right, following the same procedure above. Domino s touches domino t if and only if the segment representing s and t intersects.

See the picture above. If he pushes the leftmost domino to the right, it falls down, touching dominoes (A), (B) and (C). As a result, dominoes (A), (B), (C) will also fall towards the right. However, domino (D) won't be affected by pushing the leftmost domino, but eventually it will fall because it is touched by domino (C) for the first time.

The picture above is an example of falling dominoes. Each red circle denotes a touch of two dominoes.

User ainta has q plans of posting the video. j-th of them starts with pushing the x__j-th domino, and lasts until the y__j-th domino falls. But sometimes, it could be impossible to achieve such plan, so he has to lengthen some dominoes. It costs one dollar to increase the length of a single domino by 1. User ainta wants to know, for each plan, the minimum cost needed to achieve it. Plans are processed independently, i. e. if domino's length is increased in some plan, it doesn't affect its length in other plans. Set of dominos that will fall except x__j-th domino and y__j-th domino doesn't matter, but the initial push should be on domino x__j.

为庆祝新年，许多人会发布多米诺骨牌倾倒的视频；以下是一些相关视频链接：https://www.youtube.com/results?search_query=New+Years+Dominos

生活在二维世界中的用户 ainta 也打算发布一段类似视频。

在二维笛卡尔坐标平面上有 $n$ 个多米诺骨牌。第 $i$ 个骨牌（$1 \le i \le n$）可表示为一条平行于 $y$ 轴的线段，其长度为 $l_i$，且该线段的底端位于 $x$ 轴上。记第 $i$ 个骨牌的 $x$ 坐标为 $p_i$。骨牌按从左到右顺序排列，因此满足 $p_1 < p_2 < \dots < p_{n-1} < p_n$。

用户 ainta 想拍摄一段多米诺骨牌倾倒的视频。为使骨牌倾倒，他可以向右推动某一个骨牌。随后，该骨牌将沿圆弧轨迹倒下，直至整个线段完全与 $x$ 轴重合。

此外，若第 $s$ 个骨牌在倒下过程中触碰到第 $t$ 个骨牌，则第 $t$ 个骨牌也会随之向右倾倒，并遵循上述相同过程。当且仅当代表骨牌 $s$ 和 $t$ 的线段相交时，称骨牌 $s$ 触碰骨牌 $t$。

参见上图：若推动最左侧的骨牌向右，它将倒下并触碰到骨牌 (A)、(B) 和 (C)，从而导致骨牌 (A)、(B)、(C) 也依次向右倾倒。然而，骨牌 (D) 并不会因最左侧骨牌的初始推动而倾倒；但它最终仍会倒下，因为这是它首次被骨牌 (C) 触碰所致。

上图是多米诺骨牌连锁倾倒的一个示例。每个红色圆圈表示两个骨牌之间的一次触碰。

用户 ainta 共有 $q$ 个视频发布计划。第 $j$ 个计划从推动第 $x_j$ 个骨牌开始，持续至第 $y_j$ 个骨牌倒下为止。但有时该计划无法实现，此时他必须加长某些骨牌。将单个骨牌长度增加 1 单位需花费 1 美元。ainta 想知道：对每个计划，实现该计划所需的最小花费是多少？各计划相互独立，即某个计划中加长的骨牌长度不会影响其他计划中该骨牌的原始长度。除第 $x_j$ 个和第 $y_j$ 个骨牌外，其余哪些骨牌会倒下并不重要，但初始推动必须作用于第 $x_j$ 个骨牌。

The first line contains an integer n (2 ≤ n ≤ 2 × 105)— the number of dominoes.

Next n lines describe the dominoes. The i-th line (1 ≤ i ≤ n) contains two space-separated integers p__i, l__i (1 ≤ p__i, l__i ≤ 109)— the x-coordinate and the length of the i-th domino. It is guaranteed that _p_1 < _p_2 < ... < p__n - 1 < p__n.

The next line contains an integer q (1 ≤ q ≤ 2 × 105) — the number of plans.

Next q lines describe the plans. The j-th line (1 ≤ j ≤ q) contains two space-separated integers x__j, y__j (1 ≤ x__j < y__j ≤ n). It means the j-th plan is, to push the x__j-th domino, and shoot a video until the y__j-th domino falls.

第一行包含一个整数 $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$）—— 分别表示第 $i$ 块多米诺骨牌的 $x$ 坐标及其长度。保证 $p_1 < p_2 < \dots < p_{n-1} < p_n$。

下一行包含一个整数 $q$（$1 \leq q \leq 2 \times 10^5$）—— 计划的数量。

接下来的 $q$ 行描述这些计划。第 $j$ 行（$1 \leq j \leq q$）包含两个以空格分隔的整数 $x_j$、$y_j$（$1 \leq x_j < y_j \leq n$）。它表示第 $j$ 个计划为：推倒第 $x_j$ 块多米诺骨牌，并拍摄视频直至第 $y_j$ 块多米诺骨牌倒下。

For each plan, print a line containing the minimum cost needed to achieve it. If no cost is needed, print 0.

对于每个方案，输出一行，包含实现该方案所需的最小成本。如果不需要任何成本，则输出 0。

Consider the example. The dominoes are set like the picture below.

Let's take a look at the 4th plan. To make the 6th domino fall by pushing the 2nd domino, the length of the 3rd domino (whose x-coordinate is 4) should be increased by 1, and the 5th domino (whose x-coordinate is 9) should be increased by 1 (other option is to increase 4th domino instead of 5th also by 1). Then, the dominoes will fall like in the picture below. Each cross denotes a touch between two dominoes.

考虑如下示例。多米诺骨牌的初始摆放方式如下面图片所示。

我们来看第 4 种方案。为了通过推倒第 2 块骨牌使第 6 块骨牌倒下，需要将第 3 块骨牌（其 x 坐标为 4）的长度增加 1，同时将第 5 块骨牌（其 x 坐标为 9）的长度也增加 1（另一种可行方案是：不增加第 5 块骨牌的长度，而改为将第 4 块骨牌的长度增加 1）。此时，骨牌倒下的过程如下面图片所示。图中每个“×”表示两块骨牌之间发生的一次接触。