题目描述

Note: The time limit for this problem is 4s, twice the default.

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,\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.)

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 at 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 \le c_j,d_j \le N, 0 \le r_j,s_j \le 10^9)$

The next line describes airports. It contains $N$ space separated integers, $a_1, \cdots ,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.

题目大意

题意

Bessie 正在旅游！有 $n$ 个城市和 $m$ 条航线，第 $i$ 条航线有 $(c_i,r_i,d_i,s_i)(1\leq c_i\neq d_i\leq n,0\leq r_i,s_i\leq 10^9)$ 的限制，表示从 $c_i$ 到 $d_i$，最迟 $r_i$ 时进入，$s_i$ 时到达。第 $i$ 个城市有 $a_i$ 的停泊时间，表示 乘坐航班到达 $i$ 后，需要等待 $a_i$ 的时间后才能继续飞行。问到达每个城市的最早时间？如果不能到达，输出 -1，注意可能存在时间隧道，即到达时间$s_i$可能小于出发时间$r_i$。

输入格式

第一行两个整数 $n,m$。

接下来 $m$ 行每行四个整数 $c_i,r_i,d_i,s_i$。

接下来一行 $n$ 个整数，表示 $a_i$。

输出格式

$n$ 行，第 $i$ 行一个整数表示到达 $i$ 的最早时间，不能到达输出 -1。

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

提示

Explanation for Sample 1

Bessie 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$.

Note that this route passes through airport $2$ twice, first from time $10-11$ and then from time $0-1$.

Explanation for Sample 2

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.

SCORING

• Inputs $3-5$: $r_j<s_j$ for all $j$ , i.e. all flights arrive after they depart.
• Inputs $6-10$: $N,M \le 5000$
• Inputs $11-20$: No additional constraints.