To get into university, you are required to have a high average, so your advisor offers you a challenge:

If you can answer my $Q$ queries, I will boost your average by $1\mathrm{\%}$.

Each query will consist of $[L,R]$, meaning your advisor wants you to query the average of courses $L,L+1,\dots ,R$ rounded down to the nearest integer.

Input Specification

The first line will contain $N$ and $Q$, the number of courses you are currently taking and the number of queries.

The second line will contain $N$ space-separated integers, $A_i$, your average in the $i^{\text{th}}$ course.

The next $Q$ lines will contain $L$ and $R$, a query for the average of your courses in $[L,R]$.

Note: Fast I/O might be required to fully solve this problem (e.g., BufferedReader for Java).

Output Specification

Output $Q$ lines, the answer to each query rounded down to the nearest integer.

Constraints

For all subtasks:

$1\le N,Q\le 1000000$

$1\le L\le R\le N$

$0\le A_i\le 100$

Subtask 1 [50%]

$1\le N,Q\le 1000$

Subtask 2 [50%]

No additional constraints.

Sample Input

5 3
100 50 0 75 90
1 2
2 3
2 5

Sample Output

75
25
53