Question

Irrigation Canal Water Levels

A farm has N plots of land in a row, numbered 0 to N-1. Initially, every plot has a water level of 0.

There are Q irrigation operations. Each operation is described by three integers l, r, and val, meaning the water level of every plot from index l to index r (inclusive) is increased by val (note that val may be negative, representing drainage).

After applying all Q operations in order, output the final water level of every plot.

Input

The first line contains two integers KaTeX can only parse string typed expression and KaTeX can only parse string typed expression — the number of plots and the number of irrigation operations.

Each of the next KaTeX can only parse string typed expression lines contains three integers KaTeX can only parse string typed expression, KaTeX can only parse string typed expression, and KaTeX can only parse string typed expression.

Output

Print KaTeX can only parse string typed expression integers separated by spaces — the final water level of each plot, in order.

Example

Example 1:
Input

Output

5 3 13 -2 -2

Explanation
Start with KaTeX can only parse string typed expression. After the first operation: KaTeX can only parse string typed expression. After the second: KaTeX can only parse string typed expression. After the third: KaTeX can only parse string typed expression.

Example 2:
Input

1 1

0 0 100

Output

Explanation
With a single plot and a single operation covering it, the final level is simply KaTeX can only parse string typed expression.

Example 3:
Input

10 0

Output

0 0 0 0 0 0 0 0 0 0

Explanation
With no operations at all, every plot remains at its initial level of KaTeX can only parse string typed expression.

Online

Explore Newton School

Recent Questions

Most Solved Questions

Least Solved Questions