В бонусной системе есть n дней, и изначально за каждый день начислено 0 бонусов.

Затем система выполняет m операций. Каждая операция задаётся тройкой l, r, v и означает, что ко всем дням с номерами от l до r включительно нужно прибавить по v бонусов.

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

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

Первая строка содержит два целых числа n и m — количество дней и количество операций начисления.

В следующих m строках содержатся по три целых числа l, r, v — описание операции прибавления бонусов на отрезке дней.

Затем дано целое число q — количество запросов.

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

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

Для каждого запроса выведите одно целое число — сумму бонусов на соответствующем отрезке дней.

Каждый ответ выводите в отдельной строке.

Ограничения

• 1 <= n, m <= 2 * 10^5
• 1 <= q <= 2 * 10^5
• 1 <= l <= r <= n
• 1 <= v <= 2 * 10^8
• Ответы могут не помещаться в 32-битный целочисленный тип, но гарантированно помещаются в 64-битный знаковый тип.

Примеры

Пример 1

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

5 4
1 1 5
2 4 3
4 5 2
1 5 1
5
1 1
1 5
2 3
4 4
3 5

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

6
23
8
6
13

Пример 2

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

6 5
1 6 10
2 2 7
5 6 4
3 5 1
4 4 20
6
1 6
2 2
4 5
6 6
1 3
3 6

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

98
17
46
14
38
71