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\%~.

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 1\,000\,000~

~1 \le L \le R \le N~

~0 \le A_i \le 100~

Subtask 1 [50%]

~1 \le N, Q \le 1\,000~

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