Запросы о лесе

Дана карта леса размером $n \times n$: * — дерево, . — пусто. Строки пронумерованы сверху вниз, столбцы — слева направо от $1$ до $n$. Для каждого запроса найдите число деревьев в прямоугольнике.

В первой строке $n$ и $q$ ($1 \le n \le 1000$, $1 \le q \le 2 \cdot 10^5$). В следующих строках карта. В следующих строках , , , (, ) — верхняя левая и нижняя правая клетки прямоугольника (строка, столбец).

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

Двумерные префиксные суммы: $P_{i,j}$ — число деревьев в прямоугольнике от $(1, 1)$ до $(i, j)$, . Ответ на запрос — по формуле включений-исключений: .