DZY yêu màu sắc (DZY Loves Colors)

Nguồn: Codeforces

Phiên bản: Phước Hưng OJ Extended

Đề bài

Có dải băng gồm $n$ ô, đánh số 1 đến $n$. Ban đầu màu của ô $i$ là $i$ và độ rực rỡ của mỗi ô bằng 0.

Khi tô một ô đang có màu $y$ bằng màu $x$, độ rực rỡ của ô tăng $|x-y|$ rồi màu trở thành $x$.

Có $m$ thao tác:

• 1 l r x: tô toàn bộ ô $l..r$ bằng màu $x$.
• 2 l r: in tổng độ rực rỡ của các ô $l..r$.

Input

Dòng đầu chứa $n,m$. Mỗi trong $m$ dòng tiếp theo là 1 l r x hoặc 2 l r.

Output

Với mỗi thao tác loại 2, in tổng độ rực rỡ trên một dòng.

Subtask

• Subtask 1 (20%): n,m≤30; các điều kiện khác giữ như bài đầy đủ.

• Subtask 2 (30%): n,m≤3000; các điều kiện khác giữ như bài đầy đủ.

• Subtask 3 (50%): toàn bộ giới hạn:

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

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

• $1\le x\le10^8$

Ví dụ

Input

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

Output

8

Giải thích

Ban đầu màu [1,2,3], beauty [0,0,0]. Sơn 1..2 bằng 4: beauty thành [3,2,0]. Sơn 2..3 bằng 5: ô 2 tăng thêm 1, ô 3 tăng 2, beauty [3,3,2]; tổng là 8.