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}\\\)