JOI-kun adalah mahasiswa yang pergi ke kampus dengan bus. Rumah JOI-kun dan kampusnya sama-sama berada di Kota IOI. Kota IOI memiliki $N$ halte bus, diberi nomor dari $1$ hingga $N$. Halte terdekat dari rumah JOI-kun adalah halte $1$, sedangkan halte terdekat dari kampusnya adalah halte $N$.

Ada $M$ perjalanan bus di Kota IOI. Setiap bus berangkat sekali sehari dari halte yang telah ditentukan pada waktu yang telah ditentukan, dan tiba di halte yang telah ditentukan pada waktu yang telah ditentukan. Tidak ada perjalanan bus yang melewati pergantian hari. JOI-kun tidak dapat naik atau turun di tengah perjalanan bus.

Setiap hari, JOI-kun pergi ke kampus dengan menaiki satu atau lebih bus secara berurutan. Waktu yang diperlukan untuk berganti bus dapat diabaikan. Dengan kata lain, agar dapat berganti ke bus yang berangkat dari suatu halte pada suatu waktu, ia cukup tiba di halte tersebut pada waktu keberangkatan bus itu atau sebelumnya. Ia juga boleh menggunakan halte yang sama beberapa kali.

Dengan kondisi tersebut, JOI-kun ingin mengetahui kapan ia harus meninggalkan rumah agar tiba di kampus tepat waktu untuk kuliah. Namun, waktu dimulainya kuliah pertama berbeda-beda setiap hari. Untuk $Q$ hari tertentu, diketahui batas waktu tiba di halte $N$ agar tidak terlambat kuliah pada hari tersebut. Untuk setiap hari, paling lambat kapan JOI-kun harus tiba di halte $1$ agar tidak terlambat kuliah?

Tugas

Diberikan informasi perjalanan bus. Untuk $Q$ hari tertentu, diberikan pula batas waktu tiba di halte $N$. Tentukan untuk masing-masing hari waktu paling lambat JOI-kun harus tiba di halte $1$.

Masukan

Bacalah data berikut dari masukan standar.

• Baris pertama berisi dua bilangan bulat $N,M$ yang dipisahkan oleh spasi, menyatakan bahwa Kota IOI memiliki $N$ halte dan $M$ perjalanan bus.
• Baris ke-$i$ ($1 \le i \le M$) dari $M$ baris berikutnya berisi empat bilangan bulat $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$), dipisahkan oleh spasi. Artinya bus ke-$i$ berangkat dari halte $A_i$ pada waktu $X_i$ dan tiba di halte $B_i$ pada waktu $Y_i$. Waktu dinyatakan dalam milidetik sejak tepat pukul $00.00$.
• Baris berikutnya berisi bilangan bulat $Q$. Artinya batas waktu tiba di halte $N$ diberikan untuk $Q$ hari.
• Baris ke-$j$ ($1 \le j \le Q$) dari $Q$ baris berikutnya berisi bilangan bulat $L_j$. Artinya pada hari ke-$j$, ia harus tiba di halte $N$ paling lambat pada waktu $L_j$.

Keluaran

Tuliskan $Q$ baris ke keluaran standar. Pada baris ke-$j$ ($1 \le j \le Q$), tuliskan bilangan bulat yang menyatakan waktu paling lambat JOI-kun harus tiba di halte $1$ pada hari ke-$j$. Namun, jika ia tidak mungkin tiba di kampus tepat waktu untuk kuliah, keluarkan -1.

Batasan

Semua data masukan memenuhi syarat-syarat berikut.

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

Subsoal

Subsoal 1 [20 poin]

Syarat-syarat berikut terpenuhi.

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

Subsoal 2 [15 poin]

Syarat-syarat berikut terpenuhi.

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

Subsoal 3 [15 poin]

• $Q=1$.

Subsoal 4 [50 poin]

Tidak ada batasan tambahan.

Contoh

Masukan 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

Keluaran 1

-1
5
10
30

Penjelasan

Tidak mungkin tiba di halte $5$ paling lambat pada waktu $10$.

Agar tiba paling lambat pada waktu $30$, ia dapat menaiki bus keempat pada waktu $5$.

Agar tiba paling lambat pada waktu $60$, ia dapat melakukan hal berikut.

• Pada waktu $10$, naik bus pertama.
• Pada waktu $25$, tiba di halte $2$, menunggu $1$ milidetik, lalu naik bus ketiga.
• Pada waktu $50$, tiba di halte $5$.

Agar tiba paling lambat pada waktu $100$, ia dapat melakukan hal berikut.

• Pada waktu $30$, naik bus kelima.
• Pada waktu $40$, tiba di halte $4$, menunggu $10$ milidetik, lalu naik bus keenam.
• Pada waktu $70$, tiba di halte $5$.

Masukan 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

Keluaran 2

0
0
0
1
1
2