JOI, sem er háskólanemi, ferðast í háskólann með strætó. Bæði heimili JOI og háskólinn sem hann sækist eru í IOI-borg. Það eru $N$ strætóstoppistöðvar í IOI-borg, númeraðar frá 1 til $N$. Strætóstoppistöðin sem er næst heimili JOI er stoppistöð 1, og strætóstoppistöðin sem er næst háskólanum er stoppistöð $N$.

Það ganga $M$ strætisvagnar í IOI-borg. Hver strætisvagn leggur af stað frá ákveðinni stoppistöð á ákveðnum tíma og kemur á ákveðna stoppistöð á ákveðnum tíma, einu sinni á dag. Engir strætisvagnar ganga yfir miðnætti milli daga. JOI getur hvorki farið í né úr strætisvagni á neinum öðrum stað en tilgreindum stoppistöðvum.

Á hverjum degi ferðast JOI í háskólann með því að taka einn eða fleiri strætisvagna. Gerið ráð fyrir að tíminn sem það tekur JOI að skipta á milli strætisvagna sé hverfandi. Það er að segja, til að skipta yfir í strætisvagn sem leggur af stað frá ákveðinni stoppistöð á ákveðnum tíma þarf hann aðeins að vera kominn á þá stoppistöð á brottfarartíma vagnsins eða fyrr. Hann má einnig nota sömu stoppistöðina oft.

Við þessar aðstæður vill JOI vita hvenær hann ætti að leggja af stað að heiman til að vera kominn í háskólann í tæka tíð fyrir kennslustundirnar sínar. Hins vegar er misjafnt milli daga hvenær fyrsta kennslustund dagsins hefst í háskólanum. Fyrir $Q$ gefna daga er vitað fyrir hvaða tíma hann verður að vera kominn á stoppistöð $N$ til að ná í tíma þann daginn. Fyrir hvern þessara daga, fyrir hvaða tíma í síðasta lagi verður JOI að vera kominn á stoppistöð 1 til að ná í tíma?

Verkefni

Þér eru gefnar upplýsingar um strætóferðirnar. Ennfremur er þér gefinn tíminn sem hann verður að vera kominn á stoppistöð $N$ fyrir $Q$ daga. Fyrir hvern dag skaltu finna síðasta mögulega tímann sem JOI verður að vera kominn á stoppistöð 1.

Inntak

Lesið eftirfarandi úr staðalinntaki:

• Fyrsta línan inniheldur tvær heiltölur $N$ og $M$, aðskildar með bili, sem tákna að það séu $N$ strætóstoppistöðvar og $M$ strætisvagnar í IOI-borg.
• $i$-ta línan af næstu $M$ línum ($1 \le i \le M$) inniheldur fjórar heiltölur $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$), aðskildar með bilum. Þetta þýðir að $i$-ti strætisvagninn leggur af stað frá stoppistöð $A_i$ á tíma $X_i$ og kemur á stoppistöð $B_i$ á tíma $Y_i$. Athugið að tíminn er gefinn sem liðinn tími í millisekúndum frá kl. 0:00 AM.
• Næsta lína inniheldur heiltölu $Q$, sem táknar fjölda daga sem komutími á stoppistöð $N$ er gefinn fyrir.
• $j$-ta línan af næstu $Q$ línum ($1 \le j \le Q$) inniheldur heiltölu $L_j$, sem gefur til kynna að á $j$-ta degi verði hann að vera kominn á stoppistöð $N$ fyrir tíma $L_j$.

Úttak

Skrifið út $Q$ línur í staðalúttak. $j$-ta línan ($1 \le j \le Q$) á að innihalda heiltölu sem táknar síðasta mögulega tímann sem JOI verður að vera kominn á stoppistöð 1 á $j$-ta degi. Ef ómögulegt er að komast í háskólann í tæka tíð fyrir kennslustund skal skrifa út -1.

Takmarkanir

Öll inntaksgögn uppfylla eftirfarandi skilyrði:

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

Undirverkefni

Undirverkefni 1 [20 stig]

Eftirfarandi skilyrði eru uppfyllt: $N \le 2\,000$. $M \le 2\,000$. * $Q = 1$.

Undirverkefni 2 [15 stig]

Eftirfarandi skilyrði eru uppfyllt: $N \le 2\,000$. $M \le 2\,000$.

Undirverkefni 3 [15 stig]

• $Q = 1$ er uppfyllt.

Undirverkefni 4 [50 stig]

Engar frekari takmarkanir.

Dæmi

Inntak 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

Úttak 1

-1
5
10
30

Athugasemd

Það er ómögulegt að komast á stoppistöð 5 fyrir tíma 10. Til að komast fyrir tíma 30 er hægt að taka 4. strætisvagninn á tíma 5. Til að komast fyrir tíma 60 er hægt að gera eftirfarandi: Fara í 1. strætisvagninn á tíma 10. Koma á stoppistöð 2 á tíma 25, bíða í 1 millisekúndu og fara í 3. strætisvagninn. Koma á stoppistöð 5 á tíma 50. Til að komast fyrir tíma 100 er hægt að gera eftirfarandi: Fara í 5. strætisvagninn á tíma 30. Koma á stoppistöð 4 á tíma 40, bíða í 10 millisekúndur og fara í 6. strætisvagninn. Koma á stoppistöð 5 á tíma 70.

Inntak 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

Úttak 2

0
0
0
1
1
2