Есть n грядок, пронумерованных от 1 до n. Изначально каждая грядка получила 0 литров воды.

Система автополива выполняет k команд. Каждая команда задаётся тремя числами l, r, x и означает: полить все грядки с номерами от l до r включительно, добавив каждой по x литров воды.

После выполнения всех команд поступает q запросов. Каждый запрос задаётся двумя числами L, R. Для каждого запроса требуется определить, сколько всего литров воды было вылито на грядки с L по R включительно после применения всех команд.

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

Первая строка содержит три целых числа n, k, q — количество грядок, количество команд автополива и количество запросов.

В следующих k строках содержится по три целых числа l, r, x — описание команды полива.

В следующих q строках содержится по два целых числа L, R — границы запроса.

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

Для каждого запроса выведите в отдельной строке одно целое число — суммарный объём воды на грядках от L до R после выполнения всех команд.

Ограничения

• 1 <= n <= 2 * 10^5
• 1 <= k, q <= 2 * 10^5
• 1 <= l <= r <= n
• 1 <= L <= R <= n
• -10^9 <= x <= 10^9

Примеры

Пример 1

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

5 4 4
1 1 1000000000
2 2 -1000000000
3 3 1000000000
4 4 -1000000000
1 5
1 1
2 2
3 3

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

0
1000000000
-1000000000
1000000000

Пример 2

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

8 7 7
1 8 -5
2 7 2
3 6 -1
4 5 -5
4 5 2
3 6 -1
2 7 -5
1 8
1 4
4 8
2 8
1 1
8 8
2 5

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

-72
-36
-49
-67
-5
-5
-44