该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

[AdditionalFile2872.zip](file://AdditionalFile2872.zip?type=additional_file)

#2872. 「JOISC 2014 Day1」巴士走读

标签: 传统 | 时间限制: 1000 ms | 内存限制: 256 MiB |

题目描述

感谢 PoPoQQQ 提供的翻译，已获原译者授权搬运。

题目译自 JOISC 2014 Day1 T1「バス通学」

大学生 JOI 君每天乘坐巴士走读。
JOI 君的家和学校都在 IOI 市内。IOI 市内共有 $N$ 个巴士站点，编号为 $1\sim N$，离 JOI 家最近的站点为 $1$ 号站点，离大学最近的站点为 $N$ 号站点。
IOI 市内共有 $M$ 辆巴士，每辆巴士一天只跑一次，从某一时刻某一停靠点出发，在某一时刻到达另一个站点。运行途中不可以下车。
JOI 君每天要乘坐一次以上的巴士到达学校。我们可以无视 JOI 君换车的时间，换言之，为了换乘某个时刻从某个停靠点出发的巴士，只需要在该巴士的出发时间或之前到达站点就可以了。此外，多次在某个站点换乘也是可以的。
在这样的条件下，JOI 君想知道自己应该何时从家中出发才能按时赶到学校。然而，学校每天开始上课的时间都不同。在某 $Q$ 天里，每天到达 $N$ 号站点的最晚时间都是已知的，JOI 君想知道，他最晚何时到达 $1$ 号站点才能及时到校。
现在给你巴士的运营信息，以及这 $Q$ 天里每天到达 $N$ 号站点的最晚时间，请你求出每天 JOI 君最晚何时到达 $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≠B_i)$，表示第 $i$ 辆巴士在时刻 $X_i$ 从停靠点 $A_i$ 出发，在时刻 $Y_i$ 到达停靠点 $B_i$。时刻从半夜 12 点开始计算，单位为毫秒。
接下来一行一个整数 $Q$，含义如题目中所示。
接下来 $Q$ 行，第 $i$ 行 $(1\le i\le Q)$ 有一个整数 $L_i$，表示第 $i$ 天最迟 $L_i$ 时刻到达 $N$ 号站点。

输出格式

输出 $Q$ 行，第 $i$ 行 $(1\le i\le Q)$ 一个整数，表示 JOI 君第 $i$ 天最迟到达 $1$ 号站点的时刻。 如果无法在时限内到达，输出 $\texttt{-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

无法在时刻 10 之前到达 5 号车站。 为了在时刻 30 到达，您可以在时刻 5 乘坐 4 号车。 为了在时刻 60 到达，您可以执行以下操作。

• 在时刻 10 乘坐 1 号车。
• 在时刻 25 到达 2 号车站，等待 1 ms，转 3 号车。
• 在时刻 50 抵达 5 号车站。

为了在时间 100 到达，您可以执行以下操作。

• 在时刻 30 乘坐 5 号车。
• 在时刻 40 到达 4 号车，等待 10 ms，转 6 号车。
• 在时刻 70 抵达 5 号车站。

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

输出

0
0
0
1
1
2

数据范围与提示

对于所有数据，$2\le N\le 10^5,$ $1\le M\le 3\times 10^5,$ $0\le X_i<Y_i<86400000$ $(=24\times 60\times 60\times 1000),$ $1\le Q\le 10^5,$ $0\le L_i<86400000$。