题目描述

展馆把一天分成 n 个时间片，第 i 个时间片的人流量为 a[i]。策展人定义区间 [l,r] 的“热度”为该区间人流总量。

现在有 q 次询问，每次给出 [l,r]，请输出对应热度。

输入格式

第一行两个整数 n q。 第二行 n 个整数 a[i]。 接下来 q 行，每行两个整数 l r（1-index）。

输出格式

输出 q 行，每行一个整数。

样例

样例输入

5 3
2 1 1 4 -1
1 3
2 5
4 4

样例输出

4
5
4

数据范围

• 1 ≤ n,q ≤ 2×10^5
• |a[i]| ≤ 10^9
• 1 ≤ l ≤ r ≤ n