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.

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.