- Time limit: 1.00 s
- Memory limit: 512 MB
Given an array of integers, you have to process following operations:
- reverse a subarray
- calculate the sum of values in a subarray
Input
The first input line has two integers and : the size of the array and the number of operations. The array elements are numbered .
The next line as integers : the contents of the array.
Finally, there are lines that describe the operations. Each line has three integers , and . If , you should reverse a subarray from to . If , you should calculate the sum of values from to .
Output
Print the answer to each operation where .
Constraints
Example
Input:
8 3 2 1 3 4 5 3 4 4 2 2 4 1 3 6 2 2 4
Output:
8 9