Derek is a finance bro professional investor researching stocks. One particular stock has been public for ~N~ days. Each day the stock was valued at ~a_i~ dollars.

For ~Q~ ranges of days ~[L, R]~, he wants to know the mean price of the stock, rounding down. Unfortunately, his software doesn't have this option available. Can you help Derek answer his queries?

Constraints

For all subtasks,

~1 \le N, Q \le 2 \times 10^5~

~1 \le a_i \le 10^4~

Subtask 1 [10%]

~1 \le N, Q \le 2 \times 10^3~

Subtask 2 [90%]

No additional constraints.

Input Specification

The first line of input will contain ~2~ space-separated integers ~N~ and ~Q~.

The next line will contain ~N~ space-separated integers ~a_i~.

The next ~Q~ lines will contain ~2~ space-separated integers ~L~ and ~R \ (1 \le L \le R \le N)~, denoting that Derek want's to know the mean price of the stock between days ~L~ and ~R~ inclusive.

Output Specification

For each one of derek's ~Q~ queries output the mean price of the stock between those days on a new line.

Sample Input

6 3
100 98 98 96 95 99
1 6
1 2
1 3

Sample Input

97
99
98

Explanation

For the first query, the mean price is ~\lfloor \frac{100 + 98 + 98 + 96 + 95 + 99}{6}\rfloor = 97~.

For the second query, the mean price is ~\lfloor \frac{100 + 98}{2}\rfloor = 99~.

For the third query, the mean price is ~\lfloor \frac{100 + 98 + 98}{3}\rfloor = 98~.