题目描述

序列长度为$n$，现在有$m$次查询，每次查询区间$[l,r]$ 的最大前缀和。

输入格式

第一行两个整数 $n,m$ 表示序列长度和查询次数。

接下来一行 $n$ 个整数为序列。

接下来 $m$ 行，每行两个整数 $l$ 和 $r$ 表示查询的区间。

输出格式

$m$ 行，每行一个数字为对应区间最大前缀和。

样例 1 输入

7 4
100 -100 1000 -20 100 200 -1000
1 3
3 4
1 7
5 7

样例 1 输出

1000
1000
1280
300