Бесі на канікулах, вона може подорожувати в часі, і немає проблем якщо дві версії Бесі зустрінуться.

У цій країні є \(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\) знайдіть мінімальний час, за який Бесі зможе до нього потрапити?

Формат вхідних даних

Перший рядок введення містить \(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\).

Формат вихідних даних

На виводі має бути \(N\) рядків. Рядок \(i\) містить ранній час, в який Бесі може дістатися аеропорту \(i\) або -1, якщо Бесі не може дістатися цього аеропорту.

Приклад вхідних даних

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

Приклад вихідних даних

0
0
20

Бесі може виконати 3 польоти у вказаному порядку, що дозволить їй прибути в аеропорти 1 та 2 в момент часу 0, а в аеропорт 3 в момент часу 20.

Зауважимо, що цей маршрут проходить через аеропорт двічі, перший раз на момент часу 10-11, другий раз на момент часу 0-1.

Приклад вхідних даних

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

Приклад вихідних даних

0
10
-1

Бесі може вибрати політ 1 і прибути в аеропорт 2 в момент часу 10. Однак вона запізниться на політ 2, оскільки його відправлення о 10-й, а їй потрібно ще 1 одиниця часу на переміщення аеропорту.

ОЦІНЮВАННЯ:

• У тестах 3-5: \(r_j < s_j\) для всіх \(j\), тобто всі польоти прибувають після того, як вони вилетять.
• У тестах 6-10: \(N, M \leq 5000\)
• У тестах 11-20: Немає додаткових обмежень.