Description

He divides the cemetery into a main tombstone and secondary tombstones. There can be only $1$ main tombstone, which he numbers as $1$. There are $n-1$ secondary tombstones, numbered $2,3\dots n$, forming a cemetery with $n$ tombstones.

Each tombstone has an initial feng shui value. These values determine the overall feng shui of the cemetery, so the gravekeeper needs to query them often.

Skilled at using feng shui, the gravekeeper has defied fate again and again and gained infinite life. No one knows how long he has lived. Today, you are lucky to visit him. He asks you to witness his achievements in the coming years. However, every time he sums up feng shui values, he needs you to compute the result for him. If you get it wrong, he will take your life QAQ.

Feng shui is not unchangeable. Unless something special happens, it stays the same. It is known that in the next $2147483647$ years, there will be $f$ disasters. The gravekeeper will perform several operations:

1. Increase the feng shui value of all tombstones in interval $[l,r]$ by $k$.
2. Increase the feng shui value of the main tombstone by $k$.
3. Decrease the feng shui value of the main tombstone by $k$.
4. Query the sum of feng shui values of all tombstones in interval $[l,r]$.
5. Query the feng shui value of the main tombstone.

As mentioned above, many people settle their ancestors’ graves here, and the gravekeeper has lived for many centuries →_→, so the number of tombstones will be more than you can believe = =.

The gravekeeper kindly invites you to help him perform these operations; otherwise one day your inn might explode, and knives may fall from the sky...

To stay alive, please help him.

Input Format

• The first line contains two positive integers $n, f$, meaning there are $n$ tombstones, and in the next $2147483647$ years there will be $f$ apocalypses.
• The second line contains $n$ positive integers, where the $i$-th number is the initial feng shui value of the $i$-th tombstone.
• The next $f$ lines each describe one operation, identified by the same indices as in the statement:
  • Type $1$: 1 l r k — increase all tombstones in $[l,r]$ by $k$.
  • Type $2$: 2 k — increase the main tombstone by $k$.
  • Type $3$: 3 k — decrease the main tombstone by $k$.
  • Type $4$: 4 l r — query the sum over $[l,r]$.
  • Type $5$: 5 — query the main tombstone’s value.
• Indices are $1$-based.

Output Format

Print several lines. For each query of type $4$ or $5$, output the answer on a separate line.

5 7
0 0 0 0 0
1 1 5 1
1 1 3 3
2 3
3 1
4 1 5
2 1
5

16
7

Hint

Constraints

$20\%$ of the testdata satisfies: $1\leq n\leq 100$.

$50\%$ of the testdata satisfies: $1\leq n\leq 6000$.

$100\%$ of the testdata satisfies: $1\leq n,f\leq 2 \times 10^5$, and the answers do not exceed 64-bit integers.

Translated by ChatGPT 5