大学生 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$) 包含 $4$ 个整数 $A_i, B_i, X_i, Y_i$ ($1 \le A_i \le N, 1 \le B_i \le N, A_i \neq 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$。
数据范围
所有输入数据满足以下条件：
- $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 2\,000$ $M \le 2\,000$ * $Q = 1$
子任务 2 [15 点]
满足以下条件： $N \le 2\,000$ $M \le 2\,000$
子任务 3 [15 点]
- $Q = 1$
子任务 4 [50 点]
没有额外限制。
样例
输入 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
说明
- 无法在时刻 $10$ 之前到达 $5$ 号车站。
- 为了在时刻 $30$ 之前到达，可以在时刻 $5$ 乘坐第 $4$ 辆公交车。
- 为了在时刻 $60$ 之前到达，可以按以下方式：
- 时刻 $10$ 乘坐第 $1$ 辆公交车。
- 时刻 $25$ 到达 $2$ 号车站，等待 $1$ 毫秒后乘坐第 $3$ 辆公交车。
- 时刻 $50$ 到达 $5$ 号车站。
- 为了在时刻 $100$ 之前到达，可以按以下方式：
- 时刻 $30$ 乘坐第 $5$ 辆公交车。
- 时刻 $40$ 到达 $4$ 号车站，等待 $10$ 毫秒后乘坐第 $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
输出 2
0 0 0 1 1 2