Problem D
Traveling Merchant

Lithograph by Louis Haghe from an original by David Roberts, Wikipedia

There is a long east-west road which has $n$ towns situated along it, numbered $1$ to $n$ from west to east. All towns buy and sell the same kind of goodie. The value of a goodie fluctuates according to a weekly schedule. A town buys and sells a goodie at its value in that town on that particular day. At town $i$, the value of a goodie changes by $d_ i$ every day in the first half of a week, and changes by $-d_ i$ every day in the second half of a week. In other words, the value of a goodie at town $i$ is $v_ i$ on Mondays and Sundays, $v_ i + d_ i$ on Tuesdays and Saturdays, $v_ i + 2d_ i$ on Wednesdays and Fridays, and $v_ i + 3d_ i$ on Thursdays.

A merchant is making a business travel plan. His trip begins at a starting town $s$ and ends at a destination town $t$, visiting each town from $s$ to $t$ (inclusive) exactly once. The merchant starts the trip on a Monday. It takes him exactly one day to travel between adjacent towns and every day he travels to the next town on the path to the destination. He may buy exactly one goodie at a town along the trip and sell that goodie at a town he visits later. He can only buy once and sell once. The merchant would like to know the maximum possible profit of $q$ travel plans with different choices of town $s$ and town $t$.

Input

The first line of the input has a single integer $n$ ($2 \leq n \leq 10^5$). The next $n$ lines each have two integers. The $i$th line has $v_ i$ ($1 \leq v_ i \leq 10^9$) and $d_ i$ ($1 \leq v_ i + 3 d_ i \leq 10^9$). The next line has a single integer $q$ ($1 \leq q \leq 10^5$). The following $q$ lines each give a pair of integers $s$ and $t$ ($1 \leq s, t \leq n, s \neq t$), representing one travel plan from town $s$ to town $t$. If $s < t$ the merchant travels west to east, otherwise he travels east to west.

Output

For each travel plan, output the maximum profit the merchant can make on a single line. If the merchant cannot make any profit, output $0$.

5
1 2
2 1
5 0
4 -1
7 -2
5
1 5
5 1
3 1
4 5
5 4

4
2
2
1
0