Migrated from Lutece 3123 光棱塔

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

Tag：莫队

房主叫嚣7v1进来挨打！那我来学习交流一下！

众所周知，在红色警戒中，光棱塔是一种会随着周围光棱塔链接数量增加而提高攻击力的防御建筑，被骗进来的月亮三现在就要突破7位玩家设下的光棱大阵，还好核弹已经就绪，试着帮助三哥轻取视频素材吧！

现在阵地上有 $n$ 座光棱塔，编号从 $1$ 到 $n$，假设第 $i$ 座光棱塔属于链接 $s_i$. 规定同一链接下光棱塔的战力总和 $f(s_i)=s_i\times h(s_i)^2$，$h(s_i)$为链接$s_i$中光棱塔数。

而三哥构思了 $m$ 种核弹释放方式，核弹会移除编号在 $[a_i , b_i]$ 区间内的光棱塔，你的任务是计算每种方式下核弹轰炸后剩余光棱塔的战斗力之和。

Input

第一行包含两个整数 $n,m$（$1 \le n,m \le 2*10^5$） 接下来一行有 $n$ 个整数 $s_i$（$1\le s_i\le 2\times 10^5$）表示第$i$个光棱塔所处的链接 接下来 $m$ 行每行有两个整数 $a_i,b_i$ （$1 \le a_i\le b_i \le n$）表示核弹轰炸询问区间

Output

输出 $m$ 行，每行表示执行当次轰炸方案后剩余光棱塔的战斗力之和。

Samples

3 2
1 2 1
1 2
1 3

1
0

8 3
1 1 2 2 1 3 1 1
2 7
2 6
4 8

4
9
6

Note

对于样例 2 第二次询问，剩下光棱塔所属链接为 $1\ 1\ 1$ 战力和为 $3\times 3\times 1=9$ 第三次询问，剩下光棱塔所属链接为 $1\ 1\ 2$ 战力和为 $2\times 2 \times 1+1\times1\times2=6$

Resources

2024 UESTC ICPC Training for Data Structure