Student JOI dojeżdża na uczelnię autobusem. Zarówno jego dom, jak i uczelnia znajdują się w mieście IOI. W mieście jest $N$ przystanków autobusowych, ponumerowanych od $1$ do $N$. Najbliżej domu JOI znajduje się przystanek $1$, a najbliżej uczelni — przystanek $N$.

W mieście IOI kursuje $M$ autobusów. Każdy z nich raz dziennie odjeżdża z ustalonego przystanku o ustalonej godzinie i przyjeżdża na ustalony przystanek o ustalonej godzinie. Żaden kurs nie przechodzi na następny dzień. JOI nie może wsiadać ani wysiadać po drodze.

JOI codziennie dociera na uczelnię, korzystając z jednego lub większej liczby autobusów. Można pominąć czas potrzebny na przesiadkę. Innymi słowy, aby przesiąść się do autobusu odjeżdżającego z danego przystanku o danej godzinie, wystarczy przybyć na ten przystanek nie później niż w chwili jego odjazdu. Można też wielokrotnie korzystać z tego samego przystanku.

W tych warunkach JOI chce wiedzieć, kiedy powinien wyjść z domu, aby zdążyć na zajęcia. Godzina rozpoczęcia pierwszych zajęć na uczelni zależy jednak od dnia. Dla pewnych $Q$ dni wiadomo, do której godziny należy przybyć na przystanek $N$, aby zdążyć na zajęcia. Jaka jest dla każdego dnia najpóźniejsza chwila, w której JOI powinien przybyć na przystanek $1$, aby zdążyć?

Zadanie

Dane są informacje o kursach autobusów. Ponadto dla pewnych $Q$ dni podana jest najpóźniejsza dozwolona chwila przybycia na przystanek $N$. Dla każdego z nich wyznacz najpóźniejszą chwilę, w której JOI powinien przybyć na przystanek $1$.

Wejście

Wczytaj następujące dane ze standardowego wejścia.

• Pierwszy wiersz zawiera dwie liczby całkowite $N,M$, oddzielone spacją, oznaczające, że w mieście IOI jest $N$ przystanków i kursuje $M$ autobusów.
• $i$-ty wiersz ($1 \le i \le M$) spośród następnych $M$ wierszy zawiera cztery liczby całkowite $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$), oddzielone spacjami. Oznacza to, że $i$-ty autobus odjeżdża z przystanku $A_i$ w chwili $X_i$ i przyjeżdża na przystanek $B_i$ w chwili $Y_i$. Czas podawany jest w milisekundach, które upłynęły od dokładnej północy.
• Następny wiersz zawiera liczbę całkowitą $Q$. Oznacza to, że podane będą terminy przybycia na przystanek $N$ dla $Q$ dni.
• $j$-ty wiersz ($1 \le j \le Q$) spośród następnych $Q$ wierszy zawiera liczbę całkowitą $L_j$. Oznacza to, że $j$-tego dnia należy przybyć na przystanek $N$ nie później niż w chwili $L_j$.

Wyjście

Wypisz $Q$ wierszy na standardowe wyjście. W $j$-tym wierszu ($1 \le j \le Q$) wypisz liczbę całkowitą oznaczającą najpóźniejszą chwilę, w której JOI powinien przybyć na przystanek $1$ w $j$-tym dniu. Jeśli nie da się dotrzeć na uczelnię na czas, wypisz $-1$.

Ograniczenia

Wszystkie dane wejściowe spełniają następujące warunki.

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

Podzadania

Podzadanie 1 [20 punktów]

Spełnione są następujące warunki.

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

Podzadanie 2 [15 punktów]

Spełnione są następujące warunki.

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

Podzadanie 3 [15 punktów]

• Spełnione jest $Q=1$.

Podzadanie 4 [50 punktów]

Brak dodatkowych ograniczeń.

Przykład

Wejście 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

Wyjście 1

-1
5
10
30

Uwagi

Nie da się przybyć na przystanek $5$ do chwili $10$.

Aby przybyć do chwili $30$, można wsiąść do czwartego autobusu w chwili $5$.

Aby przybyć do chwili $60$, można postąpić następująco.

• W chwili $10$ wsiąść do pierwszego autobusu.
• W chwili $25$ przybyć na przystanek $2$, odczekać 1 milisekundę i wsiąść do trzeciego autobusu.
• W chwili $50$ przybyć na przystanek $5$.

Aby przybyć do chwili $100$, można postąpić następująco.

• W chwili $30$ wsiąść do piątego autobusu.
• W chwili $40$ przybyć na przystanek $4$, odczekać 10 milisekund i wsiąść do szóstego autobusu.
• W chwili $70$ przybyć na przystanek $5$.

Wejście 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

Wyjście 2

0
0
0
1
1
2