#P1177. E.善恶错乱之世,同病相怜之人

E.善恶错乱之世,同病相怜之人

Background

人类

你们的存在就是错误

战争 欺骗 嫉妒 贪婪

你们曾让我失去了所有

但今天

我将吞噬一切

因为我

就是崩坏。

img

Description

律者全部出动,正在破坏着这个世界,德莉莎一行人正在前往阻止律者,但是现在他们被一个魔法阵拦着了,这个魔法阵会给你n个数字,然后会询问你m次,每次询问一个区间[L,R]的总和,但是重复的数字只计算一次,于是德莉莎将这个艰巨的任务交给了作为ACMer的你。

Format

Input

第一行输入n、m (1<=n<=5000001<=m<=100000)(1<=n<=500000,1<=m<=100000) 第二行输入n个数字aia_i(1<=ai<=500000)(1<=a_i<=500000) 第三行到第m+2行每行输入L、R分别表示要求的区间(1<=L<=R<=500000)(1<=L<=R<=500000)

Output

对于每一个区间询问,输出区间和即可(重复的数只计算一次)

Samples

5 2
1 2 2 4 5
1 5
3 4
12
6

Limitation

1s, 1024KiB for each test case.