题目内容

小塔有一个长度为 $n$ 的数组 $a_1, a_2,...,a_n$，他每次会询问一个区间$[l,r]$，他想知道数组$a$的所有长度大于等于$l$且小于等于$r$的子数组之和的最大值是多少。

如果数组$a$可以通过从数组$b$的开头删除若干(可能为零或全部)元素以及从结尾删除若干(可能为零或全部)元素得到，则数组$a$是数组$b$的子数组。

输入描述

第一行输入两个整数$n$和$q(1 ≤ n ≤3000;1≤ q ≤ 10^6)$代表数组中的元素数量和询问次数。