JOI, uno studente universitario, fa il pendolare verso l'università in autobus. Sia la casa di JOI che l'università che frequenta si trovano all'interno di IOI City. Ci sono $N$ fermate dell'autobus a IOI City, numerate da 1 a $N$. La fermata più vicina alla casa di JOI è la fermata 1, e la fermata più vicina all'università è la fermata $N$.

Ci sono $M$ autobus in servizio a IOI City. Ogni autobus parte da una fermata designata a un orario prestabilito e arriva a una fermata designata a un orario prestabilito, una volta al giorno. Non ci sono autobus che operano a cavallo di giorni diversi. JOI non può salire o scendere da un autobus in nessun punto diverso dalle fermate designate.

Ogni giorno, JOI raggiunge l'università prendendo uno o più autobus. Si assuma che il tempo impiegato da JOI per cambiare autobus sia trascurabile. Cioè, per trasferirsi su un autobus che parte da una certa fermata a una certa ora, gli basta essere arrivato a quella fermata all'ora di partenza di quell'autobus o prima. Inoltre, può utilizzare la stessa fermata più volte.

In queste condizioni, JOI vuole sapere quando dovrebbe uscire di casa per arrivare all'università in tempo per le lezioni. Tuttavia, l'orario di inizio della prima lezione della giornata all'università varia di giorno in giorno. Per $Q$ giorni dati, è noto entro quale ora deve arrivare alla fermata $N$ per essere in tempo per le lezioni di quel giorno. Per ciascuno di questi giorni, entro quale ora al più tardi JOI deve arrivare alla fermata 1 per essere in tempo per le lezioni?

Compito

Vi vengono fornite le informazioni sulle corse degli autobus. Inoltre, per $Q$ giorni, vi viene fornito l'orario entro il quale egli deve arrivare alla fermata $N$. Per ogni giorno, trovate l'orario più tardo entro il quale JOI deve arrivare alla fermata 1.

Input

Leggere quanto segue dallo standard input:

• La prima riga contiene due interi $N$ e $M$, separati da uno spazio, che indicano che ci sono $N$ fermate dell'autobus e $M$ autobus a IOI City.
• La $i$-esima riga delle seguenti $M$ righe ($1 \le i \le M$) contiene quattro interi $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$), separati da spazi. Ciò significa che l'$i$-esimo autobus parte dalla fermata $A_i$ al tempo $X_i$ e arriva alla fermata $B_i$ al tempo $Y_i$. Si noti che il tempo è rappresentato come il tempo trascorso in millisecondi dalle 0:00 AM.
• La riga successiva contiene un intero $Q$, che rappresenta il numero di giorni per i quali è dato l'orario di arrivo alla fermata $N$.
• La $j$-esima riga delle seguenti $Q$ righe ($1 \le j \le Q$) contiene un intero $L_j$, che indica che nel $j$-esimo giorno egli deve arrivare alla fermata $N$ entro il tempo $L_j$.

Output

Stampare $Q$ righe sullo standard output. La $j$-esima riga ($1 \le j \le Q$) deve contenere un intero che rappresenta l'orario più tardo entro il quale JOI deve arrivare alla fermata 1 nel $j$-esimo giorno. Se è impossibile arrivare all'università in tempo per le lezioni, stampare -1.

Vincoli

Tutti i dati di input soddisfano le seguenti condizioni:

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

Subtask

Subtask 1 [20 punti]

Sono soddisfatte le seguenti condizioni: $N \le 2\,000$. $M \le 2\,000$. * $Q = 1$.

Subtask 2 [15 punti]

Sono soddisfatte le seguenti condizioni: $N \le 2\,000$. $M \le 2\,000$.

Subtask 3 [15 punti]

• È soddisfatta $Q = 1$.

Subtask 4 [50 punti]

Non ci sono vincoli aggiuntivi.

Esempi

Input 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

Output 1

-1
5
10
30

Nota

È impossibile arrivare alla fermata 5 entro il tempo 10. Per arrivare entro il tempo 30, si può prendere il 4° autobus al tempo 5. Per arrivare entro il tempo 60, si può fare quanto segue: Salire sul 1° autobus al tempo 10. Arrivare alla fermata 2 al tempo 25, aspettare 1 millisecondo e salire sul 3° autobus. Arrivare alla fermata 5 al tempo 50. Per arrivare entro il tempo 100, si può fare quanto segue: Salire sul 5° autobus al tempo 30. Arrivare alla fermata 4 al tempo 40, aspettare 10 millisecondi e salire sul 6° autobus. Arrivare alla fermata 5 al tempo 70.

Input 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

Output 2

0
0
0
1
1
2