Lộ Trình Moo II

Bessie du lịch qua các sân bay sử dụng các chuyến bay có thể du hành thời gian. Cô bắt đầu tại sân bay 1 vào thời điểm 0 và cần tìm thời điểm đến sớm nhất tại mỗi sân bay.

Mỗi chuyến bay $j$ xuất phát từ sân bay $c_j$ lúc $r_j$, đến sân bay $d_j$ lúc $s_j$. Du hành thời gian có thể xảy ra ($s_j<r_j$ được phép). Tại mỗi sân bay $i$, có thời gian chờ nối chuyến $a_i$: để lên chuyến bay khởi hành lúc $r$ từ sân bay $i$, Bessie phải đến sân bay $i$ không muộn hơn thời điểm $r-a_i$.

Dữ liệu vào

• Dòng 1: Hai số nguyên $N$ và $M$ ($1\le N,M\le 2·{10}^5$) — số sân bay và số chuyến bay.
• $M$ dòng tiếp theo: Bốn số nguyên $c_j$, $r_j$, $d_j$, $s_j$ — sân bay đi, thời gian đi, sân bay đến, thời gian đến.
• Dòng cuối: $N$ số nguyên $a_1,a_2,\dots ,a_N$ — thời gian chờ nối chuyến tại mỗi sân bay.

Dữ liệu ra

• $N$ dòng, mỗi dòng chứa thời điểm đến sớm nhất tại sân bay $i$, hoặc $-1$ nếu không thể đến được.

Ràng buộc

• $1\le N,M\le 2·{10}^5$
• $0\le r_j,s_j\le {10}^9$
• $0\le a_i\le {10}^9$
• Giới hạn thời gian: 4 giây

Ví dụ