Range add updates

Problem

A warehouse has n shelves numbered from 0, all empty. Each of q deliveries adds v units to every shelf from l to r, both included. Print the number of units on each shelf at the end.

Input, output and limits

Input: The first line has n and q. Each of the next q lines has l, r and v.
Output: One line with n integers separated by spaces.
Constraints: 1 ≤ n ≤ 100000
1 ≤ q ≤ 100000
0 ≤ l ≤ r < n
-1000 ≤ v ≤ 1000

Examples

Example

Input

8 2
1 4 5
3 6 2

Output

0 5 5 7 7 2 2 0

Shelves 3 and 4 get both deliveries.

Hints

Try the problem first. Open one hint at a time.

Hint 1

Looping over every range is too slow when n and q are large.

Hint 2

Record +v at l and -v at r + 1, then take a running total.

Write your Python code, run it on the examples and submit it to hidden tests.

Solve in the editor

Blocks divisible by kmedium
Block sums in a tablemedium
Blocks with a given totalmedium
Longest block with a given totalmedium
Group the anagramsmedium

All Python problems

Problem

Input, output and limits

Examples

Hints

More Prefix Sums & Hashing problems

Problem

Input, output and limits

Examples

Hints

More Prefix Sums & Hashing problems