JOI, en universitetsstudent, pendlar till universitetet med buss. Både JOI:s hem och universitetet han går på ligger i IOI City. Det finns $N$ busshållplatser i IOI City, numrerade från 1 till $N$. Busshållplatsen närmast JOI:s hem är busshållplats 1, och busshållplatsen närmast universitetet är busshållplats $N$.

Det finns $M$ bussar som kör i IOI City. Varje buss avgår från en bestämd busshållplats vid en schemalagd tidpunkt och anländer till en bestämd busshållplats vid en schemalagd tidpunkt, en gång om dagen. Det finns inga bussar som kör över dygnsgränsen. JOI kan inte kliva på eller av en buss på någon annan plats än de bestämda hållplatserna.

Varje dag pendlar JOI till universitetet genom att ta en eller flera bussar. Antag att tiden det tar för JOI att byta mellan bussar är försumbar. Det vill säga, för att byta till en buss som avgår från en viss busshållplats vid en viss tidpunkt behöver han bara ha anlänt till den busshållplatsen senast vid den bussens avgångstid. Han får också använda samma busshållplats flera gånger.

Under dessa förutsättningar vill JOI veta när han bör lämna sitt hem för att komma fram till universitetet i tid till sina lektioner. Tiden då dagens första lektion börjar på universitetet varierar dock från dag till dag. För $Q$ givna dagar är det känt senast vid vilken tidpunkt han måste anlända till busshållplats $N$ för att hinna i tid till lektionen den dagen. För var och en av dessa dagar, senast vid vilken tidpunkt måste JOI anlända till busshållplats 1 för att hinna i tid till lektionen?

Uppgift

Du får information om busstrafiken. Dessutom får du för $Q$ dagar tidpunkten då han senast måste anlända till busshållplats $N$. För varje dag, bestäm den senaste tidpunkten då JOI måste anlända till busshållplats 1.

Indata

Läs följande från standard inmatning:

• Den första raden innehåller två heltal $N$ och $M$, separerade med ett mellanslag, vilket anger att det finns $N$ busshållplatser och $M$ bussar i IOI City.
• Den $i$-te raden av de följande $M$ raderna ($1 \le i \le M$) innehåller fyra heltal $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$), separerade med mellanslag. Detta betyder att den $i$-te bussen avgår från busshållplats $A_i$ vid tidpunkt $X_i$ och anländer till busshållplats $B_i$ vid tidpunkt $Y_i$. Observera att tiden anges som förfluten tid i millisekunder från kl. 0:00 AM.
• Nästa rad innehåller ett heltal $Q$, som anger antalet dagar för vilka ankomsttiden till busshållplats $N$ ges.
• Den $j$-te raden av de följande $Q$ raderna ($1 \le j \le Q$) innehåller ett heltal $L_j$, som anger att han den $j$-te dagen måste anlända till busshållplats $N$ senast vid tidpunkt $L_j$.

Utdata

Skriv ut $Q$ rader till standard utmatning. Den $j$-te raden ($1 \le j \le Q$) ska innehålla ett heltal som anger den senaste tidpunkten då JOI måste anlända till busshållplats 1 den $j$-te dagen. Om det är omöjligt att komma fram till universitetet i tid till lektionen, skriv ut -1.

Begränsningar

All indata uppfyller följande villkor:

• $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$).

Deluppgifter

Deluppgift 1 [20 poäng]

Följande villkor är uppfyllda: $N \le 2\,000$. $M \le 2\,000$. * $Q = 1$.

Deluppgift 2 [15 poäng]

Följande villkor är uppfyllda: $N \le 2\,000$. $M \le 2\,000$.

Deluppgift 3 [15 poäng]

• $Q = 1$ är uppfyllt.

Deluppgift 4 [50 poäng]

Det finns inga ytterligare begränsningar.

Exempel

Indata 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

Utdata 1

-1
5
10
30

Förklaring

Det är omöjligt att anlända till busshållplats 5 senast vid tidpunkt 10. För att anlända senast vid tidpunkt 30 kan man ta den 4:e bussen vid tidpunkt 5. För att anlända senast vid tidpunkt 60 kan man göra följande: Kliv på den 1:a bussen vid tidpunkt 10. Anländ till busshållplats 2 vid tidpunkt 25, vänta 1 millisekund och kliv på den 3:e bussen. Anländ till busshållplats 5 vid tidpunkt 50. För att anlända senast vid tidpunkt 100 kan man göra följande: Kliv på den 5:e bussen vid tidpunkt 30. Anländ till busshållplats 4 vid tidpunkt 40, vänta 10 millisekunder och kliv på den 6:e bussen. Anländ till busshållplats 5 vid tidpunkt 70.

Indata 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

Utdata 2

0
0
0
1
1
2