頗旺很喜歡序列，他尤其喜歡玩一種很特別的序列，這種序列總共有$N$個數值$A_i$ ($i\in[1,N]$)。頗旺很喜歡很大的數，而且越大越好，因此，他很喜歡把數字加總，然而，頗旺發現有時候加一加數字反而會變小！這當然是由於加到負數的關係，因此，只要將所有非負的數值相加便能得到最大的數值，但，頗旺覺得這樣太不有趣了，所以，他決定只挑某個連續的部份$[L,R]$，則加總所有介於$[L,R]$間的數值，頗旺很好奇要挑選哪段連續的部份可以使得加總的數值最大，因此，頗旺就發明了最大連續和問題！

不過就在頗旺發明完後，頗旺瞬間就想到解法了，"這不就掃過去判一判，根本水題呀"，因此，他決定要變得更有趣一點，他想知道對於某個區間$[QL,QR]$，滿足$QL \leq L \leq R \leq QR$中，哪段連續的部份可以使得加總的數值最大，頗旺三個小時快用完了，因此他決定先去睡個覺，在睡覺前頗旺問$Q$個問題，也就是問說當限定在$[QL_i,QR_i]$間時，所能獲得的最大值為何，哦對了，頗旺不喜歡負的數字，因為會讓數值加總變小，因此如果答案是負的，請回答0，別讓頗旺不開心。