Seat bookings after range updates

Problem

A coaching centre rents seats in a study hall for n days. A booking says: reserve c seats on every day from day l to day r, both days included. There are m bookings.

After all bookings, print the total number of reserved seats for each day.

Input, output and limits

Input: The first line has two integers n and m. Each of the next m lines has three integers l, r and c.
Output: One line with n integers separated by spaces: the total reserved seats on days 1 to n.
Constraints: 1 ≤ n, m ≤ 10^5
1 ≤ l ≤ r ≤ n
1 ≤ c ≤ 10^9

Examples

Example

Input

Output

2 3 3 7 1

Day 4 gets 1 seat from the second booking and 6 from the third: 7 in total.

Hints

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

Hint 1

Adding c to every day of every booking can take 10^10 steps.

Hint 2

Mark only where a booking starts and where it stops: add c at day l and subtract c right after day r.

Hint 3

After all bookings, a running total over the marks gives the real count for each day.

Hint 4

Make the mark array size n + 2 so that "right after day n" has a place. Use long.

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

Solve in the editor

All Java problems

Problem

Input, output and limits

Examples

Hints

More Prefix Sum & Hashing problems

Problem

Input, output and limits

Examples

Hints

More Prefix Sum & Hashing problems