題目描述

給出一個長度為 n 的數組 a₁, a₂, ..., a_n​。

接著有 q 次查詢, 每次查詢有兩個參數 L, R。

輸入格式

第一行兩個正整數 n 和 q。

第二行有 n 個整數，表示 a₁, a₂, ..., a_n。

接下來 q 行，每行兩個正整數 L 和 R。

輸出格式

輸出 q 行，每行代表一次查詢結果。

Samples

3 2
1 2 4
1 2
2 3

3
6

提示

1 ≤ n, q ≤ 10⁵
−10⁹ ≤ a[i] ≤ 10⁹
1 ≤ L ≤ R≤ n

原始資料

• Zero1 題號：b220
• Hydro 題號：Z1220
• Locale：zh_TW
• Display：practice