Sinh viên JOI-kun đi học bằng xe buýt. Nhà của cậu và trường đại học mà cậu theo học đều nằm trong thành phố IOI. Thành phố IOI có $N$ trạm xe buýt được đánh số từ $1$ đến $N$. Trạm gần nhà JOI-kun nhất là trạm $1$, còn trạm gần trường đại học nhất là trạm $N$.
Có $M$ chuyến xe buýt hoạt động trong thành phố IOI. Mỗi chuyến chạy một lần mỗi ngày, xuất phát từ một trạm xác định vào thời điểm xác định và đến một trạm xác định vào thời điểm xác định. Không có chuyến nào chạy qua nửa đêm sang ngày hôm sau. JOI-kun không thể lên hoặc xuống xe giữa chừng.
Mỗi ngày, JOI-kun đến trường bằng một hoặc nhiều chuyến xe buýt. Có thể bỏ qua thời gian cần thiết để chuyển xe. Nói cách khác, để chuyển sang một chuyến xe xuất phát từ một trạm vào một thời điểm nào đó, cậu chỉ cần đến trạm đó không muộn hơn thời điểm xuất phát của chuyến xe. Cậu cũng được phép sử dụng cùng một trạm nhiều lần.
Với những điều kiện này, JOI-kun muốn biết nên rời nhà khi nào để đến trường kịp giờ học. Tuy nhiên, thời điểm bắt đầu tiết học đầu tiên thay đổi tùy ngày. Trong một khoảng gồm $Q$ ngày, ta biết thời hạn phải đến trạm $N$ để kịp giờ học của từng ngày. Với mỗi ngày, muộn nhất JOI-kun phải đến trạm $1$ vào lúc nào để kịp giờ học?
Nhiệm vụ
Cho thông tin về lịch trình xe buýt. Ngoài ra, với mỗi ngày trong $Q$ ngày, cho thời hạn phải đến trạm $N$. Hãy xác định, đối với từng ngày, thời điểm muộn nhất mà JOI-kun cần đến trạm $1$.
Dữ liệu vào
Đọc dữ liệu sau từ đầu vào chuẩn.
- Dòng đầu tiên chứa hai số nguyên $N,M$ cách nhau bởi dấu cách, cho biết thành phố IOI có $N$ trạm và $M$ chuyến xe buýt.
- Dòng thứ $i$ ($1 \le i \le M$) trong $M$ dòng tiếp theo chứa bốn số nguyên $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$), cách nhau bởi dấu cách. Chuyến xe thứ $i$ xuất phát từ trạm $A_i$ vào thời điểm $X_i$ và đến trạm $B_i$ vào thời điểm $Y_i$. Các thời điểm được biểu diễn bằng số mili giây đã trôi qua kể từ đúng 0 giờ.
- Dòng tiếp theo chứa số nguyên $Q$, cho biết số ngày mà thời hạn đến trạm $N$ được cung cấp.
- Dòng thứ $j$ ($1 \le j \le Q$) trong $Q$ dòng tiếp theo chứa số nguyên $L_j$, cho biết vào ngày thứ $j$ phải đến trạm $N$ không muộn hơn thời điểm $L_j$.
Dữ liệu ra
Ghi $Q$ dòng ra đầu ra chuẩn. Dòng thứ $j$ ($1 \le j \le Q$) chứa một số nguyên biểu diễn thời điểm muộn nhất JOI-kun phải đến trạm $1$ vào ngày thứ $j$. Nếu không thể đến trường kịp giờ học, hãy ghi $-1$.
Giới hạn
Tất cả dữ liệu vào thỏa mãn các điều kiện sau.
- $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$).
Nhiệm vụ con
Nhiệm vụ con 1 [20 điểm]
Thỏa mãn các điều kiện sau.
- $N \le 2\,000$.
- $M \le 2\,000$.
- $Q=1$.
Nhiệm vụ con 2 [15 điểm]
Thỏa mãn các điều kiện sau.
- $N \le 2\,000$.
- $M \le 2\,000$.
Nhiệm vụ con 3 [15 điểm]
- Thỏa mãn $Q=1$.
Nhiệm vụ con 4 [50 điểm]
Không có giới hạn bổ sung.
Ví dụ
Dữ liệu vào 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
Dữ liệu ra 1
-1 5 10 30
Ghi chú
Không thể đến trạm $5$ không muộn hơn thời điểm $10$.
Để đến không muộn hơn thời điểm $30$, có thể lên chuyến xe thứ 4 vào thời điểm $5$.
Để đến không muộn hơn thời điểm $60$, có thể làm như sau.
- Lên chuyến xe thứ 1 vào thời điểm $10$.
- Đến trạm $2$ vào thời điểm $25$, đợi 1 mili giây rồi lên chuyến xe thứ 3.
- Đến trạm $5$ vào thời điểm $50$.
Để đến không muộn hơn thời điểm $100$, có thể làm như sau.
- Lên chuyến xe thứ 5 vào thời điểm $30$.
- Đến trạm $4$ vào thời điểm $40$, đợi 10 mili giây rồi lên chuyến xe thứ 6.
- Đến trạm $5$ vào thời điểm $70$.
Dữ liệu vào 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
Dữ liệu ra 2
0 0 0 1 1 2