Sequence Manager Queries

You are given an initial sequence of integers. Your task is to implement a sequence manager that supports two types of operations:

• Append: Append a given integer to the end of the sequence.
• Sum Query: Given two indices l and r (1-indexed), output the sum of the subsequence from index l to r.

For the sum query, you are required to return the sum using the formula $$ S(l, r) = \sum_{i=l}^{r} a_i, $$ where \(a_i\) is the i-th element of the sequence.

The operations will be performed sequentially. Note that append operations affect later queries.

inputFormat

The first line contains two integers n and q, where n is the initial length of the sequence and q is the number of queries.

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

Each of the next q lines represents a query in one of the following forms:

• 1 x: Append integer x to the sequence.
• 2 l r: Output the sum of elements from index l to r (1-indexed).

outputFormat

For each query of type 2, output the sum of the specified subsequence on a separate line.

## sample

5 3
1 2 3 4 5
1 7
2 2 6
1 8

21