| Good Bye 2014 |
|---|
| Закончено |
Многие празднуют Новый год, публикуя видео с падающими доминошками. Ознакомиться с подобными видео можно здесь: https://www.youtube.com/results?search_query=New+Years+Dominos
Пользователь ainta, живущий в двухмерном мире, тоже хочет опубликовать видео.
Дано n доминошек на плоскости с декартовой системой координат. i-ю доминошку (1 ≤ i ≤ n) можно представить как параллельный оси y отрезок длины li. Нижняя точка отрезка находится на оси x. Обозначим x-координату i-й доминошки как pi. Доминошки ставятся друг за другом, таким образом, выполняется условие p1 < p2 < ... < pn - 1 < pn.
Пользователь ainta хочет снять видео с падающими доминошками. Чтобы доминошки попадали, он может толкнуть одну доминошку вправо. Тогда доминошка будет падать по круговой орбите, пока её отрезок полностью не коснётся оси x.
Также, если s-я доминошка, падая, задевает t-ю доминошку, то и t-я доминошка упадет направо, таким же описанным выше образом. Доминошка s касается доминошки t тогда и только тогда, когда отрезки, образующие s и t, пересекаются.
Рассмотрим рисунок, данный выше. Если толкнуть крайнюю слева доминошку вправо, она упадет, затронув доминошки (A), (B) и (C). В результате, доминошки (A), (B), (C) также упадут вправо. Хотя доминошка (D) не будет задета при падении крайней доминошки слева, она в итоге также упадет, потому что её толкнет доминошка (C).
Приведенный выше рисунок демонстрирует пример падающих доминошек. Каждый красный кружок означает соприкосновение двух доминошек.
У пользователя ainta есть q планов публикации видео. j-й из них начинается с того, что мы толкаем xj-ю доминошку и заканчивается с падением yj-й доминошки. Но порой реализовать такой план невозможно, в связи с чем требуется удлинить некоторые доминошки. Увеличить длину одной доминошки на 1 единицу стоит один доллар. Пользователь ainta хочет знать для каждого плана минимальную цену, необходимую для достижения цели. Планы обрабатываются независимо друг от друга, то есть если длина доминошки увеличивается при каком-либо плане, это не влияет на длину этой доминошки в других планах. Множество доминошек, которые упадут помимо xj-й и yj-й, не имеет значения, но исходный удар должен наноситься именно по доминошке xi.
В первой строке содержится целое число n (2 ≤ n ≤ 2 × 105)— количество доминошек.
В следующих n строках описываются доминошки. В i-й строке (1 ≤ i ≤ n) записано два целых числа через пробел pi, li (1 ≤ pi, li ≤ 109)— x-координата и длина i-й доминошки. Гарантируется, что p1 < p2 < ... < pn - 1 < pn.
В следующей строке содержится целое число q (1 ≤ q ≤ 2 × 105) — количество планов.
Следующие q строк описывают планы. В j-ой строке (1 ≤ j ≤ q) записано два целых числа через пробел xj, yj (1 ≤ xj < yj ≤ n). Это означает, что j-ый план заключается в том, чтобы толкнуть xj-ю доминошку и снимать видео, пока не упадет yj-я доминошка.
Для каждого плана выведите строку, содержащую минимальную стоимость, необходимую для его реализации. Если никаких затрат не требуется, выведите 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
Рассмотрим пример. Доминошки расставлены как на картинке ниже.
Посмотрим на 4-й план. Для того, чтобы 2-я доминошка привела к падению 6-й, третью доминошку (с x-координатой 4) надо увеличить на 1, и 5-ю доминошку (с x-координатой 10) надо увеличить на 1 (альтернативный вариант — вместо 5-й доминошки можно также увеличить 4-ю доминошку на 1). Затем доминошки попадают так, как указано на картинке ниже. Каждый крестик обозначет соприкосновение двух доминошек.
