SOLVE

LATER

Infinite arrays

/

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

Explanation

\(A=\{4,1,5\}\\ B=\{4,1,5,4,1,5,4,1,5,4,1,5,...\} \)

**Query #1: **

L=1, R=4, elements are {4,1,5,4}. Sum=4+1+5+4=14.

**Query #2:**

L=3, R=7, elements are {5,4,1,5,4}. Sum=5+4+1+5+4=19.

**Query #3:**

L=9, R=10, elements are {5,4}. Sum=5+4=9.

Time Limit:
3.0 sec(s)
for each input file.

Memory Limit:
256 MB

Source Limit:
1024 KB

Initializing Code Editor...