011 - Contest

問題

$N \ $問からなるコンテストに処理部員$ \ M \ $人が参加している。
各処理部員には「レーティング」という値があり、$i \ (1 \leq i \leq M) \ $番目の処理部員の「レーティング」は$ \ R_i \ $である。

このコンテストで全ての処理部員が$ \ 1 \ $問以上の問題に正答することができ、$i \ $番目の処理部員は問題$ \ l_i \ $から$ \ r_i \ $までを全て正答している。

ここで$ \ i \ (1 \leq i \leq N) \ $番目の問題の「Difficulty」を、$i \ $番目の問題を正答した処理部員の「レーティング」の平均値（小数点以下は切り捨て）とする。ただし、正答者がいない問題の「Difficulty」は$ \ -1 \ $とする。

各問題の「Difficulty」を求めよ。

入力

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

$N \ M$
$R_1 \ R_2 \ \ldots \ R_M$
$l_1 \ r_1$
$l_2 \ r_2$
$\vdots$
$l_M \ r_M$

出力

各問題の「Difficulty」を改行区切りで出力せよ。

制約

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

• $1 \leq N,M \leq 3 \times 10^5$
• $1 \leq R_i \leq 10^9$
• $1 \leq l_i \leq r_i \leq N$
• 入力は全て整数

入出力例

入力例

5 3
5 7 2
2 3
1 4
3 3

出力例

7
6
4
7
-1

• 問題1:$ \ \frac{7}{1} = 7 $
• 問題2:$ \ \frac{5 + 7}{2} = 6 $
• 問題3:$ \ \frac{5 + 7 + 2}{3} = 4.666666...$
• 問題4:$ \ 7 \div 1 = 7 $
• 問題5:正答者がいないので$ \ -1 \ $

小数点以下は切り捨てて求めてください。