Shahwat has a stick that has n blocks that are indexed from 1 to n (from first to last). Each block has a beauty number written on it (Initially, it is the index number) and an abstract number which is invisible. Initially, all abstract numbers are 0. Then Shahwat will make k queries.
Each query can be of the following two types:
- Type 1: He will give a range L, R, and an integer A. Here, beauty numbers of every block from L to R (inclusive) will be replaced by A. Suppose, one of the blocks from L to R (inclusive) had a beauty number B. After replacing, the beauty number of that block becomes A. After that, the abstract number of that block increases by the difference between A and B.
- Type 2: He will ask the summation of the abstract numbers between L and R (inclusive).
Input
The first line contains two integers n, k (1 ≤ n, k ≤ 2 * 105), denoting the number of blocks and the number of queries, respectively.
Each of the next k lines begins with an integer type (1 ≤ type ≤ 2), denoting the type of the query.
If the type of the query is 1, three space-separated integers L, R, A (1 ≤ L ≤ R ≤ n; 0 ≤ A ≤ 108) will follow.
If the type of the query is 2, two space-separated integers L, R (1 ≤ L ≤ R ≤ n) will follow.
Output
For each query of type 2, print a line denoting the summation of abstract numbers.
Sample
| Input | Output |
|---|---|
10 6 1 1 5 3 2 2 7 1 4 10 11 1 3 8 12 1 1 6 3 2 1 10 | 4 87 |
