For an array $A$ of $n$ integers, you need to process $q$ queries, each belonging to one of the three types:
- `1 x`: Add the value $x$ to the end of array $A$.
- `2`: Remove the last value from array $A$.
- `3 l r`: Calculate the sum of elements from index $l$ to $r$, array indices starting from $1$.
### Input
- The first line consists of two integers $n, q$.
- The second line contains $n$ integers $A_i$.
- The next $q$ lines, each containing a query in the specified format.
### Output
- Output an integer as the answer for each type $3$ query.
### Constraints
- $1 \le n, q \le 10^5$.
- $1 \le x \le 10^9$.
- $1 \le l \le r \le |A|$ where $|A|$ is the length of array $A$ at the time of the query.
### Sample test
Input
```
5 4
1 2 3 4 5
1 6
3 1 6
2
3 2 3
```
Output:
```
21
5
```
