Бесі збирається на екскурсію. Маршрут складається з \(N\) пунктів пронумерованих \(1\ldots N\) (\(1\le N\le 10^5\)).

Є \(K\) (\(1\le K\le 10^5\)) квитків доступних для продажу. \(i\)-ий квиток можна купити в пункті \(c_i\) (\(1\le c_i\le N\)) за ціну \(p_i\) (\(1\le p_i\le 10^9\)) і забезпечити собі доступ до всіх пунктів \([a_i,b_i]\) (\(1\le a_i\le b_i\le N\)). Перш ніж увійти до будь-якого пункту, Бесі має купити квиток який забезпечує доступ до цього пункту. Купивши одного разу квиток у пункт, Бесі може повертатися до нього будь-якої миті у майбутньому.

Для кожного \(i\in [1,N]\), виведіть мінімальну сумарну ціну, яку потрібно заплатити, щоб отримати доступ до обох пунктів \(1\) і \(N\), якщо спочатку Бесі мала доступ лише до пункту \(i\). Якщо це неможливо, виведіть \(-1\).

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

Перший рядок введення містить \(N\) та \(K\).

Кожен із наступних \(K\) рядків містить чотири цілих числа \(c_i\), \(p_i\), \(a_i\), \(b_i\) для кожного \(1 \ le i \ le K \).

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

\(N\) рядків, по одному для кожного пункту.

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

7 6
4 1 2 3
4 10 5 6
2 100 7 7
6 1000 1 1
5 10000 1 4
6 100000 5 6

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

-1
-1
-1
1111
10100
110100
-1

Пояснення до прикладу-1

<Якщо Бесі стартує з пункту \(i=4\), існує тільки один спосіб отримати доступ до всіх пунктів від \(1\) до \(N\) і він такий:

1. Купити перший квиток у пункті \(4\), що дасть Бесі доступ до точок \(2\) та \(3\).
2. Купити третій квиток у точку \(2\), що дає Бесі доступ до точки \(7\)
3. Повернутися до точки \(4\) і купити другий квиток, що дасть Бесі доступ до точок \(5\) та \(6\).
4. Купити четвертий квиток у точці \(6\),що дасть Бесі доступ до точки 1

Оцінювання

• У тестах 1-7 \(N,K\le 1000\).
• У тестах 8-19 немає додаткових обмежень.