B. Balloon Trip
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Summer vacation has arrived, and Nobita is once again dreaming of an exciting adventure. Instead of studying for exams or doing homework, he imagines drifting peacefully in a hot-air balloon across the mountains that stretch endlessly beyond his town. Of course, when it comes to turning dreams into reality, there is only one person he can rely on: Doraemon.

The mountains Nobita wants to cross are arranged in a straight line, and each one has a specific height. For convenience, Doraemon numbers the mountains from $$$1$$$ to $$$n$$$, and Nobita writes down their current heights in a notebook. The height of the mountain $$$i$$$ is $$$a_i$$$. At first glance, the plan seems simple: launch the balloon at one mountain, then float to the next, and keep going until the desired destination.

But the balloon journey is not smooth. Each time the balloon moves from one mountain to the next, the balloon must rise or sink to match the new height. The effort required is the difference of the two mountain heights. If the next mountain is nearly the same height as the current one, the balloon moves gently. If the difference is large, the balloon struggles and the journey becomes more costly. Nobita quickly realizes that calculating the total effort for a long trip is not easy at all.

Doraemon, seeing Nobita's frustration, pulls out yet another gadget from his pocket. This one has the power to increase the heights of an entire stretch of mountains all at once. With just a flick, Doraemon can make a group of mountains taller. Naturally, Nobita becomes excited because this means he can reshape the mountains before planning his balloon routes. But now the situation is even more complex: the mountain heights are changing, and Nobita still wants to know the cost of his planned trips.

You are given a sequence of operations, describing either Doraemon's gadget use or Nobita's trip queries. There are two types of operations:

  1. Gadget Boost: Written as 1 l r x — Doraemon uses his gadget to adjust every mountain between $$$l$$$ and $$$r$$$ (inclusive). Each of these mountains has its height increased by $$$x$$$.
  2. Trip Query: Written as 2 l r — Nobita imagines starting at mountain $$$l$$$, then floating to $$$l+1$$$, then to $$$l+2$$$, and so on until reaching mountain $$$r$$$. The cost of this trip is the sum of the efforts required for each step. Nobita wants to know this total value after all changes so far have been applied.

Your task is to follow this summer adventure, processing every operation in the given order. When Nobita asks about a trip, you must calculate and report the correct cost at that moment.

Input

The first line of input contains two integers $$$n$$$ and $$$q$$$ ($$$1 \le n,q \le 3 \cdot 10^5$$$) — the number of mountains and the number of queries.

The second line of input contains n integers $$$a_1,\dots ,a_n$$$ ($$$1 \le a_i \le 10^9$$$) — the height of the mountains.

The next q lines contain query descriptions. Each of them contains integers $$$t, l, r$$$ and may contain $$$x$$$ ($$$1 \le t_i \le 2, 1 \le l \le r \le n, 1 \le x_i \le 10^9$$$). Here $$$t = 1$$$ corresponds to the gadget boost and $$$t = 2$$$ corresponds to the trip query.

It's guaranteed that the input will contain at least one trip query.

Output

For each trip query, print the answer.

Examples
Input
5 6
5 1 4 4 7
2 1 5
1 2 4 3
2 1 5
2 3 3
1 3 5 2
2 2 4
Output
10
4
0
5
Input
10 9
9 3 18 11 17 19 10 7 10 18
1 1 2 10
1 6 8 8
2 2 9
1 9 9 10
1 6 10 15
1 2 7 4
2 1 10
1 1 4 14
2 3 8
Output
45
68
56