Moo Route II

문제

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 $NN$ airports numbered $1,2,\dots ,N1,\; 2,\; \backslash ldots,\; N$ and $MM$ time-traveling flights ($1\le N,M\le 2000001\backslash leq\; N,\; M\; \backslash leq\; 200000$). Flight $jj$ leaves airport $c_{j}c\_j$ at time $r_{j}r\_j$, and arrives in airport $d_{j}d\_j$ at time $s_{j}s\_j$ ($0\le r_j,s_j\le {10}^{9}0\; \backslash leq\; r\_j,\; s\_j\; \backslash leq\; 10^9$, is possible). In addition, she must leave $a_{i}a\_i$ time for a layover at airport $ii$ ($1\le a_i\le {10}^{9}1\backslash le\; a\_i\backslash le\; 10^9$). (That is to say, if Bessie takes a flight arriving in airport $ii$ at time $ss$, she can then transfer to a flight leaving the airport at time $rr$ if $r\ge s+a_{i}r\; \backslash geq\; s\; +\; a\_i$. The layovers do not affect when Bessie arrives at an airport.)

Bessie starts at city $11$ at time $00$. For each airport from $11$ to $NN$, what is the earliest time when Bessie can get to at it?

입력

The first line of input contains $NN$ and $MM$.

The next $MM$ lines describe flights. The $jj$th of these lines contains $c_{j}c\_j$, $r_{j}r\_j$, $d_{j}d\_j$, $s_{j}s\_j$ in that order. ($1\le c_j,d_j\le N1\backslash leq\; c\_j,\; d\_j\; \backslash leq\; N$, $0\le r_j,s_j\le {10}^{9}0\backslash leq\; r\_j,\; s\_j\; \backslash leq\; 10^9$)

The next line describes airports. It contains $NN$ space separated integers, $a_1,\dots ,a_{N}a\_1,\; \backslash ldots,\; a\_N$.

출력

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

3 3
1 0 2 10
2 11 2 0
2 1 3 20
10 1 10

0
0
20

3 3
1 0 2 10
2 10 2 0
2 1 3 20
10 1 10

0
10
-1