Description

As stated, given a sequence, you need to perform the following two operations:

1. Add $x$ to every number in a given interval.
2. Query the value of a specific element.

Input Format

The first line contains two integers $N$ and $M$, representing the number of elements in the sequence and the total number of operations.

The second line contains $N$ space-separated integers, where the $i$-th number is the initial value of the $i$-th element of the sequence.

Each of the next $M$ lines contains $2$ or $4$ integers describing an operation, as follows:

Operation 1: Format: 1 x y k Meaning: add $k$ to every number in the interval $[x,y]$.

Operation 2: Format: 2 x Meaning: output the value of the $x$-th number.

Output Format

Output several lines of integers, which are the results of all type 2 operations.

5 5
1 5 4 2 3
1 2 4 2
2 3
1 1 5 -1
1 3 5 7
2 4

6
10

Hint

Explanation for Sample 1:

Therefore, the outputs are $6$ and $10$.

Constraints

For $30\%$ of the testdata: $N\le8$, $M\le10$.

For $70\%$ of the testdata: $N\le 10^4$, $M\le10^4$.

For $100\%$ of the testdata: $1 \leq N, M\le 5\times10^5$, $1 \leq x, y \leq n$. It is guaranteed that at any time, the absolute value of any element in the sequence does not exceed $2^{30}$.

Translated by ChatGPT 5