Cho một dãy gồm N số nguyên dương A1, A2,…, AN. (N ≤ 10⁵, Ai ≤10⁸).

Cho Q truy vấn có dạng (u,v). Với mỗi truy vấn (u,v) trả lời tổng các phần tử của mảng A từ phần tử thứ u đến phần tử thứ v.

Input:

Dòng đầu chứa số N, Q (1 ≤ Q ≤ 105)

Dòng thứ hai chứa N số nguyên dương A1, A2,…, AN. Q dòng tiếp theo ghi 2 số nguyên u,v (1 ≤ u ≤ v ≤ 105)

Output: Gồm Q dòng, mỗi dòng ghi trả lời tương ứng với mỗi truy vấn.