Problem Statement

You are given integer sequences $A=(A_1,A_2,\ldots,A_N)$ and $B=(B_1,B_2,\ldots,B_N)$ of length $N$, and integer sequences $X=(X_1,X_2,\ldots,X_K)$ and $Y=(Y_1,Y_2,\ldots,Y_K)$ of length $K$.

For each $k=1,2,\ldots,K$, find $\displaystyle \sum_{i=1}^{X_k} \sum_{j=1}^{Y_k} |A_i-B_j|$.

Constraints

• $1\le N\le 10^5$
• $0\le A_i,B_j\le 2\times 10^8$
• $1\le K\le 10^4$
• $1\le X_k,Y_k\le N$
• All input values are integers.

Input

The input is given from Standard Input in the following format:

N
A_1 A_2 \ldots A_N
B_1 B_2 \ldots B_N
K
X_1 Y_1
X_2 Y_2
\vdots
X_K Y_K

Output

Print $K$ lines. The $i$-th line $(1\le i\le K)$ should contain the answer for $k=i$.