Беси собирается на экскурсию. Маршрут состоит из \(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\).
ФОРМАТ ВВОДА (с клавиатуры / stdin):
Первая строка ввода содержит
\(N\) и
\(K\).
Каждая из последующих \(K\) строк содержит четыре целых числа
\(c_i\), \(p_i\), \(a_i\), \(b_i\)
для каждого \(1\le i\le K\).
ФОРМАТ ВЫВОДА (на экран / stdout):
\(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
1111
10100
110100
-1
|