Infinite arrays
/

## 1-D Array, Arrays, Data Structures, One-dimensional

Problem
Editorial
Analytics

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

SAMPLE INPUT
1
3
4 1 5
3
1 3 9
4 7 10

SAMPLE OUTPUT
14 19 9

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

## This Problem was Asked in

Initializing Code Editor...