大掃除

題目敘述

虹咲學園學生會想將校園內的雜物整理乾淨。學生會將所有雜物排成一排，並且紀錄下各個雜物的重量。而為了增加搬運的效率，學生會想知道特定區段的雜物總重，以便規劃每人搬運的數量及順序。學生會已經將資料給了你，請寫出一個程式達成她們的要求。

輸入說明

第一行為兩正整數

$n,m(0<n,m<{10}^6)$
第二行有n個整數

$a_0,a_1...a_{n-1}(0\le a_i<{10}^8)$
第三行開始，接下來有

$m$行，每行有兩整數

$l,r(0\le l,r<n)$，求數列

$a$中第

$a_l$項到第

$a_r$項之區間和(此區間為閉區間)。

輸出說明

對於每筆查詢輸出其查詢區間和。

範例輸入#1

5 3
1 2 3 4 5
0 2
0 4
1 1

範例輸出#1

6 15 2

範例輸入#2

8 3
100 2 35 455 5 1 22 10000000
0 5
0 3
7 7

範例輸出#2

598 592 10000000