Quarry

Useful minerals were found on a plot of land. The owner plans to install a new automatic excavation system, operate it, and turn the plot into a quarry.

The system digs one pit at a time. A pit starts at position $S_i$ and ends at position $E_i$, both measured in meters from the start of the quarry, and its depth is $H_i$ meters.

The quarry can be drawn as a two-dimensional diagram that shows the elevation above sea level along the quarry, both at the beginning and after mineral extraction starts.

The system works by carrying out excavation commands. Each command lowers the elevation by $H_i$ meters on the interval $[S_i, E_i]$. Figure 1 shows the elevation after two commands: the first digs on $[0; 2]$, the second digs on $[1; 3]$, and each digs a pit 1 meter deep. The area dug by the first command is green (light gray in the grayscale print), and the area dug by the second is blue (gray in the grayscale print).

Figure 1.

The owner knows which excavation commands will be given to the system. Before starting, the owner wants to know what the quarry will look like after all commands are executed.

Find the elevation of the quarry after all excavation commands are executed.

The first line contains two integers, the length of the quarry $N$ and the number of commands $K$.

The second line contains $N$ integers $A_i$, the initial elevation above sea level at $i$ meters from the start of the quarry. The first value is the elevation at 0 meters from the start.

Each of the next $K$ lines contains three integers $S_i$, $E_i$, and $H_i$, the start, end, and depth of the $i$-th excavation command.

Print $N$ numbers. The $i$-th number is the elevation at $i$ meters from the start of the quarry after all commands are executed.

The final elevation can be negative.

$0 \le S_i \le E_i < N \le 250\,000$

$1 \le K \le 250\,000$

$-1\,000 \le A_i, H_i \le 1\,000$