NC53253. 巴士走读
描述
感谢 PoPoQQQ 提供的翻译，已获原译者授权搬运。
题目译自 JOISC 2014 Day1 T1「バス通学」
大学生JOI君每天乘坐巴士走读。
JOI君的家和学校都在IOI市内。IOI市内共有N个巴士站点，编号为
，离JOI家最近的站点为1号站点，离大学最近的站点为N号站点。
IOI市内共有M辆巴士，每辆巴士一天只跑一次，从某一时刻某一停靠点出发，在某一时刻到达另一个站点。运行途中不可以下车。
JOI君每天要乘坐一次以上的巴士到达学校。我们可以无视JOI君换车的时间，换言之，为了换乘某个时刻从某个停靠点出发的巴士，只需要在该巴士的出发时间或之前到达站点就可以了。此外，多次在某个站点换乘也是可以的。
在这样的条件下，JOI君想知道自己应该何时从家中出发才能按时赶到学校。然而，学校每天开始上课的时间都不同。在某Q天里，每天到达N号站点的最晚时间都是已知的，JOI君想知道，他最晚何时到达1号站点才能及时到校。
现在给你巴士的运营信息，以及这Q天里每天到达N号站点的最晚时间，请你求出每天JOI君最晚何时到达1号站点。
JOI君的家和学校都在IOI市内。IOI市内共有N个巴士站点，编号为
IOI市内共有M辆巴士，每辆巴士一天只跑一次，从某一时刻某一停靠点出发，在某一时刻到达另一个站点。运行途中不可以下车。
JOI君每天要乘坐一次以上的巴士到达学校。我们可以无视JOI君换车的时间，换言之，为了换乘某个时刻从某个停靠点出发的巴士，只需要在该巴士的出发时间或之前到达站点就可以了。此外，多次在某个站点换乘也是可以的。
在这样的条件下，JOI君想知道自己应该何时从家中出发才能按时赶到学校。然而，学校每天开始上课的时间都不同。在某Q天里，每天到达N号站点的最晚时间都是已知的，JOI君想知道，他最晚何时到达1号站点才能及时到校。
现在给你巴士的运营信息，以及这Q天里每天到达N号站点的最晚时间，请你求出每天JOI君最晚何时到达1号站点。
输入描述
第一行两个空格分隔的正整数N和M，表示IOI市内有N个巴士站点和M辆巴士。
接下来M行，第i行有四个空格分隔的整数
，表示第i辆巴士在时刻
从停靠点
出发，在时刻
到达停靠点
。时刻从半夜12点开始计算，单位为毫秒。
接下来一行一个整数Q，含义如题目中所示。
接下来Q行，第i行有一个整数
，表示第i天最迟
输出描述
输出Q行，第i行。
示例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号车站，等待1ms，转3号车。
在时刻50抵达5号车站。
为了在时间100到达，您可以执行以下操作。
在时刻30乘坐5号车。
在时刻40到达4号车，等待10ms，转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