The semester has just begun at Universidad Nacional (UNAL). As usual, a group of vandals enjoys bringing chaos to all students and damaging the university facilities. Those guys have been planning the next attack on the university, their goal is to try to tear down all the walls that enclose the university.

First, they see the university as a set of $$$n$$$ walls numbered from $$$1$$$ to $$$n$$$, each with a height of $$$h_i$$$ meters, arranged as shown in the following image.

They plan to carry out $$$q$$$ attacks, in each attack, they tear down $$$s$$$ meters of all walls from $$$a$$$ to $$$b$$$.

The day has come and Mr. Potato Head is sad because this attack will be very costly for the university. He wants to know how many meters of the wall are left after some attacks. Can you help him with this task?

The first line contains two integers $$$n$$$ and $$$q$$$ $$$(1 \leq n, q \leq 10^{5})$$$, the number of walls and number of attacks respectively.

The second line contains $$$n$$$ numbers $$$h_1,...,h_n$$$ separated by spaces $$$-$$$ The height of each wall $$$(1 \leq h_i \leq 10^{8})$$$.

Each of the next $$$q$$$ lines contains one of the following operations:

• $$$1$$$ $$$a$$$ $$$b$$$: Mr. Potato Head ask how many meters of wall in total are left from walls $$$a$$$ to $$$b$$$ $$$(1 \leq a, b \leq n)$$$.
• $$$2$$$ $$$a$$$ $$$b$$$ $$$s$$$: The vandals have torn down $$$s$$$ $$$(1 \leq s \leq 10^{8})$$$ meters of all walls from $$$a$$$ to $$$b$$$ $$$(1 \leq a, b \leq n)$$$ (Note that if a wall has a height lower than $$$s$$$ then its height after the attack will be zero).

For each operation of type $$$1$$$ print the number of meters that are left in this interval.

It is guaranteed that there is at least one operation of type $$$1$$$.