题目描述

原题是这样的：

给定 $n$ 个整数 $a_{1}, a_{2}, \cdots, a_{n}$, 求它们两两相乘再相加的和，即

$$S=a_{1} \cdot a_{2}+a_{1} \cdot a_{3}+\cdots+a_{1} \cdot a_{n}+a_{2} \cdot a_{3}+\cdots+a_{n-2} \cdot a_{n-1}+a_{n-2} \cdot a_{n}+a_{n-1} \cdot a_{n} $$

Gordon 直接秒掉了这道题，然后反手给了你一个加强版：

总共 $q$ 组询问，每次询问给你两个数 $l,r$，问你 $a_l,a_{l+1},\cdots,a_r$ 两两相乘再相加的和。

输入格式

输入的第一行包含一个整数 $n,q$。

第二行包含 $n$ 个整数 $a_{1}, a_{2}, \cdots a_{n}$。

接下来 $q$ 行，每行两个整数 $l,r$，表示询问内容。

输出格式

对于每组询问，输出一行，有一个整数 $S$，表示所求的和。请使用合适的数据类型进行运算。

5 5
2 3 5 1 5 
3 4
1 2
1 2
2 3
3 3

5
6
6
15
0

提示

对于所有评测用例, $1 \leq n,q \leq 2\times10^5,1\leq a_{i} \leq 1000,1\le l\le r\le n$。