Bessie is on vacation! Due to some recent technological advances, Bessie will travel via technologically sophisticated flights, which can even time travel. Furthermore, there are no issues if two "parallel" versions of Bessie ever meet. In the country, there are $N$ airports numbered $1,2,\ldots,N$ and $M$ time-traveling flights $(1 \leq N,M \leq 200000)$. Flight $j$ leaves airport $c_j$ at time $r_j$ and arrives at airport $d_j$ at time $s_j$ ($0 \leq r_j,s_j \leq 10^9, s_j \lt r_j$ is possible). In addition, she must leave $a_i$ time for a layover at airport $i$ $(1 \leq a_i \leq 10^9)$. (That is to say, if Bessie takes a flight arriving at airport $i$ at time $s$, she can then transfer to a flight leaving the airport at time $r$ if $r \geq s + a_i$. The layovers do not affect when Bessie arrives at an airport.) Bessie starts at city $1$ at time $0$. For each airport from $1$ to $N$, what is the earliest time when Bessie can get to it?

The first line of input contains $N$ and $M$. The next $M$ lines describe flights. The $j$-th of these lines contains $c_j, r_j, d_j, s_j$ in that order. $(1 \leq c_j, d_j \leq N, 0 \leq r_j, s_j \leq 10^9)$ The next line describes airports. It contains $N$ space-separated integers $a_1, \ldots, a_N$.

There are $N$ lines of output. Line $i$ contains the earliest time when Bessie can get to airport $i$, or `-1` if it is not possible for Bessie to get to that airport.

In this case, Bessie can take flight $1$, arriving at airport $2$ at time $10$. However, she does not arrive in time to also take flight $2$, since the departure time is $10$ and she cannot make a $1$ time-unit layover.