Algorithms and Data Structures

Range Sum Queries

You are given an array of n elements and q range sum queries. Your task is to efficiently answer each query by calculating the sum of elements within a given range using a segment tree data structure.

Input

The first line of the input contains two integers n and q (1 ≤ n, q ≤ 100 000), representing the number of elements in the array and the number of queries, respectively.
The second line contains n space-separated integers (), representing the elements of the array.
The following q lines each contain two integers and (), representing the range for each query.

Output

For each query, print the sum of elements within the given range on separate lines.

Examples

Input
Output
5 3 1 2 3 4 5 1 3 2 4 1 5
6 9 15

Explanation

For the given array [1, 2, 3, 4, 5], we perform the following range sum queries:
  1. Query [1, 3]: The sum of the elements in the range [1, 3] is 1 + 2 + 3 = 6.
  1. Query [2, 4]: The sum of the elements in the range [2, 4] is 2 + 3 + 4 = 9.
  1. Query [1, 5]: The sum of the elements in the range [1, 5] is 1 + 2 + 3 + 4 + 5 = 15.
 

Constraints

Time limit: 10 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in
Sign in to continue