DZY Loves Colors

Source: Codeforces

Version: Phuoc Hung OJ Extended

Problem Statement

There are $n$ ribbon units. Initially unit $i$ has color $i$ and colorfulness 0. Painting a unit whose current color is $y$ with color $x$ increases its colorfulness by $|x-y|$ and changes its color to $x$.

Process $m$ operations:

• 1 l r x: paint every unit $l..r$ with color $x$.
• 2 l r: print the total colorfulness on $l..r$.

Input

The first line contains $n,m$. Each of the next $m$ lines is 1 l r x or 2 l r.

Output

For every type-2 operation, print the total colorfulness on its own line.

Subtasks

• Subtask 1 (20%): n,m≤30; all other conditions are unchanged.

• Subtask 2 (30%): n,m≤3000; all other conditions are unchanged.

• Subtask 3 (50%): full constraints:

• $1\le n,m\le10^5$

• $1\le l\le r\le n$

• $1\le x\le10^8$

Examples

Input

3 3
1 1 2 4
1 2 3 5
2 1 3

Output

8

Explanation

After painting positions 1..2 with color 4, colorfulness is [3,2,0]. Painting positions 2..3 with color 5 changes it to [3,3,2], whose sum is 8.