输入一个序列 \(a[1],a[2],\dots,a[n]\) 。

\(q\) 询问，每次输入 \(l,r\) ，输出 \(a[l]\times 1+a[l+1]\times 2+\cdots+a[r]\times (r-l+1)\) 的结果。

第一行两个整数 \(n,q\) 。

第二行 \(n\) 个整数 \(a[1],\dots,a[n]\) 。

接下来 \(q\) 行，每行两个整数 \(l,r\) 。

\(q\) 行，每行一个整数答案。

\(1\leq n,q\leq 10^6\)
\(\big|a[i]\big|\leq 10^6\)

样例解释
第一次 2×1 + 3×2 + 1×3 = 11
第二次 3×1 + 1×2 + 7×3 + 8×4 + (-5)×5=33
第三次 7×1 + 8×2 + (-5)×3 + 9×4 = 44