Звёздочки в прямоугольнике

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

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

В первой строке числа $n$ и $m$ от $1$ до $500$ и число $q$ от $1$ до $10^5$. В следующих $n$ строках по $m$ символов. В последней строке $4q$ чисел: подряд идущие четвёрки $r_1$, $c_1$, $r_2$, $c_2$, причём $r_1 \le r_2$ и $c_1 \le c_2$. Нумерация с единицы.

$q$ чисел через пробел.

Отвечать на каждый запрос обходом прямоугольника — это до двадцати пяти миллиардов действий. Накопленные суммы из двадцать девятого занятия работают и на плоскости: заведите таблицу сумм по прямоугольникам от левого верхнего угла, и любой запрос сведётся к четырём числам.