P9126 [USACO23FEB] Moo Route II S

注意：本题的时间限制为 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$：无额外限制。

### 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