Problem Statement

In AtCoder Kingdom, there is a railway line extending east-west, and this line has stations $1,2,\ldots,N$. Station $i\ (1\leq i\leq N)$ is located at coordinate $x_i$ $(x_1 < x_2 < \ldots < x_N)$.

On this line, AtCoder Express company operates $M$ types of express trains.

The $i$-th type of express train operates as follows:

• You can board this train at one of the stations $l_i,l_i+1,\ldots,r_i$.
• You can get off this train at one of the stations $L_i, L_i+1, \ldots, R_i$. Here, the train travels in one direction, either east or west, satisfying $r_i\lt L_i$ or $R_i\lt l_i$.
• The fare consists of a base fare of $c_i$ plus an amount based on the distance from the boarding station to the destination station. Specifically, when traveling from station $s\ (l_i\leq s\leq r_i)$ to station $t\ (L_i\leq t\leq R_i)$, the fare is $c_i+|x_s-x_t|$.

You are currently at station $1$. For each $k\ (2\leq k\leq N)$, determine whether you can travel from station $1$ to station $k$ by transferring between express trains, and if you can travel, find the minimum total fare required for the travel.

Constraints

• $2\leq N\leq 10^5$
• $1\leq M\leq 10^5$
• $0\leq x_1 < x_2 < \ldots < x_N \leq 10^{12}$
• $1\leq l_i\leq r_i\leq N, 1\leq L_i\leq R_i\leq N$
• $r_i\lt L_i$ or $R_i\lt l_i$.
• $1\leq c_i\leq 10^{12}$
• All input values are integers.

Input

The input is given from Standard Input in the following format:

N M
x_1 x_2 \ldots x_N
l_1 r_1 L_1 R_1 c_1
l_2 r_2 L_2 R_2 c_2
\vdots
l_M r_M L_M R_M c_M

Output

Output the answer in the following format:

\mathrm{ans}_2 \mathrm{ans}_3 \ldots \mathrm{ans}_N

$\mathrm{ans}_i$ is the answer for $k=i$. If you can travel from station $1$ to station $i$, $\mathrm{ans}_i$ is the minimum total fare required for the travel; otherwise, $\mathrm{ans}_i$ is -1.