绝世武功

题目描述

小明在练习绝世武功， $n$ 个练功桩排成一排，一开始每个桩的损伤为 $0$。

接下来小明会练习 $m$ 种绝世武功，每种武功都会对 $[l, r]$ 区间分别造成 $[s,e]$ 的伤害。

这个伤害是一个等差序列。例如 $l = 1, r = 4, s = 2, e = 8$ ,则会对 $1-4$ 号练功桩造成$2， 4， 6， 8$ 点损伤。

小明想让你统计一下所有练功桩的损伤的和。

输入描述

第一行输入 $n, m$，代表练功桩的数量和绝世武功的种类数。

接下来 $m$ 行输入 $4$ 个整数 $l, r, s, e$ 。

$1 \leq n \leq 10^7 , 1\leq m \leq 3 \times 10 ^ 5 , 1\leq l, r \leq n$

输出描述

输出一个整数代表所有练功桩的损伤和， 题目保证所有输入输出都在 $[0, 9 \times 10^{18}]$

输入输出样例

示例 1

>输入

6 2
1 5 2 10
2 4 1 1

>输出

33