Cho một mảng gồm \(n\) số nguyên, nhiệm vụ của bạn là xử lý \(q\) truy vấn có dạng: tổng các phần tử trong đoạn \([a, b]\) là bao nhiêu?

Input

• Dòng đầu tiên là hai số nguyên \(n\) và \(q\): số phần tử và truy vấn
• Dòng thứ hai là \(n\) số nguyên \(x_1, x_2,\ldots, x_n\): các phần tử của mảng
• \(q\) dòng cuối cùng là các truy vấn. Mỗi dòng là hai số nguyên \(a\) và \(b\): tổng các phần tử trong đoạn \([a, b]\) là bao nhiêu?

Constraints

• \(1 \leq n, q \leq 2\cdot 10^5\)
• \(1 \leq x_i \leq 10^9\)
• \(1 \leq a \leq b \leq n\)

Output

• In ra đáp án của mỗi truy vấn

Example

8 4
3 2 4 5 1 1 5 3
2 4
5 6
1 8
3 3

11
2
24
4