巴士走读

时间限制:30s      空间限制:256MB

题目描述

大学生的JOI君每天乘坐巴士走读。
JOI君的家和学校都在IOI市内。IOI市内共有N个巴士停靠点,编号为1~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<=i<=M)有四个空格分隔的整数Ai,Bi,Xi,Yi(1<=Ai<=N,1<=Bi<=N,Ai≠Bi),表示第i辆巴士在时刻Xi从停靠点Ai出发,在时刻Yi到达停靠点Bi。时刻从半夜12点开始计算,单位为毫秒。
接下来一行一个整数Q,含义如题目中所示
接下来Q行,第i行(1<=i<=Q)有一个整数Li,表示第i天最迟Li时刻到达站点N


输出格式

输出Q行,第i行(1<=i<=Q)一个整数,表示JOI君第i天最迟到达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

提示

2<=N<=100000
1<=M<=300000
0<=Xi<Yi<86400000(=24*60*60*1000)(1<=i<=M)
1<=Q<=100000
0<=Li<86400000(1<=i<=Q)


题目来源

JOI 2013~2014 春季training合宿 竞技1 By PoPoQQQ

Menuappsclose