Беси собирается на экскурсию. Маршрут состоит из n пунктов пронумерованных 1..n. Имеется k билетов доступных для продажи. i-ый билет можно купить в пункте ci за цену pi и обеспечить себе доступ ко всем пунктам [ai, bi]. Прежде чем войти в любой пункт, Беси должна купить билет который обеспечивает доступ в этот пункт. Купив однажды билет в пункт, Беси может возвращаться в него в любой момент в будущем.

Для каждого i ∈ [1, n], выведите минимальную суммарную цену которую требуется заплатить, чтобы получить доступ к обоим пунктам 1 и n, если изначально Беси имела доступ только к пункту i. Если это невозможно, выведите −1.

Входные данные

Первая строка ввода содержит n (1 ≤ n ≤ 105) и k (1 ≤ k ≤ 105).

Каждая из последующих k строк содержит четыре целых числа ci (1 ≤ ci ≤ n), pi (1 ≤ pi ≤ 109), ai и bi (1 ≤ ai ≤ bi ≤ n) для каждого i (1 ≤ i ≤ k).

Выходные данные

Выведите n строк, по одной для каждого пункта.

Пример

Если Беси стартует из пункта i = 4, существует только один способ получить доступ ко всем пунктам от 1 до n и он таков:

• Купить первый билет в пункте 4, что даст Беси доступ к точкам 2 и 3.
• Купить третий билет в точку 2, что даёт Беси доступ к точке 7.
• Вернуться в точку 4 и купить второй билет, что даст Беси доступ к точкам 5 и 6.
• Купить четвёртый билет в точке 6, что даст Беси доступ в точку 1.