Der Student JOI-kun fährt mit dem Bus zur Universität. Sowohl sein Zuhause als auch seine Universität liegen in der Stadt IOI. In der Stadt IOI gibt es $N$ Bushaltestellen, die von $1$ bis $N$ nummeriert sind. Die nächstgelegene Haltestelle zu seinem Zuhause ist Haltestelle $1$, die nächstgelegene zur Universität ist Haltestelle $N$.

In der Stadt IOI verkehren $M$ Busse. Jeder Bus fährt einmal am Tag zu einer festgelegten Zeit von einer festgelegten Haltestelle ab und kommt zu einer festgelegten Zeit an einer festgelegten Haltestelle an. Kein Bus fährt über Mitternacht hinaus. JOI-kun kann unterwegs weder in einen Bus einsteigen noch aus ihm aussteigen.

JOI-kun fährt jeden Tag mit einem oder mehreren Bussen zur Universität. Die zum Umsteigen benötigte Zeit kann vernachlässigt werden. Das heißt, um in einen Bus umzusteigen, der zu einer bestimmten Zeit von einer Haltestelle abfährt, genügt es, spätestens zu dessen Abfahrtszeit an dieser Haltestelle anzukommen. Dieselbe Haltestelle darf auch mehrmals benutzt werden.

Unter diesen Bedingungen möchte JOI-kun wissen, wann er das Haus verlassen muss, um rechtzeitig zum Unterricht an der Universität anzukommen. Allerdings beginnt die erste Lehrveranstaltung je nach Tag zu einer anderen Zeit. Für $Q$ Tage ist bekannt, bis wann er an Haltestelle $N$ ankommen muss, um rechtzeitig zum Unterricht zu kommen. Wann muss JOI-kun an jedem dieser Tage spätestens an Haltestelle $1$ ankommen, um den Unterricht rechtzeitig zu erreichen?

Aufgabe

Gegeben sind Informationen über die Busfahrten. Außerdem ist für $Q$ Tage jeweils gegeben, bis wann Haltestelle $N$ erreicht werden muss. Bestimme für jeden dieser Tage, wann JOI-kun spätestens an Haltestelle $1$ ankommen muss.

Eingabe

Lies die folgenden Daten von der Standardeingabe ein.

• Die erste Zeile enthält zwei durch ein Leerzeichen getrennte ganze Zahlen $N,M$. Sie bedeuten, dass es in der Stadt IOI $N$ Haltestellen gibt und $M$ Busse verkehren.
• Die $i$-te Zeile ($1 \le i \le M$) der folgenden $M$ Zeilen enthält vier durch Leerzeichen getrennte ganze Zahlen $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$). Sie bedeuten, dass der $i$-te Bus zur Zeit $X_i$ von Haltestelle $A_i$ abfährt und zur Zeit $Y_i$ an Haltestelle $B_i$ ankommt. Zeiten werden als seit genau Mitternacht verstrichene Zeit in Millisekunden angegeben.
• Die nächste Zeile enthält eine ganze Zahl $Q$. Sie bedeutet, dass für $Q$ Tage vorgegeben wird, bis wann Haltestelle $N$ erreicht werden muss.
• Die $j$-te Zeile ($1 \le j \le Q$) der folgenden $Q$ Zeilen enthält eine ganze Zahl $L_j$. Sie bedeutet, dass am $j$-ten Tag Haltestelle $N$ spätestens zur Zeit $L_j$ erreicht werden muss.

Ausgabe

Gib $Q$ Zeilen auf der Standardausgabe aus. Gib in der $j$-ten Zeile ($1 \le j \le Q$) eine ganze Zahl aus, die angibt, wann JOI-kun am $j$-ten Tag spätestens an Haltestelle $1$ ankommen muss. Falls es unmöglich ist, die Universität rechtzeitig zum Unterricht zu erreichen, gib stattdessen $-1$ aus.

Beschränkungen

Alle Eingabedaten erfüllen die folgenden Bedingungen.

• $2 \le N \le 100\,000$.
• $1 \le M \le 300\,000$.
• $0 \le X_i < Y_i < 86\,400\,000$ ($=24\times60\times60\times1000$) ($1 \le i \le M$).
• $1 \le Q \le 100\,000$.
• $0 \le L_j < 86\,400\,000$ ($=24\times60\times60\times1000$) ($1 \le j \le Q$).

Teilaufgaben

Teilaufgabe 1 [20 Punkte]

Die folgenden Bedingungen sind erfüllt.

• $N \le 2\,000$.
• $M \le 2\,000$.
• $Q=1$.

Teilaufgabe 2 [15 Punkte]

Die folgenden Bedingungen sind erfüllt.

• $N \le 2\,000$.
• $M \le 2\,000$.

Teilaufgabe 3 [15 Punkte]

• Es gilt $Q=1$.

Teilaufgabe 4 [50 Punkte]

Es gibt keine zusätzlichen Beschränkungen.

Beispiele

Eingabe 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

Ausgabe 1

-1
5
10
30

Hinweis

Haltestelle $5$ kann nicht bis zur Zeit $10$ erreicht werden.

Um bis zur Zeit $30$ anzukommen, genügt es, zur Zeit $5$ in den vierten Bus einzusteigen.

Um bis zur Zeit $60$ anzukommen, kann man wie folgt vorgehen.

• Zur Zeit $10$ in den ersten Bus einsteigen.
• Zur Zeit $25$ an Haltestelle $2$ ankommen, 1 Millisekunde warten und in den dritten Bus einsteigen.
• Zur Zeit $50$ an Haltestelle $5$ ankommen.

Um bis zur Zeit $100$ anzukommen, kann man wie folgt vorgehen.

• Zur Zeit $30$ in den fünften Bus einsteigen.
• Zur Zeit $40$ an Haltestelle $4$ ankommen, 10 Millisekunden warten und in den sechsten Bus einsteigen.
• Zur Zeit $70$ an Haltestelle $5$ ankommen.

Eingabe 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

Ausgabe 2

0
0
0
1
1
2