QARRAY2 - Query on an array II

Adeeb is the promising programmer of BSMRSTU Smile.  One day he was solving a problem of RMQ(Range Sum Query). The solution he was written is given below:

 

int n, q ;
scanf("%d %d",&n, &q) ;
int a[n];
for(int i = 0 ; i < n ; ++i){
    scanf("%d",&a[i]) ;
}
int l, r ;
while(q--){
     scanf("%d %d",&l, &r) ;
     int res = 0 ;
     for(int i = l ; i <= r ; ++i){
         res += a[i] ;
      }
      printf("%d\n",res);
}

int n, q ;

scanf("%d %d",&n, &q) ;

int a[n];

for(int i = 0 ; i < n ; ++i){

    scanf("%d",&a[i]) ;

}

int l, r ;

while(q--){

     scanf("%d %d",&l, &r) ;

     int res = 0 ;

     for(int i = l ; i <= r ; ++i){

         res += a[i] ;

      }

      printf("%d\n",res);

}

 

As long as the the constraint of the problem was sufficiently small, his solution was correct and got accepted. But now, the constraint of the problem has been increased.
Today, he is trying to solve the newly modified problem by submitting the above-written code. But Alas! It's getting TLE(Time Limit Exceeded) verdict Cry . He became disappointed. He has no idea without the above-written code to solve the problem.
As a friend of Adeeb, you want to help him and he promised that if you help him to solve the problem then he will give you some candies Wink.

 

Input

There will be T test cases.

In every test case, you will be given n and q as the input.

The next line will contain n space separated integers, the value of the array a.

Constraint: 

1 <= T <= 10

1 <= n, q <= 10

1 <= l <= r <= n, 1 <= ai <= 109 .

Output

In every test case, print q lines of output, one integer for the corresponding query.

Example

Input:
1
5 2
1 2 3 4 5
1 4
2 5

Output:
10
14

Added by:Prodip
Date:2019-03-29
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All

hide comments
2019-03-30 06:19:40
Only Prefix Sum for Classic Problem ? Move this problem to tutorial
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.