You are given an array $A$ of size $N$. You have also defined an array $B$ as the concatenation of array $A$ for infinite number of times. 
For example, if $A=\{A_1, A_2, A_3\}$, then $B= \{A_1, A_2, A_3, A_1, A_2, A_3,.....\}$.

Now, you are given $Q$ queries. Each query consists of two integers, $L_i$ and $R_i$. Your task is to calculate the sum of the subarray of $N$ from index $L_i$ to $R_i$.

Note: As the value of this output is very large, print the answer as modulus $10^9+7$.

Input format

• First line: $T$ denoting the number of test cases
• For each test case:
  • First line: Contains $N$, the size of the array
  • Second line: Contains $N$ space-separated integers corresponding to $A_i$
  • Third line: Contains $Q$ denoting the number of queries
  • Fourth line: Contains $Q$ space-separated integers corresponding to $L_i$
  • Fifth line: Contains $Q$ space-separated integers corresponding to $R_i$

Output format

For each test case, print $Q$ space-separated integers that denote the answers of the provided $Q$ queries. Print the answer to each test case in a new line.

Constraints

$1\le T\le100\\ 1\le N\le 10^4\\ 1\le Q\le 10^4\\ 1\le A_i\le 10^9\\ 1\le L_i\le R_i\le 10^{18}\\$