#214540. [JOISC 2014] 巴士走读 / Bus

大学生 JOI 君乘坐公交车上下学。JOI 君的家和他所就读的大学都位于 IOI 市内。IOI 市共有 个公交站，编号从 到 。JOI 君家最近的公交站是公交站 ，大学最近的公交站是公交站 。

IOI 市内运行的公交车共有 辆，每辆公交车每天仅运行一次，按照预定时刻从指定的公交站出发，并在预定时刻到达指定的公交站。不存在每天多次运行的公交车。JOI 君在途中不能从一辆公交车换乘到另一辆公交车。

JOI 君每天乘坐一辆或多辆公交车前往大学。JOI 君换乘公交车所需的时间可以忽略不计。换句话说，只要在某个时刻有公交车从当前所在的公交站出发，他就可以换乘该车，前提是该车的发车时刻或更早之前他已经到达该公交站。此外，他可以多次利用同一公交站。

在上述条件下，JOI 君希望知道，每天从家出发后，是否能在上课前抵达大学。但大学每天第一节课的开始时间各不相同。已知在接下来的 天里，每天为了赶上第一节课，他最晚必须在公交站 到达。对于每一天，JOI 君想知道，最晚何时必须从公交站 出发，才能赶上当天的课程。

题目

给定公交车运行的相关信息，以及接下来 天中每天为了赶上课程必须到达公交站 的最晚时间，对于每一天，求出 JOI 君最晚必须在何时从公交站 出发才能赶上当天的课程。

从标准输入读取以下输入数据：

• 第 行包含两个整数 和 ，以空格分隔，表示 IOI 市内共有 个公交站，有 辆公交车运行。
• 接下来的 行中，第 行（）包含四个整数 、、、（满足 ，，），以空格分隔。这表示第 辆公交车在时刻 从公交站 出发，在时刻 到达公交站 。其中，时刻是以午夜 点起经过的毫秒数表示的。
• 下一行包含一个整数 ，表示给出“必须在公交站 到达”的日期共有 天。
• 接下来的 行中，第 行（）包含一个整数 ，表示在第 天，必须在时刻 之前到达公交站 。

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

样例输入 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

-1
5
10
30

样例输入 2

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

样例输出 2

0
0
0
1
1
2

样例 1 解释

无法在时刻 前到达公交站 。

为了在时刻 前到达，只需在时刻 乘坐第 辆公交车。

为了在时刻 前到达，可以按以下方式操作：

• 在时刻 乘坐第 辆公交车。
• 在时刻 到达公交站 ，等待 毫秒后换乘第 辆公交车。
• 在时刻 到达公交站 。

为了在时刻 前到达，可以按以下方式操作：

• 在时刻 乘坐第 辆公交车。
• 在时刻 到达公交站 ，等待 毫秒后换乘第 辆公交车。
• 在时刻 到达公交站 。

数据范围

所有输入数据满足以下条件：

• 。
• 。
• （）。
• 。
• （）。

子任务

子任务 1 [20 分]

满足以下条件：

• 。
• 。
• 。

子任务 2 [15 分]

满足以下条件：

• 。
• 。

子任务 3 [15 分]

满足以下条件：

• 。

子任务 4 [50 分]

无额外限制。

翻译由 Qwen3-235B 完成