Cho dãy ~A~ gồm ~N~ phần tử.

Một dãy ~a~ là dãy con của dãy ~b~ khi và chỉ khi ta xóa đi một số phần tử trong dãy ~b~ sẽ thu về dãy ~a~.

Cụ thể với ~a = [1, 2, 3]~ sẽ là dãy con của ~b = [1, 4, 5, 2, 10, 3]~. Và dãy ~a~ = [] (rỗng) cũng là một dãy con của ~b = [1, 4, 5, 2, 10, 3]~.

Yêu cầu: Với ~q~ truy vấn, mỗi truy vấn gồm 1 cặp số ~l~ và ~r~ ~(1 <= l <= r <= N)~. Hãy tìm dãy con của dãy ~A_l, A_{l + 1}, ..., A_{r - 1}, A_{r}~ có tổng lớn nhất và in ra tổng đó.

INPUT

• Dòng đầu chứa 2 số ~N~ và ~q~ ~(1 <= N, q, <= 10^5)~
• Dòng thứ 2 chứa dãy ~A~ gồm ~n~ phần tử ~(|A_i| <= 10^7)~
• ~q~ dòng tiếp theo, mỗi dòng gồm 1 cặp số ~l~ và ~r~

OUTPUT

• Với mỗi testcase, in ra yêu cầu của bài

SUBTASKS

• Subtask 1 (40%): ~q <= 10^4, n <= 10^2~
• Subtask 2 (60%): ~q <= 10^5, n <= 10^5~

SAMPLE

Input

7 2
1 -2 3 -4 5 -6 7
1 5
3 6

Output

9
8

Explanation

Dãy con có tổng lớn nhất từ:
1 -> 5: 1 + 0 + 3 + 0 + 5 = 9
3 -> 6: 3 + 0 + 5 + 0 = 8