407419: GYM102787 D The Grim Treaper

Happy Halloween! Farmer John is rather weary: he has lots of harvesting still unfinished, and his Deere sweet tractor just broke down, so he must finish the harvesting with nothing more than his scythe. He is rather depressed knowing the total amount of harvesting he has left. To make things even worse, Bessie and friends don't know how to use a toilet, so they keep leaving... fertilizer... all over the grass, causing the wheat to grow even more! So much reaping of wheat needs to be done! How grim!

Initially, FJ has $$$n$$$ blades of grass numbered $$$1..n$$$ in a row. Initially blade $$$i$$$ has height $$$a_i$$$. $$$q$$$ times, one of the following will happen:

1. FJ will slice his scythe from $$$l$$$ to $$$r$$$ at height $$$h$$$, cutting all blades from $$$l$$$ to $$$r$$$ that are strictly longer than height $$$h$$$ to height $$$h$$$.

2. FJ will transplant range $$$l..r$$$ of his field to the end of the field. He will move all grass blades forwards so, in total, positions $$$1..n$$$ are still occupied after this operation.

3. Bessie and friends will take a dump on blades of grass from $$$l$$$ to $$$r$$$. Each of them will grow by $$$x$$$ units where $$$x$$$ is the stinkiness of the... fertilizer.

After each operation, Farmer John needs to know how much work he has left to do. In particular, he would like to know the sum of heights of all blades of grass.

The first line will contain two integers $$$n$$$ and $$$q$$$: the number of blades of grass, and the number of events. ($$$1 \leq n, q \leq 3*10^5$$$)

The second line will contain $$$n$$$ integers: the initial heights of grass blades. ($$$1 \leq a_i \leq 10^6$$$).

The following $$$q$$$ lines will describe each query, and be of one of the following forms:

- $$$1$$$ $$$l$$$ $$$r$$$ $$$h$$$. In this case $$$1 \leq l \leq r \leq n$$$ and $$$1 \leq h \leq 10^9$$$.

- $$$2$$$ $$$l$$$ $$$r$$$. In this case $$$1 \leq l \leq r \leq n$$$.

- $$$3$$$ $$$l$$$ $$$r$$$ $$$x$$$. In this case $$$1 \leq l \leq r \leq n$$$ and $$$1 \leq x \leq 10^5$$$.

Note that grass may grow to more than $$$2 * 10^9$$$ units.

After each query, print a single line describing the total height of all blades of grass after that query.

3 3
125987 264237 288891
3 2 3 30851
2 2 3
3 1 2 88689

740817
740817
918195

5 5
3 3 1 8 7
1 4 5 9
2 1 3
3 1 2 4
2 2 5
3 3 3 5

22
22
30
30
35