题目描述

大学生 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$。

5 6
1 2 10 25
1 2 12 30
2 5 26 50
1 5 5 20
1 4 30 40
4 5 50 70
4
10
30
60
100

-1
5
10
30

3 8
1 2 1 5
1 3 0 1
1 3 2 8
2 3 2 3
2 3 3 4
2 3 4 5
2 3 5 6
2 3 6 7
6
3
4
5
6
7
8

0
0
0
1
1
2

提示

样例 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 完成