You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

方差

题目背景

定义一个长度为 $n$ 的序列 $a$ 的方差为：

其中：$\sum$ 为累加求和符号，例如 $\sum_{i=1}^5 a_i=a_1+a_2+a_3+a_4+a_5$。$\overline{a}$ 为序列 $a$ 的平均数。

例如对于序列 $\{3,5,1,4,2\}$，$\overline{a}=3$，此时 $s^2=\frac{1}{n} \sum_{i=1}^n (a_i-\overline{a})^2=\frac{1}{5}((3-3)^2+(5-3)^2+(1-3)^2+(4-3)^2+(2-3)^2)=2$。

更简单的理解方式是，方差是 平方的平均数 减去 平均数的平方。

题目描述

给定一个长度为 $n$ 的序列 $a_{1\dots n}$ 和 $q$ 次询问，每次询问形式为一个区间 $[l,r]$，问的是 $a_{l\dots r}$ 这个序列的方差。

为了避免出现小数，设方差为 $s^2$ ，请你对每个询问，输出 $(r-l+1)^2s^2$ （即序列长度平方乘上方差），根据上面的式子可以证明这个一定是整数。

输入格式

第一行两个正整数 $n$、$q$，第二行 $n$ 个整数 $a_{1\dots n}$ 表示这个序列。

接下来 $q$ 行，每行两个正整数 $l$、$r$，表示一个询问。

输出格式

对于每个询问，输出一行一个整数，表示你的答案。

样例 #1

样例输入 #1

5 15
5 7 8 8 8
1 1
1 2
1 3
1 4
1 5
2 2
2 3
2 4
2 5
3 3
3 4
3 5
4 4
4 5
5 5

样例输出 #1

0
4
14
24
34
0
1
2
3
0
0
0
0
0
0

提示

【样例解释】

对于第 $12$ 组询问，区间 $[3, 5]$ 的平均数 $\overline{a} = 8$，方差 $s^2 = \frac{1}{3}((8 - 8)^2 + (8 - 8)^2 + (8 - 8)^2) = 0$。

【数据范围】

• 对于 $20\%$ 的数据，保证 $n,q\leq 10$。
• 对于 $50\%$ 的数据，保证 $n,q\leq 100$。
• 对于 $100\%$ 的数据，保证 $n\leq 10^4$，$q\leq 10^3$，$a_i\leq 10^5$。