题目描述

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.

题目大意

题目描述

注意：本题的时间限制为 4 秒，是默认限制的两倍。

Bessie 正在度假！由于最近的技术进步，Bessie 可以通过先进的航班旅行，这些航班甚至可以进行时间旅行。此外，即使存在多个“平行”的 Bessie 同时出现也不会有任何问题。

在这个国家，有 $N$ 个机场，编号为 $1,2,\cdots,N$，以及 $M$ 条时间旅行航班（$1 \leq N,M \leq 200000$）。第 $j$ 条航班从机场 $c_j$ 在时间 $r_j$ 起飞，并在时间 $s_j$ 抵达机场 $d_j$（$0 \leq r_j,s_j \leq 10^9$，$s_j < r_j$ 是可能的）。此外，Bessie 在机场 $i$ 需要停留 $a_i$ 时间（$1 \leq a_i \leq 10^9$）。也就是说，如果 Bessie 乘坐一趟航班在时间 $s$ 抵达机场 $i$，她可以转乘一趟从该机场出发的航班，只要该航班的起飞时间 $r \geq s + a_i$。需要注意的是，停留时间不会影响 Bessie 抵达某机场的实际时间。

Bessie 从城市 $1$ 出发，起始时间为 $0$。对于从 $1$ 到 $N$ 的每个机场，求出 Bessie 最早可以到达该机场的时间。

输入格式

第一行输入包含两个整数 $N$ 和 $M$。

接下来的 $M$ 行描述航班信息。其中第 $j$ 行包含 $c_j, r_j, d_j, s_j$，依次表示航班的起飞机场、起飞时间、降落机场和降落时间。$(1 \leq c_j,d_j \leq N, 0 \leq r_j,s_j \leq 10^9)$

接下来的 $1$ 行描述每个机场的停留时间。该行包含 $N$ 个用空格分隔的整数，分别为 $a_1,\cdots,a_N$。

输出格式

输出共 $N$ 行。第 $i$ 行输出 Bessie 最早到达机场 $i$ 的时间；如果无法到达该机场，输出 $-1$。

样例 1 的解释

Bessie 可以按照给定的顺序乘坐第 $3$ 班航班，这使她可以在时间 $0$ 到达机场 $1$ 和机场 $2$，以及在时间 $20$ 到达机场 $3$。

注意，这条路线会两次经过机场 $2$，第一次是在时间 $10-11$，第二次是在时间 $0-1$。

样例 2 的解释

在这个例子中，Bessie 可以乘坐第 $1$ 班航班，在时间 $10$ 抵达机场 $2$。但是，她无法及时赶上第 $2$ 班航班，因为该航班的起飞时间为 $10$，而她需要至少 $1$ 个时间单位来完成停留。

评分标准

• 测试点 $3-5$：对于每个 $j$，$r_j < s_j$，也就是说所有航班的到达时间晚于起飞时间。
• 测试点 $6-10$：$N,M \leq 5000$
• 测试点 $11-20$：无额外限制。

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.