Adeeb is the promising programmer of BSMRSTU .  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);

}

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  . 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 .

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 <= a_i <= 10⁹ .

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