8940: Carrot Trees

链接：https://ac.nowcoder.com/acm/contest/57355/C
来源：牛客网
Walk Alone planted n magical carrot trees in a row. Let ai denote the number of carrots on the i-th tree (note that ai is a real number). Initially, there are no carrots on any tree. On each day, he can do one of the following two operations on the trees:

• 1 l r x. Water all carrot trees between l and r inclusively. After that, ai will increase by x/k immediately for all l≤i≤r, where k is a constant in all operations.

• 2 l r. Pick a carrot from all trees between l and $r$ inclusively and having at least one carrot. After that, ai will decrease by 1 for all integers $i$ where l≤i≤r and ai≥1.

After m days, Walk Alone has picked many carrots, and he wants you to tell him the total number of carrots he harvested.

The first line contains three integers n (1≤n≤10^6), m (1≤m≤2⋅10^5) and k (1≤k≤10^9), indicating the number of carrots, the number of operations, and the constant in the first operation.
Each of the following m lines indicates an operation, the format of which is as above. It is guaranteed that 1≤ℓ≤r≤n and 1≤x≤10^9.

Output an integer indicating the total number of carrots.