У вас есть \(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++).
Выходные данные
Для каждого набора входных данных выведите \(q\) строк, \(i\)-я должна содержать ответ на \(i\)-й запрос.
Примечание
В первом наборе входных данных только один запрос. Нам надо найти сумму площадей всех прямоугольников, которые вмещают прямоугольник \(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\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
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
|