2013 - 睡眠記録中のKamba君

問題

Pandora高校のKamba君は、体調管理のために毎日の睡眠時間を記録することにしました。Kamba君は $M$ 日間、自分の睡眠時間をメモし、後で振り返ることにしました。そこで、記録された $M$ 日間の睡眠データと、調べたい範囲 $A$ 日目から $B$ 日目までの情報が与えられるので、それぞれの期間の平均睡眠時間を求めてください。

入力

入力は以下の形式で標準入力から与えられる。

$M$ $K$
$H_1$ $H_2$ $...$ $H_M$
$A_1$ $B_1$
$A_2$ $B_2$
$:$
$:$
$A_K$ $B_K$

1行目にKamba君が睡眠データを記録した総日数 $M$ （整数）と、調べたい期間の数 $K$ （整数）が与えられる。
2行目に $M$ 個の整数 $H_1$ ～ $H_M$ （各日の睡眠時間（整数））が空白区切りで与えられる。
$K$ 行に渡って、$A_i$ $B_i$（それぞれの平均睡眠時間を求めたい範囲の開始日と終了日）が与えられる。

出力

各範囲について、指定された $A$ 日目から $B$ 日目までの平均睡眠時間を順に出力してください。 また、各結果は1行ずつ出力し、最後に改行を入れること。

制約

全ての入出力ケースについて以下を満たす。

• $1 \leq M \leq 365$
• $1 \leq K \leq 740$
• $0 \leq H_i \leq 24$
• $1 \leq A_i \leq B_i \leq M$

入出力例

入力例1

7 2
6 7 7 6 6 4 5
1 7
3 5

出力例1

5
6

入力例2

7 3
4 4 3 4 5 12 13
1 7
6 7
1 5

出力例2

6
12
4