Background

人类

你们的存在就是错误

战争 欺骗 嫉妒 贪婪

你们曾让我失去了所有

但今天

我将吞噬一切

因为我

就是崩坏。

Description

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

Format

Input

第一行输入n、m $(1<=n<=500000，1<=m<=100000)$ 第二行输入n个数字$a_i$，$(1<=a_i<=500000)$ 第三行到第m+2行每行输入L、R分别表示要求的区间$(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.