Cho dãy số có \(N\) phần tử \((-10^7 \le A_i \le 10^7)\) và \(Q\) truy vấn (mỗi truy vấn gồm \(L\) và \(R\)). Hãy in ra tổng con lớn nhất trong đoạn \([L, R]\)

Ràng buộc:

• \(10 \le N, Q \le 10^5\)
• \(0 \le L \le R \le N\)

Dữ liệu vào:

• Dòng thứ nhất: có 2 số \(N\) và \(Q\)
• Q Dòng tiếp theo: mỗi dòng chứa 2 số \(L\) và \(R\)

Dữ liệu ra:

• Q dòng: mỗi dòng là tổng mảng con lớn nhất trong đoạn \(L, R\)

Lưu ý:

• vị trí bắt đầu từ \(0\)

Input

10 2
10 -1 -2 5 3 2 -10 -2 -3 -1
0 9
1 5

Output

17
10