The battle has concluded! hewmatt10 has lost the brutal war and was once again, removed of all of his past artworks. Wanting to cherish the last moments of his reign before inevitably returning to [REDACTED]'s torture chamber, hewmatt10 wants to remember as many contents from his art gallery as possible.

Containing ~N~ paintings numbered from ~1~ to ~N~ each with a colourfulness ~c_i~, hewmatt10 has recalled ~Q~ snapshots of him staring at his art gallery from afar, knowing the sum ~s_i~ of colourfulness across all paintings between ~l~ and ~r~, inclusive.

Your task is to take these snapshots and determine a valid solution for the colourfulness of each painting.

Input Specification

On the first line, two integers, ~N~ and ~Q~ ~(1~ ~\le~ ~N,~ ~Q~ ~\le~ ~10^5)~.

On the next ~Q~ lines, three integers ~l~, ~r~ ~(1 \le l \le r \le N)~, and ~s_i~ ~(1 \le \vert s_i \vert \le 10^9)~, representing an individual snapshot.

Output Specification

~N~ integers ~c_i~ ~(0 \le \vert c_i \vert \le 10^{18})~, indicating the colourfulness of each painting. If there are multiple solutions, output any one. It is guaranteed that there will be at least one solution.

Subtasks

For this problem, all subtasks are disjoint, and you are NOT required to pass previous subtasks to earn points for a specific subtask.

Subtask	Description	Points
1	~1~ ~\le~ ~N, Q~ ~\le~ ~10~. There will exist a solution such that ~ \vert c_i \vert \le 1~.	10
2	~1~ ~\le~ ~N, Q~ ~\le~ ~400~.	15
3	~1~ ~\le~ ~N, Q~ ~\le~ ~2000~.	20
4	~l~ will be unique for all queries.	15
5	No further constraints.	40

Sample Input

10 8
1 5 5
3 4 2
7 9 3
6 9 4
1 10 10
2 10 9
3 5 3
6 6 1

Sample Output

1 1 1 1 1 1 1 1 1 1

Explanation

If you add up all of the subarrays in the snapshots, you will end up with ~s_i~. For example, the sum of all elements from index ~1~ to ~5~ is ~5~, the sum of all elements from ~3~ to ~4~ is ~2~, etc. Note that 1 1 2 0 1 1 3 0 0 1 is also one of the various valid solutions.