说明

原题是这样的： 给定 n 个整数 a1,a2,⋯,an , 求它们两两相乘再相加的和，即 S=a 1 ⋅a 2 +a 1 ⋅a 3 +⋯+a 1 ⋅a n +a 2 ⋅a 3 +⋯+a n−2 ⋅a n−1 +a n−2 ⋅a n +a n−1 ⋅a n。

Gordon 直接秒掉了这道题，然后反手给了你一个加强版： 总共 q 组询问，每次询问给你两个数 l,r，问你 a l ,a l+1 ,⋯,a r 两两相乘再相加的和。

输入格式

输入的第一行包含一个整数 n,q。 第二行包含 n 个整数 a 1 ,a 2 ,⋯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≤n,q≤2×10^5 ,1≤a i ≤1000,1≤l≤r≤n。