JOI là một sinh viên đại học đi học bằng xe buýt. Nhà của JOI và trường đại học đều nằm trong thành phố IOI. Thành phố có \(N\) trạm xe buýt, được đánh số từ \(1\) đến \(N\). Trạm gần nhà JOI nhất là trạm \(1\), còn trạm gần trường nhất là trạm \(N\).

Có \(M\) chuyến xe buýt hoạt động trong thành phố. Mỗi chuyến chạy đúng một lần mỗi ngày, xuất phát từ một trạm xác định vào một thời điểm xác định và đến một trạm xác định vào một thời điểm xác định. Không có chuyến nào kéo dài sang ngày hôm sau. JOI không thể lên hoặc xuống xe giữa hành trình của một chuyến.

Mỗi ngày, JOI đi một hoặc nhiều chuyến xe buýt để đến trường. Có thể bỏ qua thời gian cần để chuyển xe: để lên một chuyến xuất phát từ một trạm vào một thời điểm nào đó, JOI chỉ cần đến trạm ấy trước hoặc đúng thời điểm xe xuất phát. JOI cũng có thể đi qua cùng một trạm nhiều lần.

Với những điều kiện trên, JOI muốn biết mình nên rời nhà khi nào để đến trường kịp giờ học. Tuy nhiên, giờ bắt đầu tiết học đầu tiên thay đổi theo từng ngày. Với \(Q\) ngày, đã biết thời điểm muộn nhất JOI phải đến trạm \(N\) để kịp giờ học trong từng ngày. Trong mỗi ngày đó, JOI có thể đến trạm \(1\) muộn nhất vào thời điểm nào mà vẫn kịp giờ học?

Yêu cầu

Cho thông tin về các chuyến xe buýt và thời điểm muộn nhất phải đến trạm \(N\) trong từng ngày của \(Q\) ngày, hãy tìm thời điểm muộn nhất JOI có thể đến trạm \(1\) trong mỗi ngày.

Dữ liệu vào

Đọc dữ liệu từ đầu vào chuẩn:

• Dòng đầu chứa hai số nguyên \(N, M\) cách nhau bởi dấu cách, cho biết thành phố có \(N\) trạm và \(M\) chuyến xe buýt.
• Trong \(M\) dòng tiếp theo, dòng thứ \(i\) (\(1 \le i \le M\)) chứa bốn số nguyên \(A_i, B_i, X_i, Y_i\) cách nhau bởi dấu cách, với \(1 \le A_i \le N\), \(1 \le B_i \le N\) và \(A_i \ne B_i\). 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\). Thời điểm được tính 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\), là số ngày được cho thời hạn đến trạm \(N\).
• Trong \(Q\) dòng tiếp theo, dòng thứ \(j\) (\(1 \le j \le Q\)) chứa số nguyên \(L_j\): trong ngày thứ \(j\), JOI phải đến trạm \(N\) trước hoặc đúng 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 là thời điểm muộn nhất JOI có thể đến trạm \(1\) trong ngày thứ \(j\) mà vẫn đến trường kịp giờ học. Nếu không thể đến trường kịp giờ, ghi -1.

Ràng buộc

Tất cả dữ liệu vào thỏa mãn:

• \(2 \le N \le 100\,000\).
• \(1 \le M \le 300\,000\).
• \(0 \le X_i < Y_i < 86\,400\,000\) (\(1 \le i \le M\)).
• \(1 \le Q \le 100\,000\).
• \(0 \le L_j < 86\,400\,000\) (\(1 \le j \le Q\)).

Ở đây, \(86\,400\,000 = 24 \times 60 \times 60 \times 1000\).

Phân nhóm

• Nhóm 1 (20 điểm): \(N \le 2\,000\), \(M \le 2\,000\), \(Q = 1\).
• Nhóm 2 (15 điểm): \(N \le 2\,000\), \(M \le 2\,000\).
• Nhóm 3 (15 điểm): \(Q = 1\).
• Nhóm 4 (50 điểm): Không có ràng buộc bổ sung.

Ví dụ

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
5
10
30

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

0
0
0
1
1
2