Bessie đang đi nghỉ! Với một số tiến bộ công nghệ gần đây, Bessie sẽ đi bằng các chuyến bay có công nghệ cao, thậm chí có thể du hành thời gian. Hơn nữa, sẽ không có vấn đề gì nếu hai phiên bản "song song" của Bessie gặp nhau.

Trong nước có \(N\) sân bay được đánh số \(1,2,...,N\) và \(M\) chuyến bay du hành thời gian \((1 \leq N,M \leq 200000)\). Chuyến bay \(j\) rời sân bay \(c_j\) tại thời điểm \(r_j\), và đến sân bay \(d_j\) tại thời điểm \(s_j\) \((0 \leq r_j,s_j \leq 10^9)\). Ngoài ra, nó phải mất \(a_i\) thời gian cho việc quá cảnh tại sân bay \(i (1 \leq a_i \leq 10^9)\). (Nghĩa là, nếu Bessie đáp chuyến bay đến sân bay \(i\) tại thời điểm \(s\), thì nó có thể chuyển sang chuyến bay rời sân bay vào thời điểm \(r\) nếu \(s+a_i \leq r\). Việc quá cảnh không diễn ra khi Bessie đến sân bay.)

Bessie bắt đầu tại thành phố \(1\) vào lúc \(0\) . Đối với mỗi sân bay từ \(1\) đến \(N\), thời gian sớm nhất mà Bessie có thể đến đó là khi nào?

Input

• Dòng đầu tiên chứa N và M.
• \(M\) dòng tiếp theo mô tả các chuyến bay. Dòng thứ \(j\) trong số các dòng này chứa \(c_j\) , \(r_j\) , \(d_j\) , \(s_j\) theo thứ tự đó. \((1 \leq c_j,d_j \leq N, 0 \leq r_j,s_j \leq 10^9 )\)
• Dòng tiếp theo mô tả các sân bay. Nó chứa \(N\) số nguyên cách nhau bằng dấu cách \(a_1,…,a_N\).

Output

In ra \(N\) dòng, dòng thứ \(i\) chứa thời gian sớm nhất Bessie có thể đến sân bay \(i\), hoặc \(-1\) nếu Bessie không thể đến sân bay đó.

Scoring

• Subtask \(1\): \(r_j<s_j\) cho tất cả \(j\), tức là tất cả các chuyến bay đều đến sau khi chúng khởi hành.
• Subtask \(2\): \(N,M \leq 5000\)
• Subtask \(3\): Không có điều kiện gì thêm.

Example

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

0
0
20

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

0
10
-1