You are given an array of n numbers and q queries. For each query you have to print the floor of the expected value(mean) of the subarray from L to R.

**Input :**

First line contains two integers N and Q denoting number of array elements and number of queries.

Next line contains N space seperated integers denoting array elements.

Next Q lines contain two integers L and R(indices of the array).

**Output :**

print a single integer denoting the answer.

**Constraints :**

- 1<= N ,Q,L,R <= 10^6
- 1<= Array elements <= 10^9

SAMPLE INPUT | SAMPLE OUTPUT |

5 3 1 2 3 4 5 1 3 2 4 2 5 | 2 3 3 |

```
#include <stdio.h>
int main()
{
unsigned long N,Q,L,R,*A,t;
scanf("%d%d", &N,&Q);
A = (unsigned long*)calloc(N+1,sizeof(unsigned long));
for(int i=1;i<=N;i++)
{
scanf("%ld",&t);
A[i] = t + A[i-1];
}
for(int i=0;i<Q;i++)
{
scanf("%ld%ld",&L,&R);
printf("%ld\n",(A[R]-A[L-1])/(1+R-L));
}
return 0;
}
```