For an array A of n integers, you need to process q queries, each belonging to one of the three types:
- 1x: Add the value x to the end of array A.
- 2: Remove the last value from array A.
- 3lr: 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 Ai.
- 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≤n,q≤105.
- 1≤x≤109.
- 1≤l≤r≤|A| where |A| is the length of array A at the time of the query.
### Sample test
Input
5412345163162323
Output:
215