Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Just Another Range Query

Limits: 1s, 256 MB

This is another simple range query problem where you will perform some updates and answer some queries. Let’s take an array A of length N. Initially, A[i] = i for each i in the range [1,N].

You will have to perform Q operations on this array. There will be two types of operations:

  • 1 L R V - which means that you will have to subtract V from all A[i] such that L ≤ i ≤ R.
  • 2 L R - which means that you will have to print the sum of all A[i] such that L ≤ i ≤ R.

Input

In the first line of input, there will be two integers N and Q (1 ≤ N ≤ 109, 1 ≤ Q ≤ 105) which are the length of the array and number of operations to perform respectively.

Next Q lines will contain the description of the operations to perform in the format 1 L R V or 2 L R (1 ≤ L ≤ R ≤ N, 1 ≤ V ≤ 105).

Output

For each operation of the format 2 L R, print the answer of the query in a single line.

Samples

InputOutput
10 5
2 1 5
1 4 8 10
2 2 7
1 1 10 1
2 1 10
15
-13
-5

Author
Discussion
Submit

Login to submit