You are given an array A of n integers.
There are q queries of either form:
- 1lrx: Add x to Al,Al+1,...,Ar.
- 2lr: Find the sum Al+Al+1+...+Ar.
### Input
- The first line contains 2 integers n,q.
- The second line contains n integers Ai.
- The next q lines, each line contains either 3 (for type 2) or 4 (for type 1) integers, a query.
### Output
- Print the answer for each query of type 2.
### Constraints
- 1≤n,q≤105.
- 1≤i≤n.
- 1≤l≤r≤n.
- 0≤|Ai|,|x|≤106.
### Example
Input:
53123322241142235
Output:
812