Một rạp phim ở thành phố Tân An có ~N~ ghế được đánh số từ ~1~ đến ~N~ sở hữu chính sách rất độc lạ:

• Khách hàng đến muốn thưởng thức bộ phim chỉ được mua vé từ ghế ~U~ đến ghế ~V~. ~(1 \le U\le V \le N)~
• Mỗi một ghế ngồi lại có một giá riêng và thậm chí còn khuyến mãi tặng tiền lại cho khách.

Bạn Đụt đang đi chơi cùng người bạn gái tưởng tượng của anh ấy. Vì thời tiết ở Tân An khá nóng nên cả hai quyết định đi xem phim vì trong đấy có máy lạnh và bộ phim Vệ binh dải ngân hà 3 đang được phát sóng. Là một người cuồng phim MARVEL như Đụt thì xem phim là một sự lựa chọn hợp lý.

Lúc mua vé, Đụt có rất nhiều tiền nên muốn ra vẻ với người bạn gái mình, mua sao cho tiền vé là mắc nhất. Tuy nhiên, đời không như là mơ, cô bạn gái tưởng tượng của bạn lại chỉ muốn ngồi trong khoảng ~L~ đến ~R~. Vì có quá nhiều ghế với nhiều giá tiền cũng như chính sách của rạp chiếu phim rất độc lạ nên bạn Đụt không tài nào tính toán được làm sao để vừa ra vẻ có tiền và vừa chiều lòng bạn gái anh ấy, bạn hãy giúp anh ấy nhé.

Dữ liệu vào

• Dòng đầu tiên chứa số nguyên dương ~N~ ~(N \le 10^6)~ là số ghế của rạp phim độc lạ và số nguyên dương ~Q~ ~(Q \le 10^5)~. Vì bạn gái của Đụt đổi ý liên tục nên ~Q~ là số yêu cầu.
• Dòng thứ hai chứa ~N~ số nguyên ~a_1,a_2,\dots ,a_N~ ~(1 \le i \le N , |a_i| \le 10^5)~ là giá tiền của vé ở ghế thứ ~i~, nếu giá vé âm tức là khuyến mãi tặng tiền cho khách.
• ~Q~ dòng tiếp theo, mỗi dòng là hai số ~L~ và ~R~ ~(1 \le L\le R \le N)~ là khoảng ghế mà bạn gái Đụt muốn ngồi.

Kết quả ra

• Gồm ~Q~ dòng, mỗi dòng là số tiền mà bạn Đụt mua vé có thể vừa khoe sự giàu có của mình và chiều lòng bạn gái anh ấy.

Ví dụ

Dữ liệu

5 1
1 -2 4 3 -6
2 3

Kết quả

6

Dữ liệu

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

Kết quả

6
0

Giải thích

• Ở test thứ nhất, bạn Đụt sẽ mua vé ở các ghế có giá trị ~1 + (-2) + 4 + 3 = 6~ chứa đoạn ~[2,3]~ mà bạn gái Đụt mong muốn.
• Ở test thứ hai
  • Bạn Đụt sẽ mua vé ở các ghế có giá trị ~2+3+ (-4)+5=6~ chứa đoạn ~[2,3]~ mà bạn gái Đụt mong muốn.
  • Bạn Đụt sẽ mua vé ở các ghế có giá trị ~2+3+(-4)+5+(-6)=0~ chứa đoạn ~[2,6]~ mà bạn gái Đụt mong muốn.

Ràng buộc

• Có ~20~ test có ~N \le 10^4~, ~Q \le 10^4~, ~|a_i| \le 10^5~ .
• Có ~5~ test có ~N \le 10^5~, ~Q \le 10^5~, ~|a_i| \le 10^5~ .
• Có ~5%~ test có ~N \le 10^6~, ~Q \le 10^5~, ~|a_i| \le 10^5~ .