P14418 [JOISC 2014] 巴士走读 / Bus

大学生 JOI 君乘坐公交车上下学。JOI 君的家和他所就读的大学都位于 IOI 市内。IOI 市共有 $N$ 个公交站，编号从 $1$ 到 $N$。JOI 君家最近的公交站是公交站 $1$，大学最近的公交站是公交站 $N$。 IOI 市内运行的公交车共有 $M$ 辆，每辆公交车每天仅运行一次，按照预定时刻从指定的公交站出发，并在预定时刻到达指定的公交站。不存在每天多次运行的公交车。JOI 君在途中不能从一辆公交车换乘到另一辆公交车。 JOI 君每天乘坐一辆或多辆公交车前往大学。JOI 君换乘公交车所需的时间可以忽略不计。换句话说，只要在某个时刻有公交车从当前所在的公交站出发，他就可以换乘该车，前提是该车的发车时刻或更早之前他已经到达该公交站。此外，他可以多次利用同一公交站。 在上述条件下，JOI 君希望知道，每天从家出发后，是否能在上课前抵达大学。但大学每天第一节课的开始时间各不相同。已知在接下来的 $Q$ 天里，每天为了赶上第一节课，他最晚必须在公交站 $N$ 到达。对于每一天，JOI 君想知道，最晚何时必须从公交站 $1$ 出发，才能赶上当天的课程。 **题目** 给定公交车运行的相关信息，以及接下来 $Q$ 天中每天为了赶上课程必须到达公交站 $N$ 的最晚时间，对于每一天，求出 JOI 君最晚必须在何时从公交站 $1$ 出发才能赶上当天的课程。

从标准输入读取以下输入数据： - 第 $1$ 行包含两个整数 $N$ 和 $M$，以空格分隔，表示 IOI 市内共有 $N$ 个公交站，有 $M$ 辆公交车运行。 - 接下来的 $M$ 行中，第 $i$ 行（$1 \le i \le M$）包含四个整数 $A_i$、$B_i$、$X_i$、$Y_i$（满足 $1 \le A_i \le N$，$1 \le B_i \le N$，$A_i \ne B_i$），以空格分隔。这表示第 $i$ 辆公交车在时刻 $X_i$ 从公交站 $A_i$ 出发，在时刻 $Y_i$ 到达公交站 $B_i$。其中，时刻是以午夜 $0$ 点起经过的毫秒数表示的。 - 下一行包含一个整数 $Q$，表示给出“必须在公交站 $N$ 到达”的日期共有 $Q$ 天。 - 接下来的 $Q$ 行中，第 $j$ 行（$1 \le j \le Q$）包含一个整数 $L_j$，表示在第 $j$ 天，必须在时刻 $L_j$ 之前到达公交站 $N$。

向标准输出输出 $Q$ 行。第 $j$ 行（$1 \le j \le Q$）应输出一个整数，表示在第 $j$ 天，JOI 君最晚必须在何时到达公交站 $1$ 才能赶上当天的课程。如果无论如何都无法在上课前抵达大学，则输出 $-1$。

### 样例 1 解释 无法在时刻 $10$ 前到达公交站 $5$。 为了在时刻 $30$ 前到达，只需在时刻 $5$ 乘坐第 $4$ 辆公交车。 为了在时刻 $60$ 前到达，可以按以下方式操作： - 在时刻 $10$ 乘坐第 $1$ 辆公交车。 - 在时刻 $25$ 到达公交站 $2$，等待 $1$ 毫秒后换乘第 $3$ 辆公交车。 - 在时刻 $50$ 到达公交站 $5$。 为了在时刻 $100$ 前到达，可以按以下方式操作： - 在时刻 $30$ 乘坐第 $5$ 辆公交车。 - 在时刻 $40$ 到达公交站 $4$，等待 $10$ 毫秒后换乘第 $6$ 辆公交车。 - 在时刻 $70$ 到达公交站 $5$。 ### 数据范围 所有输入数据满足以下条件： - $2 \le N \le 100\,000$。 - $1 \le M \le 300\,000$。 - $0 \le X_i < Y_i < 86\,400\,000\ (= 24 \times 60 \times 60 \times 1000)$（$1 \le i \le M$）。 - $1 \le Q \le 100\,000$。 - $0 \le L_j < 86\,400\,000\ (= 24 \times 60 \times 60 \times 1000)$（$1 \le j \le Q$）。 ### 子任务 **子任务 1 [20 分]** 满足以下条件： - $N \le 2000$。 - $M \le 2000$。 - $Q = 1$。 **子任务 2 [15 分]** 满足以下条件： - $N \le 2000$。 - $M \le 2000$。 **子任务 3 [15 分]** 满足以下条件： - $Q = 1$。 **子任务 4 [50 分]** 无额外限制。 翻译由 Qwen3-235B 完成