#### Registered Users Only

Please login to utilize this feature.

Do note that this website only supports submissions in C++.

## Problem Description

Rar the Cat has an array of *N* integers. Initially, the *i ^{th}* integer has the value

*A*.

_{i}Rar the Cat wants you to answer queries and updates, there will be a total of *M* queries and updates, in order.

For each query, Rar the Cat will provide you with two integers *x* and *y* where 0 ≤ *x* ≤ *y* < *N*. You are to respond with the sum of the integers from *A[x]* to *A[y]* inclusive.

For each update, Rar the Cat will provide you with three integers, *a*, *b* and *c*. This means you have to add *c* to every integer from *A[a]* to *A[b]*.

## Limits

For all testcases, -(10^{3}) ≤ A_{i}, c ≤ 10^{3}, 0 ≤ x ≤ y < N, 0 ≤ a ≤ b < N.

Subtask 1 (57%): 1 ≤ N ≤ 100000, 0 ≤ M ≤ 200000. For all update commands, *a* = *b*.

Subtask 2 (43%): 1 ≤ N ≤ 100000, 0 ≤ M ≤ 200000. No further restrictions.

Subtask 3 (0%): Sample Testcases.

## Input

The first line of input will contain one integer, *N*.

The second line of input will contain *N* integers, representing the array *A*.

The next line will contain a single integer, *M*.

*M* lines will follow. The first character of each line will be *T*.

If *T* is 0, then it represents a query. 2 integers will then follow, *x* and *y*.

If *T* is 1, then it represents a update. 3 integers will then follow, *a*, *b* followed by *c*.

## Output

For each line of query, you are to output the sum of *A[x]* to *A[y]* inclusive, on a single line.

## Sample Testcase 1

### Input

10 1 2 9 5 7 6 3 4 2 2 5 0 0 1 0 0 9 1 1 8 7 0 0 9 0 5 7

### Output

3 41 97 34

### Tags

### Subtasks and Limits

Subtask | Score | #TC | Time | Memory | Scoring |
---|---|---|---|---|---|

1 | 57 | 20 | 1s | 64MB | Minimum |

2 | 43 | 41 | 1s | 64MB | Minimum |

3 | 0 | 1 | 1s | 64MB | Minimum |

### Judge Compile Command

g++-7 ans.cpp -o fenwicktree -Wall -static -O2 -lm -m64 -s -w -std=gnu++17 -fmax-errors=512