**Замечание: Время на тест в этой задаче 4 сек, в два раза больше времени на тест по умолчанию.**
Беси на каникулах, она может путешествовать во времени, И нет проблем
если две версии Беси встретятся.
В этой стране имеется \(N\) аэропортов, пронумерованных \(1, 2, \ldots, N\) и
\(M\) полётов во времени (\(1\leq N, M \leq 200000\)). Полёт \(j\) вылетает из
аэропорта \(c_j\) в момент времени \(r_j\), и прибывает в аэропорт \(d_j\) в
момент времени \(s_j\) (\(0 \leq r_j, s_j \leq 10^9\), \(s_j < r_j\) - такое возможно!).
Кроме того, она должна потратить \(a_i\) времени для пересадки в аэропорту \(i\)
(\(1\le a_i\le 10^9\)).
Необходимо отметить, что если Беси прилетает в аэропорт \(i\) в момент времени \(s\),
она может пересесть на рейс, который отправляется в момент времени \(r\), только
если \(r \geq s + a_i\).
Беси начинает в городе \(1\) в момент времени \(0\). Для каждого аэропорта
от \(1\) to \(N\), каково минимальное время когда Беси сможет в него попасть?
ФОРМАТ ВВОДА (с клавиатуры / stdin):
Первая строка ввода содержит
\(N\) и
\(M\).
Следующие \(M\) строк описывают полёты. \(j\)-ая из этих строк содержит \(c_j\),
\(r_j\), \(d_j\), \(s_j\) в указанном порядке. (\(1\leq c_j, d_j \leq N\),
\(0\leq r_j, s_j \leq 10^9\))
Следующая строка описывает аэропорты - она содержит \(N\) разделённых
одиночными пробелами целых чисел \(a_1, \ldots, a_N\).
ФОРМАТ ВЫВОДА (на экран / stdout):
На выводе должно быть \(N\) строк. Строка \(i\) содержит самое раннее время, в которое
Беси может добраться в аэропорт \(i\) или -1, если Беси не может добраться в этот аэропорт.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 3
1 0 2 10
2 11 2 0
2 1 3 20
10 1 10
|
0
0
20
|