問題
$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 \ $
小数点以下は切り捨てて求めてください。