E. New Year Domino
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
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 arendominoes on a 2D Cartesian plane.i-th domino (1≤i≤n) can be represented as a line segment which is parallel to they-axis and whose length isli. The lower point of the domino is on thex-axis. Let’s denote thex-coordinate of thei-th domino aspi. Dominoes are placed one after another, sop1<p2<…<pn-1<pnholds.
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 thes-th domino touches thet-th domino while falling down, thet-th domino will also fall down towards the right, following the same procedure above. Dominostouches dominotif and only if the segment representingsandtintersects.
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 hasqplans of posting the video.j-th of them starts with pushing thexj-th domino, and lasts until theyj-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 by1. 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 exceptxj-th domino andyj-th domino doesn’t matter, but the initial push should be on dominoxj.
Input
The first line contains an integern(2≤n≤2×105)— the number of dominoes.
Nextnlines describe the dominoes. Thei-th line (1≤i≤n) contains two space-separated integerspi,li(1≤pi,li≤109)— thex-coordinate and the length of thei-th domino. It is guaranteed thatp1<p2<…<pn-1<pn.
The next line contains an integerq(1≤q≤2×105) — the number of plans.
Nextqlines describe the plans. Thej-th line (1≤j≤q) contains two space-separated integersxj,yj(1≤xj<yj≤n). It means thej-th plan is, to push thexj-th domino, and shoot a video until theyj-th domino falls.
Output
For each plan, print a line containing the minimum cost needed to achieve it. If no cost is needed, print 0.
Sample test(s)
input
61 53 34 49 210 112 141 22 42 52 6
output
0112
Note
Consider the example. The dominoes are set like the picture below.
人生最好的旅行，就是你在一个陌生的地方，
