题目描述

ymzs666在努力锻炼自己的记忆力，他现在已经可以做到记下一串给定的数据，并且当你对它进行询问时，它可以准确的告诉你这个数据所在的位置。但你想刁难刁难他，所以你决定告诉他一个起始值l，和一个结束值r，并要求他告诉你l到r区间内数值的和。作为一个高级机器人，ymzs666轻松的回答出了你的每一个问题，那么问题来了，他的回答程序究竟是怎样设计的呢？现在由你来写出这个回答程序，解开ymzs666的计算之谜。

输入格式

第1行给你两个整数n，m，代表接下来有n个数，m代表m次询问

第2行给你这n个数a[i]

以下m行每行给你两个整数l和r，代表询问的区间

输出格式

每次询问输出一行，表示l到r区间内数值之和

样例

输入

5 2
1 2 3 4 5
2 4
1 5

输出

9
15

数据范围与提示

$1\leq n \leq 10^5$

$a[i] \leq 1000$

$1 \leq l \leq r \leq n$