Yliopisto-opiskelija JOI kulkee yliopistolle bussilla. Sekä JOIn koti että yliopisto, jota hän käy, sijaitsevat IOI-kaupungissa. IOI-kaupungissa on $N$ bussipysäkkiä, jotka on numeroitu 1:stä $N$:ään. JOIn kotia lähinnä oleva bussipysäkki on bussipysäkki 1, ja yliopistoa lähinnä oleva bussipysäkki on bussipysäkki $N$.

IOI-kaupungissa liikennöi $M$ bussia. Jokainen bussi lähtee määrätystä bussipysäkistä aikataulun mukaisena aikana ja saapuu määrättyyn bussipysäkkiin aikataulun mukaisena aikana kerran päivässä. Yhtään vuorokauden rajan yli kulkevaa bussia ei ole. JOI ei voi nousta bussiin tai poistua siitä missään muualla kuin määrätyillä pysäkeillä.

Joka päivä JOI matkustaa yliopistolle yhdellä tai useammalla bussilla. Oletetaan, että JOIlta bussien vaihtamiseen kuluva aika on mitätön. Toisin sanoen vaihtaakseen bussiin, joka lähtee tietyltä bussipysäkiltä tiettyyn aikaan, hänen täytyy vain olla saapunut kyseiselle bussipysäkille viimeistään kyseisen bussin lähtöaikana. Lisäksi hän voi käyttää samaa bussipysäkkiä useita kertoja.

Näillä ehdoilla JOI haluaa tietää, milloin hänen pitäisi lähteä kotoa ehtiäkseen yliopistolle ajoissa luennoilleen. Päivän ensimmäisen luennon alkamisaika yliopistolla kuitenkin vaihtelee päivittäin. Annetulle $Q$ päivälle tiedetään, mihin aikaan mennessä hänen on saavuttava bussipysäkille $N$ ehtiäkseen sinä päivänä luennolle. Mihin aikaan viimeistään JOIn on saavuttava bussipysäkille 1 kukin näistä päivistä ehtiäkseen luennolle?

Tehtävä

Sinulle annetaan tiedot bussiliikenteestä. Lisäksi $Q$ päivälle annetaan aika, johon mennessä hänen on saavuttava bussipysäkille $N$. Etsi jokaiselle päivälle myöhäisin aika, johon mennessä JOIn on saavuttava bussipysäkille 1.

Syöte

Lue seuraavat tiedot vakiosyötteestä:

• Ensimmäinen rivi sisältää kaksi välilyönnillä erotettua kokonaislukua $N$ ja $M$, jotka ilmaisevat, että IOI-kaupungissa on $N$ bussipysäkkiä ja $M$ bussia.
• Seuraavien $M$ rivin $i$-s rivi ($1 \le i \le M$) sisältää neljä välilyönnein erotettua kokonaislukua $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$). Tämä tarkoittaa, että $i$-s bussi lähtee bussipysäkiltä $A_i$ ajanhetkellä $X_i$ ja saapuu bussipysäkille $B_i$ ajanhetkellä $Y_i$. Huomaa, että aika esitetään kuluneena aikana millisekunteina kello 0:00 AM alkaen.
• Seuraava rivi sisältää kokonaisluvun $Q$, joka ilmaisee niiden päivien lukumäärän, joille saapumisaika bussipysäkille $N$ annetaan.
• Seuraavien $Q$ rivin $j$-s rivi ($1 \le j \le Q$) sisältää kokonaisluvun $L_j$, joka osoittaa, että $j$-ntenä päivänä hänen on saavuttava bussipysäkille $N$ viimeistään ajanhetkellä $L_j$.

Tuloste

Tulosta $Q$ riviä vakiotulosteeseen. $j$-nnen rivin ($1 \le j \le Q$) tulee sisältää kokonaisluku, joka ilmaisee myöhäisimmän ajan, johon mennessä JOIn on saavuttava bussipysäkille 1 $j$-ntenä päivänä. Jos yliopistolle on mahdotonta ehtiä ajoissa luennolle, tulosta -1.

Rajoitukset

Kaikki syötetiedot täyttävät seuraavat ehdot:

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

Osatehtävät

Osatehtävä 1 [20 pistettä]

Seuraavat ehdot täyttyvät: $N \le 2\,000$. $M \le 2\,000$. * $Q = 1$.

Osatehtävä 2 [15 pistettä]

Seuraavat ehdot täyttyvät: $N \le 2\,000$. $M \le 2\,000$.

Osatehtävä 3 [15 pistettä]

• $Q = 1$ täyttyy.

Osatehtävä 4 [50 pistettä]

Ei ole lisärajoituksia.

Esimerkit

Syöte 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

Tuloste 1

-1
5
10
30

Huomautus

On mahdotonta saapua bussipysäkille 5 ajanhetkeen 10 mennessä. Saapuakseen ajanhetkeen 30 mennessä voi ottaa 4. bussin ajanhetkellä 5. Saapuakseen ajanhetkeen 60 mennessä voi toimia seuraavasti: Nouse 1. bussiin ajanhetkellä 10. Saavu bussipysäkille 2 ajanhetkellä 25, odota 1 millisekunti ja nouse 3. bussiin. Saavu bussipysäkille 5 ajanhetkellä 50. Saapuakseen ajanhetkeen 100 mennessä voi toimia seuraavasti: Nouse 5. bussiin ajanhetkellä 30. Saavu bussipysäkille 4 ajanhetkellä 40, odota 10 millisekuntia ja nouse 6. bussiin. Saavu bussipysäkille 5 ajanhetkellä 70.

Syöte 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

Tuloste 2

0
0
0
1
1
2