Forest queries

You are given an $n \times n$ map of a forest: * is a tree, . is empty. Rows are numbered from top to bottom and columns from left to right, from $1$ to $n$. For every query find the number of trees in a rectangle.

The first line contains $n$ and $q$ ($1 \le n \le 1000$, $1 \le q \le 2 \cdot 10^5$). The next $n$ lines contain the map. The next $q$ lines contain $y_1$, $x_1$, $y_2$, $x_2$ ($1 \le y_1 \le y_2 \le n$, $1 \le x_1 \le x_2 \le n$) — the top-left and bottom-right cells of the rectangle (row, column).

For every query print one number on a separate line.

2D prefix sums: $P_{i,j}$ is the number of trees in the rectangle from $(1, 1)$ to $(i, j)$, $P_{i,j} = c_{i,j} + P_{i-1,j} + P_{i,j-1} - P_{i-1,j-1}$. A query is answered by inclusion–exclusion: $P_{y_2,x_2} - P_{y_1-1,x_2} - P_{y_2,x_1-1} + P_{y_1-1,x_1-1}$.

Counting cells in every query is $O(n^2 q)$ — $2 \cdot 10^{11}$ operations.

Source: CSES, problem 1652.