Университет студенті JOI университетке автобуспен қатынайды. JOI-дың үйі де, ол оқитын университет те IOI қаласында орналасқан. IOI қаласында 1-ден $N$-ге дейін нөмірленген $N$ автобус аялдамасы бар. JOI-дың үйіне ең жақын автобус аялдамасы — 1-аялдама, ал университетке ең жақын автобус аялдамасы — $N$-аялдама.

IOI қаласында $M$ автобус жүреді. Әр автобус күніне бір рет белгіленген автобус аялдамасынан кесте бойынша белгілі бір уақытта шығып, белгіленген автобус аялдамасына кесте бойынша белгілі бір уақытта жетеді. Тәулік ауысып жүретін автобустар жоқ. JOI белгіленген аялдамалардан басқа жерде автобусқа міне немесе одан түсе алмайды.

Күн сайын JOI бір немесе бірнеше автобусқа мініп, университетке барады. JOI-дың бір автобустан екінші автобусқа ауысып мінуіне кететін уақыт елеусіз деп есептейік. Яғни, белгілі бір аялдамадан белгілі бір уақытта шығатын автобусқа ауысып міну үшін, ол сол аялдамаға автобустың шығу уақытында немесе одан ертерек жетсе болғаны. Сондай-ақ, ол бір автобус аялдамасын бірнеше рет пайдалана алады.

Осы шарттарда JOI сабаққа уақытында жету үшін үйінен қашан шығу керектігін білгісі келеді. Алайда университеттегі күннің бірінші сабағының басталу уақыты әр күні әртүрлі болады. Берілген $Q$ күн үшін сол күні сабаққа үлгеру үшін $N$-аялдамаға қай уақытқа дейін жету керектігі белгілі. Осы күндердің әрқайсысы үшін сабаққа үлгеру үшін JOI 1-аялдамаға ең кеш дегенде қай уақытқа дейін келуі керек?

Тапсырма

Сізге автобустардың қозғалысы туралы ақпарат берілген. Сонымен қатар, $Q$ күн үшін оның $N$-аялдамаға қай уақытқа дейін жетуі керектігі берілген. Әр күн үшін JOI-дың 1-аялдамаға келуі тиіс ең кеш уақытты табыңыз.

Кіріс деректер

Стандартты кірістен келесі деректерді оқыңыз:

• Бірінші жолда бос орынмен бөлінген екі бүтін сан $N$ және $M$ берілген, бұл IOI қаласында $N$ автобус аялдамасы мен $M$ автобус бар екенін білдіреді.
• Келесі $M$ жолдың $i$-ші жолында ($1 \le i \le M$) бос орынмен бөлінген төрт бүтін сан $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$) берілген. Бұл $i$-ші автобус $A_i$ аялдамасынан $X_i$ уақытында шығып, $B_i$ аялдамасына $Y_i$ уақытында жететінін білдіреді. Уақыт түнгі 0:00 AM-ден бастап өткен миллисекундтар санымен көрсетілгенін ескеріңіз.
• Келесі жолда $N$-аялдамаға келу уақыты берілген күндер санын білдіретін бір бүтін сан $Q$ берілген.
• Келесі $Q$ жолдың $j$-ші жолында ($1 \le j \le Q$) бір бүтін сан $L_j$ берілген, ол $j$-ші күні оның $N$-аялдамаға $L_j$ уақытына дейін жетуі керектігін көрсетеді.

Шығыс деректер

Стандартты шығысқа $Q$ жол шығарыңыз. $j$-ші жолда ($1 \le j \le Q$) $j$-ші күні JOI-дың 1-аялдамаға келуі тиіс ең кеш уақытты білдіретін бүтін сан болуы керек. Егер сабаққа уақытында университетке жету мүмкін болмаса, -1 шығарыңыз.

Шектеулер

Барлық кіріс деректер келесі шарттарды қанағаттандырады:

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

Ішкі тапсырмалар

Ішкі тапсырма 1 [20 ұпай]

Келесі шарттар орындалады: $N \le 2\,000$. $M \le 2\,000$. * $Q = 1$.

Ішкі тапсырма 2 [15 ұпай]

Келесі шарттар орындалады: $N \le 2\,000$. $M \le 2\,000$.

Ішкі тапсырма 3 [15 ұпай]

• $Q = 1$ шарты орындалады.

Ішкі тапсырма 4 [50 ұпай]

Қосымша шектеулер жоқ.

Мысалдар

Кіріс 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

Шығыс 1

-1
5
10
30

Ескертпе

5-аялдамаға 10 уақытына дейін жету мүмкін емес. 30 уақытына дейін жету үшін 5 уақытында 4-ші автобусқа мінуге болады. 60 уақытына дейін жету үшін келесідей әрекет етуге болады: 10 уақытында 1-ші автобусқа міну. 25 уақытында 2-аялдамаға жетіп, 1 миллисекунд күтіп, 3-ші автобусқа міну. 50 уақытында 5-аялдамаға жету. 100 уақытына дейін жету үшін келесідей әрекет етуге болады: 30 уақытында 5-ші автобусқа міну. 40 уақытында 4-аялдамаға жетіп, 10 миллисекунд күтіп, 6-шы автобусқа міну. 70 уақытында 5-аялдамаға жету.

Кіріс 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

Шығыс 2

0
0
0
1
1
2