题目背景

年糕所在的班级一共有 $n$ 个人，大家刚刚进行了期末考试，并都知道了自己的成绩。
为了方便期末的时候根据成绩分发奖励，老师把所有同学分成了 $k$ 个小组，每个小组成员的编号为 $l_i$ 到 $r_i$。
作为班长，年糕需要对每个小组的成绩进行记录并汇报给老师。但是由于班里的同学太多了，她有点忙不过来。请你编写一个程序帮帮她。

题目描述

年糕所在的班级共有 $n$ 个人，其中编号为 $i$ 的同学的期末成绩为 $a_i$。
老师把所有的同学分成了 $k$ 组，每个小组成员的编号为 $l_i$ 到 $r_i$。
根据这些信息，请你分别求出每个小组所有成员期末成绩的总和。
注意: 一个同学可能同时存在于多个小组里，请你注意辨别。

输入格式

第一行输入两个整数 $n,k$，分别表示班级的人数和小组的个数。
第二行输入 $n$ 个整数，表示所有同学的期末成绩。
接下来 $k$ 行，每行输入两个整数 $l_i$ 和 $r_i$，表示小组成员的编号范围。

输出格式

对于每个询问，输出一个整数，表示这个小组所有成员的成绩之和。

输入输出样例

5 3
90 80 70 100 60
1 3
2 4
5 5

240
250
60

说明/提示

数据范围

$1≤n≤10^3$
$1≤k≤20$
$k≤n$
$1≤l_i≤r_i≤n$
$0≤a_i≤100$