E. Считаем прямоугольники
ограничение по времени на тест
6 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У вас есть $$$n$$$ прямоугольников, $$$i$$$-й из них имеет высоту $$$h_i$$$ и ширину $$$w_i$$$.

Вам надо ответить на $$$q$$$ запросов, которые задаются четырьмя числами: $$$h_s \ w_s \ h_b \ w_b$$$.

Для каждого запроса выведите суммарную площадь всех таких прямоугольников, которые могут вместить в себя прямоугольник с высотой $$$h_s$$$ и шириной $$$w_s$$$ и при этом сами вмещаются в прямоугольник с высотой $$$h_b$$$ и шириной $$$w_b$$$. Иными словами, выведите $$$\sum h_i \cdot w_i$$$ по всем $$$i$$$, что $$$h_s < h_i < h_b$$$ и $$$w_s < w_i < w_b$$$.

Обратите внимание, что если у прямоугольников одинаковая ширина или высота, то ни один из них не может вместить в себя другой. Также обратите внимание, что вы не можете вращать прямоугольники.

Обратите внимание, что для некоторых наборов входных данных ответ не будет помещаться в 32-х битных целочисленный тип, вы должны использовать 64-битный целочисленный тип вашего языка (например, long long в C++).

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

В первой строке входных данных записано целое число $$$t$$$ ($$$1 \leq t \leq 100$$$) — количество наборов входных данных.

Первая строка каждого набора входных данных содержит два целых числа $$$n, q$$$ ($$$1 \leq n \leq 10^5$$$; $$$1 \leq q \leq 10^5$$$) — количество прямоугольников и количество запросов.

Затем следуют $$$n$$$ строк, каждая содержит два целых числа $$$h_i, w_i$$$ ($$$1 \leq h_i, w_i \leq 1000$$$) — высоту и ширину $$$i$$$-го прямоугольника.

Затем в $$$q$$$ строках заданы запросы, каждая строка содержит четыре целых числа $$$h_s, w_s, h_b, w_b$$$ ($$$1 \leq h_s < h_b,\ w_s < w_b \leq 1000$$$) — описание запроса.

Сумма значений $$$q$$$ по всем набора входных данных не превосходит $$$10^5$$$. Сумма значений $$$n$$$ по всем наборам входных данных не превосходит $$$10^5$$$.

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

Для каждого набора входных данных выведите $$$q$$$ строк, $$$i$$$-я должна содержать ответ на $$$i$$$-й запрос.

Пример
Входные данные
3
2 1
2 3
3 2
1 1 3 4
5 5
1 1
2 2
3 3
4 4
5 5
3 3 6 6
2 1 4 5
1 1 2 10
1 1 100 100
1 1 3 3
3 1
999 999
999 999
999 998
1 1 1000 1000
Выходные данные
6
41
9
0
54
4
2993004
Примечание

В первом наборе входных данных только один запрос. Нам надо найти сумму площадей всех прямоугольников, которые вмещают прямоугольник $$$1 \times 1$$$ и сами вмещаются в прямоугольник $$$3 \times 4$$$.

Нам подходит только прямоугольник $$$2 \times 3$$$, так как $$$1 < 2$$$ (сравниваем высоты) и $$$1 < 3$$$ (сравниваем ширины), то $$$1 \times 1$$$ помещается в него. Аналогично, $$$2 < 3$$$ (сравниваем высоты) и $$$3 < 4$$$ (сравниваем ширины), то есть он помещается в $$$3 \times 4$$$.

Прямоугольник $$$3 \times 2$$$ слишком высок, чтобы поместиться в $$$3 \times 4$$$ rectangle.

Суммарная площадь в ответа равна $$$2 \cdot 3 = 6$$$.