Từng là một vị vua bất bại, một chiến binh mà khiến cho bất cứ ai nghe đến tên cũng phải khiếp sợ nhưng giờ đây, sau khi trải qua hơn 1000 năm chìm đắm trong vòng xoay rượu chè, Sa đã bị tha hóa. Sau những chuỗi ngày 18 tiếng liên tục, Sa nhận ra sự sai lầm của mình, anh ấy muốn tìm lại vị thế của mình ngày xưa nên đã quay trở lại chiến trường. Có \(n\) các thành trì, thành trì thứ \(i\) có giá trị \(a_{i}\) (có thể âm) được Sa đưa vào tầm ngắm. Cú đánh bom sẽ làm phá hủy một đoạn liên tiếp các thành trì. Sa có \(m\) quả bom nên Sa đã chọn một số phương án để tấn công, mỗi phương án được biểu thị bởi \(x\) và \(y\), biểu thị một cú đánh bom từ thành trì \(x\) đến thành trì \(y\), và kết quả của cú đánh bom này là tổng giá trị từ \(x\) đến \(y\). Các bạn hãy giúp Sa tính toán kết quả cho từng kết quả đánh bom.

Input

• Dòng đầu gồm 2 số nguyên \(n\) và \(m\). \((1 \leq n, m \leq 30000)\)
• Dòng tiếp theo ghi \(n\) số nguyên \(a[i]\) cách nhau bởi dấu cách. \((1 \leq i \leq n)\) \((|a[i]| \leq 1000)\)
• \(m\) dòng tiếp theo mỗi dòng ghi 2 số \(x, y(1 \leq x \leq y \leq n)\), biểu thị cú đánh bom phá hủy từ thành trì \(x\) đến thành trì \(y\).

Output

• Gồm \(m\) dòng, dòng thứ \(i\) chứa kết quả của phương án đánh bom thứ \(i\).

Example

5 3
1 -8 -1 2 9
1 5
3 3
2 4

3
-1
-7