Sun Wukong was honored as the great saint of Qitian. He was very happy, so he held a peach meeting for the monkeys (ID numbered 1 to N). To make it more interesting, Sun Wukong decided to throw the dice. The conference will roll the dice Q times, forming Q instructions, each in the form of ’m a b’, where m is an integer label, and a and b are monkey’s ID. The meaning of each instruction is as follows:
1. If m > 0, send m peaches to each monkey in ID interval [a, b];
2. If m < 0, remove |m| peaches from each monkey in the ID interval [a, b] (if the number of peaches from any monkey is less than |m|, remove all peaches of the monkey);
3. If m = 0, calculate the sum of peaches of each monkey in the interval [a, b]; now you are invited to preside over the peach conference, can you complete the task according to the requirements of Sun Wukong?
输入描述:
The fifirst line contains two positive integers N and Q (1 ≤ N, Q ≤ 100000), representing N monkeys and Q instructions, respectively.
Next, there are Q lines, and each line corresponds to one instruction. Each instruction is composed of three integers m (−10000 ≤ m ≤ 10000), a and b (1 ≤ a ≤ b ≤ N), which respectively represent the label m and the ID interval of monkey.
输出描述:
Output each instruction with label m = 0 as an integer in order per line, that is, the sum of peaches of each monkey in the interval [a, b].
示例1
输入
复制
10 8
1 1 10
0 4 6
2 3 6
0 4 5
-2 5 8
0 4 7
-2 4 5
0 3 5