Có ~N~ sân bay được đánh số từ ~1~ đến ~N~, và ~M~ chuyến bay. Mỗi chuyến bay thứ ~j~ được mô tả bởi bốn số ~c_j, r_j, d_j, s_j~:

• chuyến bay rời sân bay ~c_j~ tại thời điểm ~r_j~,
• đến sân bay ~d_j~ tại thời điểm ~s_j~.

Do đây là các chuyến bay du hành thời gian nên có thể xảy ra ~s_j < r_j~.

Ngoài ra, tại sân bay ~i~, hành khách cần ~a_i~ đơn vị thời gian để quá cảnh. Điều này có nghĩa là nếu đến sân bay ~i~ tại thời điểm ~t~, thì chỉ có thể tiếp tục đi một chuyến bay rời sân bay này tại thời điểm ~r~ nếu ~r \ge t + a_i~.

VanhG bắt đầu ở sân bay ~1~ tại thời điểm ~0~. Riêng lần xuất phát đầu tiên không cần tính thời gian quá cảnh.

Yêu cầu

Với mỗi sân bay từ ~1~ đến ~N~, hãy xác định thời điểm sớm nhất mà VanhG có thể đến được sân bay đó.

Dữ liệu

• Dòng đầu tiên chứa hai số nguyên dương ~N~ và ~M~.
• ~M~ dòng tiếp theo, dòng thứ ~j~ chứa bốn số nguyên ~c_j, r_j, d_j, s_j~ mô tả chuyến bay thứ ~j~.
• Dòng cuối cùng chứa ~N~ số nguyên ~a_1, a_2, \ldots, a_N~ mô tả thời gian quá cảnh tại các sân bay.

Kết quả

Gồm ~N~ dòng.

Dòng thứ ~i~ in ra thời điểm sớm nhất có thể đến sân bay ~i~. Nếu không thể đến được, in ra ~-1~.

Ví dụ

Ví dụ 1

Input

3 3
1 0 2 10
2 11 2 0
2 1 3 20
10 1 10

Output

0
0
20

Ví dụ 2

Input

3 3
1 0 2 10
2 10 2 0
2 1 3 20
10 1 10

Output

0
10
-1

Giải thích

Ví dụ 1

Có thể đi lần lượt cả ~3~ chuyến bay theo đúng thứ tự trong dữ liệu. Khi đó có thể đến sân bay ~2~ tại thời điểm ~10~, sau đó quay lại sân bay ~2~ ở thời điểm ~0~, rồi đi tiếp đến sân bay ~3~ ở thời điểm ~20~. Vì thế thời điểm sớm nhất đến các sân bay ~1, 2, 3~ lần lượt là ~0, 0, 20~.

Ví dụ 2

Sau chuyến bay đầu tiên, VanhG đến sân bay ~2~ tại thời điểm ~10~. Do cần ~1~ đơn vị thời gian để quá cảnh ở sân bay ~2~, anh ấy không thể bắt chuyến bay thứ hai vì chuyến này khởi hành đúng tại thời điểm ~10~.

Ràng buộc và chấm điểm

Ràng buộc

• ~1 \le N, M \le 2 \cdot 10^5~
• ~1 \le c_j, d_j \le N~
• ~0 \le r_j, s_j \le 10^9~
• ~1 \le a_i \le 10^9~

Chấm điểm

• Subtask ~1~ ~(25\%):~ ~r_j < s_j~ với mọi ~j~
• Subtask ~2~ ~(25\%):~ ~N, M \le 5000~
• Subtask ~3~ ~(50\%):~ không có ràng buộc gì thêm