Bình có một dãy số \(a_1, a_2, \dots, a_n\) và nhận được \(q\) truy vấn. Mỗi truy vấn yêu cầu tính tổng các số trong đoạn \([l, r]\).

Gợi ý: Dùng mảng cộng dồn (prefix sum) — xây dựng \(pref[i] = \sum_{k=1}^{i} a_k\), mỗi truy vấn trả lời \(pref[r] - pref[l-1]\) trong \(O(1)\).

Input

Dòng đầu chứa \(n\) và \(q\) (\(1 \le n, q \le 10^5\)). Dòng hai chứa \(n\) số \(a_i\) (\(1 \le a_i \le 10^9\)). \(q\) dòng tiếp theo, mỗi dòng chứa \(l, r\) (\(1 \le l \le r \le n\)).

Output

Với mỗi truy vấn, in ra tổng các số từ \(l\) đến \(r\).

Example

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

Output:

6
14
7