BCCI is really angry with players for showing such a disastrous performance. They have called all the players to a special temple where they asked them to stand in a straight line. There were “N” players in the temple. BCCI marked their positions as 0, 1, 2 up to N-1. After that they called Mr. Aloknath to give them blessings. He chooses two integers X and Y (X <= Y), and gives “K” units of blessings to all the players standing at positions between X and Y (inclusive). He repeats this process “M” number of times. Can you tell us what will be the total units of blessings each player will have in the end?

Input

The first line contains two integers “N” and “M”. Each of the next “M” lines will contain three integers X, Y and K.

Output

Output “N” integers Ai (0 <= i < N) in separate lines where Ai is the units of blessings player standing at position i will have in the end.

Constraints

1 <= N <= 10^6

1 <= M <= 10^5

0 <= A <= B <= N-1

0 <= K <= 1000

Example

Input:
5 5
0 4 3
0 2 1
1 3 0
1 4 2
2 2 3

Output:
4
6
9
5
5