Farmer John is distributing haybales across the farm!

Farmer John's farm has $N$ $(1\le N\le 2\cdot 10^5)$ barns, located at integer points $x_1,\dots, x_N$ $(0 \le x_i \le 10^6)$ on the number line. Farmer John's plan is to first have $N$ shipments of haybales delivered to some integer point $y$ $(0 \le y \le 10^6)$ and then distribute one shipment to each barn.

Unfortunately, Farmer John's distribution service is very wasteful. In particular, for some $a_i$ and $b_i$ $(1\le a_i, b_i\le 10^6)$, $a_i$ haybales are wasted per unit of distance left each shipment is transported, and $b_i$ haybales are wasted per unit of distance right each shipment is transported. Formally, for a shipment being transported from point $y$ to a barn at point $x$, the number of haybales wasted is given by

Given $Q$ $(1\le Q\le 2\cdot 10^5)$ independent queries each consisting of possible values of $(a_i,b_i)$, please help Farmer John determine the fewest amount of haybales that will be wasted if he chooses $y$ optimally.

SAMPLE INPUT:

5
1 4 2 3 10
4
1 1
2 1
1 2
1 4

SAMPLE OUTPUT:

11
13
18
30

For example, to answer the second query, it is optimal to select $y=2$. Then the number of wasted haybales is equal to $2(2-1)+2(2-2)+1(3-2)+1(4-2)+1(10-2)=1+0+1+2+8=13$.

Problem credits: Benjamin Qi