Подсчёт прямоугольников

У вас $n$ прямоугольников, у $i$-го высота $h_i$ и ширина $w_i$. Даны $q$ запросов: в каждом числа $h_s, w_s, h_b, w_b$. Найдите сумму площадей $\sum h_i w_i$ всех прямоугольников, для которых $h_s < h_i < h_b$ и $w_s < w_i < w_b$ (строгие неравенства). Поворачивать прямоугольники нельзя.

В первой строке $n$ и $q$ ($1 \le n, q \le 10^5$). В следующих $$ строках и (). В следующих строках , , , (, ).

Для каждого запроса одно число в отдельной строке.

Размеры маленькие: постройте таблицу $1000 \times 1000$, где $c_{h,w}$ — сумма площадей прямоугольников высоты $h$ и ширины $w$. По её двумерным префиксным суммам каждый запрос — сумма по строкам и столбцам , за .