A. Егор и массив
ограничение по времени на тест
1.5 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У Егора есть массив 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, m, k (1 ≤ n, m, k ≤ 105). Во второй строке заданы n целых чисел: a1, a2, ..., an (0 ≤ ai ≤ 105) — изначальный массив.

В следующих m строках заданы операции, операция с номером i записана тремя целыми числами: li, ri, di, (1 ≤ li ≤ ri ≤ n), (0 ≤ di ≤ 105).

В следующих k строках заданы запросы, запрос с номером i записан двумя целыми числами: xi, yi, (1 ≤ xi ≤ yi ≤ m).

Числа в строках разделяются одиночными пробелами.

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

В единственную строку выведите n целых чисел a1, a2, ..., an — массив, который получит Егор после применения всех запросов. Выведенные числа разделяйте пробелами.

Пожалуйста, не используйте спецификатор %lld для чтения или записи 64-х битовых чисел на C++. Рекомендуется использовать потоки cin, cout или спецификатор %I64d.

Примеры
Входные данные
3 3 3
1 2 3
1 2 1
1 3 2
2 3 4
1 2
1 3
2 3
Выходные данные
9 18 17
Входные данные
1 1 1
1
1 1 1
1 1
Выходные данные
2
Входные данные
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