题目描述

有 $n$ 个多米诺骨牌，从左到右排列，每一个骨牌都有一个高度 $l_i$，向右推倒，它会直接向右倒下，如下图，倒下后该骨牌的顶端落在 $p_i+l_i$ 的位置，（$p_i$ 是它位于的坐标，即倒下时该骨牌不会发生移动）

在倒下过程中，骨牌会碰到其他骨牌，碰到的骨牌会向右倒，如下图，最左边的骨牌倒下会碰倒 $A,B,C$，$A,B,C$ 会倒下，但是不会直接碰到 $D$，但是 $D$ 会因为 $C$ 的倒下而碰倒。

现在给你 $n$ 个骨牌的坐标 $p_i$，和每个骨牌的高度 $l_i$。则一个骨牌能碰倒另一个骨牌当且仅当 $p_i+l_i≥p_j$。同时有 $q$ 个询问 $[l,r]$，问向右推到第 $l$ 个骨牌，最少需要多少代价让 $r$ 倒下。你可以临时增加某个骨牌的高度，增加 $1$ 个高度的代价是 $1$。

输入格式

第一行一个整数 $n$，$2\le n\le 2×10^{5}$。

接下来 $n$ 行，每行两个整数 $p_i,l_i$，$1\le p_{i},l_{i}<=10^{9}$，$p_{1}<p_{2}<...<p_{n-1}<p_{n}$。

接下来一个整数 $q$，$1\le q\le 2×10^{5}$。

接下来 $q$ 行，每行两个整数 $l,r$，表示询问。

输出格式

对于每个询问，在一行中输出答案。

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