У Егора есть массив a = a1, a2, ..., an и m операций. Каждая операция имеет вид: li, ri, di, (1 ≤ li ≤ ri ≤ n). Применить операцию i к массиву значит, элементы массива c номерами li, li + 1, ..., ri, увеличить на величину di.
Егор записал на листочке бумаги k запросов. Каждый запрос имеет вид: xi, yi, (1 ≤ xi ≤ yi ≤ m), что означает, что нужно применить к массиву операции с номерами xi, xi + 1, ..., yi.
Сейчас Егор хочет узнать, какой будет массив a после выполнения всех запросов. Помогите Егору.
Выходные данные
В единственную строку выведите n целых чисел a1, a2, ..., an — массив, который получит Егор после применения всех запросов. Выведенные числа разделяйте пробелами.
Пожалуйста, не используйте спецификатор %lld для чтения или записи 64-х битовых чисел на C++. Рекомендуется использовать потоки cin, cout или спецификатор %I64d.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 3 3
1 2 3
1 2 1
1 3 2
2 3 4
1 2
1 3
2 3
|
9 18 17
|
|
2
|
1 1 1
1
1 1 1
1 1
|
2
|
|
3
|
4 3 6
1 2 3 4
1 2 1
2 3 2
3 4 4
1 2
1 3
2 3
1 2
1 3
2 3
|
5 18 31 20
|