Một công ty ~X~ để dễ quản lý cũng như đưa ra chính sách hợp lý, công ty này cần phân tích dữ liệu lịch sử thông qua các truy vấn. Cụ thể, họ cần tính toán tổng các chỉ số hiệu suất trong một khoảng thời gian nhất định.

Cho một mảng số nguyên dương ~A~ gồm ~n~ phần tử, trong đó ~A_i~ biểu thị doanh thu của công ty của ngày ~i~.

Họ cần ~q~ truy vấn, mỗi truy vấn yêu cầu tính tổng doanh thu từ ngày thứ ~l~ đến ngày thứ ~r~.

Input

• Dòng đầu tiên gồm hai số nguyên ~n~ và ~q~ (~1 \leq n, q \leq 10^5~) lần lượt là số lượng phần tử của mảng và số lượng truy vấn.
• Dòng thứ hai gồm ~n~ số nguyên với ~1 \leq A_i \leq 10^6~.
• Gồm ~q~ dòng có hai số nguyên ~l~ và ~r~ (~1 \leq l \leq r \leq n~) đại diện cho truy vấn.

Output

• Với mỗi truy vấn, in ra tổng doanh thu của truy vấn đó.

Scoring

• Subtask 1 (80% số điểm): ~1 \le n, q \le 10^3~.
• Subtask 2 (20% số điểm): ~1 \le n, q \le 10^5~.

Samples

Sample Input

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

Sample Output

6
9
12