AT_abc480_d [ABC480D] Concatenation of Prefixes

長さ $ N $ の整数列 $ (A_1,\dots,A_N) $ が与えられます。 以下の手順で長さ $ \frac{N(N+1)}{2} $ の数列 $ B $ を作ります。 - 最初、 $ B $ を空列とする。 - $ i=1,2,\dots,N $ の順に、 $ B $ の末尾に $ (A_1,\dots,A_i) $ を連結する。 以下の形式の質問が $ Q $ 個与えられるのでそれらに答えてください。 質問： $ L,R $ が与えられる。 $ B_L+B_{L+1}+\dots+B_R $ を求めよ。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ Q $ $ A_1 $ $ A_2 $ $ \dots $ $ A_N $ $ \mathrm{query}_1 $ $ \mathrm{query}_2 $ $ \vdots $ $ \mathrm{query}_Q $ ここで $ \mathrm{query}_i $ は $ i $ 番目の質問を表し、以下の形式で与えられる。 > $ L $ $ R $

$ Q $ 行出力せよ。 $ i $ 行目には $ i $ 番目の質問に対する答えを出力せよ。

### Sample Explanation 1 $ B=(1,1,10,1,10,100,1,10,100,1000) $ です。 - $ 1 $ 番目の質問に対する答えは $ 10+1+10+100=121 $ です。 - $ 2 $ 番目の質問に対する答えは $ 1+1+10+1+10+100+1+10+100+1000=1234 $ です。 - $ 3 $ 番目の質問に対する答えは $ 10 $ です。 ### Constraints - $ 1 \leq N \leq 10^5 $ - $ 1 \leq Q \leq 10^5 $ - $ -10^8 \leq A_i \leq 10^8 $ - 各質問において、 $ 1\leq L\leq R \leq \frac{N(N+1)}{2} $ - 入力は全て整数