JOI, en universitetsstudent, pendler til universitetet med buss. Både hjemmet til JOI og universitetet han går på ligger i IOI City. Det er $N$ bussholdeplasser i IOI City, nummerert fra 1 til $N$. Bussholdeplassen nærmest hjemmet til JOI er bussholdeplass 1, og bussholdeplassen nærmest universitetet er bussholdeplass $N$.

Det kjører $M$ busser i IOI City. Hver buss kjører fra en bestemt bussholdeplass til et fastsatt tidspunkt og ankommer en bestemt bussholdeplass til et fastsatt tidspunkt, én gang om dagen. Det er ingen busser som kjører over flere dager. JOI kan ikke gå på eller av en buss noe annet sted enn på de bestemte holdeplassene.

Hver dag pendler JOI til universitetet ved å ta én eller flere busser. Anta at tiden det tar for JOI å bytte mellom busser er neglisjerbar. Det vil si at for å bytte til en buss som går fra en bestemt bussholdeplass på et bestemt tidspunkt, trenger han bare å ha ankommet den bussholdeplassen senest ved bussens avgangstid. Han kan også bruke samme bussholdeplass flere ganger.

Under disse forholdene ønsker JOI å vite når han bør dra hjemmefra for å rekke frem til universitetet i tide til forelesningene. Tidspunktet når dagens første forelesning starter på universitetet varierer imidlertid fra dag til dag. For $Q$ gitte dager er det kjent innen hvilket tidspunkt han må ankomme bussholdeplass $N$ for å rekke forelesningen den dagen. For hver av disse dagene, senest ved hvilket tidspunkt må JOI ankomme bussholdeplass 1 for å rekke forelesningen?

Oppgave

Du får informasjon om bussrutene. Videre får du for $Q$ dager tidspunktet han må ankomme bussholdeplass $N$ innen. For hver dag, finn det seneste tidspunktet JOI må ankomme bussholdeplass 1.

Inndata

Les følgende fra standard inndata:

• Den første linjen inneholder to heltall $N$ og $M$, adskilt med et mellomrom, som betyr at det er $N$ bussholdeplasser og $M$ busser i IOI City.
• Den $i$-te linjen av de følgende $M$ linjene ($1 \le i \le M$) inneholder fire heltall $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$), adskilt med mellomrom. Dette betyr at den $i$-te bussen går fra bussholdeplass $A_i$ ved tidspunkt $X_i$ og ankommer bussholdeplass $B_i$ ved tidspunkt $Y_i$. Merk at tiden er representert som antall millisekunder som har gått siden kl. 0:00 AM.
• Neste linje inneholder et heltall $Q$, som representerer antall dager der ankomsttiden ved bussholdeplass $N$ er gitt.
• Den $j$-te linjen av de følgende $Q$ linjene ($1 \le j \le Q$) inneholder et heltall $L_j$, som indikerer at på den $j$-te dagen må han ankomme bussholdeplass $N$ innen tidspunkt $L_j$.

Utdata

Skriv ut $Q$ linjer til standard utdata. Den $j$-te linjen ($1 \le j \le Q$) skal inneholde et heltall som representerer det seneste tidspunktet JOI må ankomme bussholdeplass 1 på den $j$-te dagen. Hvis det er umulig å komme frem til universitetet i tide til forelesningen, skriv ut -1.

Begrensninger

Alle inndata tilfredsstiller følgende betingelser:

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

Deloppgaver

Deloppgave 1 [20 poeng]

Følgende betingelser er oppfylt: $N \le 2\,000$. $M \le 2\,000$. * $Q = 1$.

Deloppgave 2 [15 poeng]

Følgende betingelser er oppfylt: $N \le 2\,000$. $M \le 2\,000$.

Deloppgave 3 [15 poeng]

• $Q = 1$ er oppfylt.

Deloppgave 4 [50 poeng]

Det er ingen ytterligere begrensninger.

Eksempler

Inndata 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

Merk

Det er umulig å ankomme bussholdeplass 5 innen tidspunkt 10. For å ankomme innen tidspunkt 30 kan man ta den 4. bussen ved tidspunkt 5. For å ankomme innen tidspunkt 60 kan man gjøre følgende: Gå på den 1. bussen ved tidspunkt 10. Ankomme bussholdeplass 2 ved tidspunkt 25, vente 1 millisekund og gå på den 3. bussen. Ankomme bussholdeplass 5 ved tidspunkt 50. For å ankomme innen tidspunkt 100 kan man gjøre følgende: Gå på den 5. bussen ved tidspunkt 30. Ankomme bussholdeplass 4 ved tidspunkt 40, vente 10 millisekunder og gå på den 6. bussen. Ankomme bussholdeplass 5 ved tidspunkt 70.

Inndata 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