Given an integer array nums and multiple queries. Each query contains two indices left and right. Your task is calculating the sum of the elements of nums between indices left and right inclusive.

Input

The first line contains two integers n and q which are the length of nums and the number of queries, relatively. The second line contains n integers which are the elements of nums. Each of the next q lines contains two integers left and right.

Output

Output q lines. Each line contains an integer representing the corresponding sum

Example

Input:

5 2
2 -1 2 5 4
1 1
0 2

Output:

` -1 3