範囲合計クエリ (Range Sum Queries)

配列に含まれる n 個の要素と、q 件の範囲合計クエリが与えられます。Segment Tree (セグメントツリー) を使用して、指定された範囲内に含まれる要素の合計を効率的に求めることがあなたのタスクです。

入力

1 行目には、配列の要素数である n と、クエリの数である q (1 ≤ n, q ≤ 100000) が与えられます。

2 行目には () が空白区切りで並んでおり、これが配列の各要素を示します。

続く q 行には、それぞれ と () の 2 つの整数が与えられます。これらはクエリで求める範囲を表します。

出力

各クエリに対して、指定された範囲内の要素の合計を改行区切りで出力してください。

Examples

Explanation

たとえば、配列 [1, 2, 3, 4, 5] に対して以下の範囲合計クエリを実行します:

1. クエリ [1, 3]: [1, 3] の範囲にある要素の合計は 1 + 2 + 3 = 6。

2. クエリ [2, 4]: [2, 4] の範囲にある要素の合計は 2 + 3 + 4 = 9。

3. クエリ [1, 5]: [1, 5] の範囲にある要素の合計は 1 + 2 + 3 + 4 + 5 = 15。