Taco Operations

You are given a list of n integers and q operations. There are two types of operations:

• append x — append an integer x to the end of the list.
• query l r — calculate the sum of the elements from index l to index r (inclusive).

The list indices are zero-indexed. Formally, if lst represents the list, then a query operation computes $$ S = \sum_{i=l}^{r}{lst[i]} \; .$$

Your task is to process all operations sequentially and output the result for each query operation.

inputFormat

The first line contains two integers n and q — the initial number of elements and the number of operations.

The second line contains n space-separated integers representing the initial list.

The following q lines each contain an operation in one of the two formats:

• append x
• query l r

outputFormat

For each query operation, output the resulting sum on a new line.

## sample

5 5
1 2 3 4 5
query 1 3
append 6
query 2 4
append 7
query 0 6

9
12
28

</p>