题目描述

题目译自 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$

子任务详情：