大學生 JOI 君搭公車上學。JOI 君的家和他就讀的大學都位於 IOI 市內。IOI 市有 $N$ 個公車站，編號為 $1$ 至 $N$。離 JOI 君家最近的是公車站 $1$，離大學最近的是公車站 $N$。

IOI 市內有 $M$ 班公車。每班公車每天行駛一次，在指定時刻從指定公車站出發，並在指定時刻抵達指定公車站。沒有跨日行駛的公車。JOI 君不能中途上車或下車。

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 \ne 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