$N$ Tarotians live on one street of the form of a straight line. The $i$-th Tarotian lives in a house at street number $s_i$.
To supply water to them, the Magician can choose two citizens on the street, then water of a specific amount will magically flow in to their houses, and the houses in between. For example, if the Magician chooses two citizens who lives in house 3 and 6 respectively, citizens who lives in houses 3-6 will all receive the same amount of water.
The Magician would like to do this $Q$ times. Each time specifying which two citizens $u_i, v_i$ they chose, and the amount of water $w_i$ to supply to.
Your task is to find out how much water each Tarotian has received after the supplyment of water.

Input

The first line consists of two integers $N$ and $Q$. The second line consists of $N$ integers $s_i$. Then, $Q$ lines follow. Each line consists of three integers, $u_i, v_i, $ and $w_i$.

Output

Output $n$ integers, the $i^{th}$ integer represents the amount of water citizen $i$ received after the $Q$ additions of water.

Constraints

For all testcases: $1 \le N, Q \le 10^6$, $1 \le u_i, v_i, s_i \le N$, $1 \le w_i \le 10^9$.
Subtask 1 (30%): $N, Q \le 10^3$
Subtask 2 (70%): No other constraints