题目描述

大学生的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。

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

5
10
30

提示

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

题目来源

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