{"raw_statement":[{"iden":"statement","content":"**Note: The time limit for this problem is 4s, twice the default.**\n\nBessie 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.\n\nIn the country there are $N$ airports numbered $1,2,\\cdots ,N$ and $M$ time-traveling flights $(1 \\le N,M \\le 200000)$. Flight $j$ leaves airport $c_j$ at time $r_j$, and arrives in airport $d_j$ at time $s_j (0 \\le rj,sj \\le 10^9$, $s_j<r_j$ is possible$)$. In addition, she must leave $a_i$ time for a layover at airport $i (1 \\le a_i \\le 10^9)$. (That is to say, if Bessie takes a flight arriving in airport $i$ at time $s$, she can then transfer to a flight leaving the airport at time $r$ if $r \\ge s+a_i$. The layovers do not affect when Bessie arrives at an airport.)\n\nBessie starts at city $1$ at time $0$. For each airport from $1$ to $N$, what is the earliest time when Bessie can get to at it? "},{"iden":"input","content":"The first line of input contains $N$ and $M$.\n\nThe next $M$ lines describe flights. The $j$-th of these lines contains $c_j, r_j, d_j, s_j$ in that order. $(1 \\le c_j,d_j \\le N, 0 \\le r_j,s_j \\le 10^9)$\n\nThe next line describes airports. It contains $N$\nspace separated integers, $a_1, \\cdots ,a_N$. "},{"iden":"output","content":"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. "},{"iden":"note","content":"### Explanation for Sample 1\n\nBessie can take the $3$ flights in the listed order, which allows her to arrive at airports $1$ and $2$ at time $0$, and airport $3$ at time $20$.\n\nNote that this route passes through airport $2$ twice, first from time $10-11$ and then from time $0-1$.\n\n### Explanation for Sample 2\n\nIn 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. \n\n### SCORING\n\n - Inputs $3-5$: $r_j<s_j$ for all $j$, i.e. all flights arrive after they depart.\n - Inputs $6-10$: $N,M \\le 5000$\n - Inputs $11-20$: No additional constraints."}],"translated_statement":null,"sample_group":[["3 3\n1 0 2 10\n2 11 2 0\n2 1 3 20\n10 1 10","0\n0\n20"],["3 3\n1 0 2 10\n2 10 2 0\n2 1 3 20\n10 1 10","0\n10\n-1"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}