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: 0.2 seconds

Memory limit: 512 MB

Output limit: 1 MB