U397164 不是可做题

给定正整数序列 $a_1\sim a_n$。 $m$ 次询问，每次询问指定区间 $[l,r]$，回答对于其所有非空子区间（包括自身），有多少种不同的区间和。

第一行两个正整数 $n,m$。 第二行 $n$ 个正整数，第 $i$ 个为 $a_i$。 下面 $m$ 行，每行两个正整数 $l,r$。

输出 $m$ 行，每行一个正整数。

样例的第四个询问中，不同区间和分别为：$1,2,4,5,6,9,10,11$。 对于 $100\%$ 的数据，$1\le n,m,a_i\le 10^5$，$1\le l\le r\le n$。