All Tracks Data Structures Arrays 1-D Problem

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

Best Submission

Similar Problems

Contributors

This Problem was Asked in

Initializing Code Editor...
Notifications
View All Notifications

?