Spiral Rectangle Sums

A grid of size $(2n+1) \times (2n+1)$ is filled as follows. Write $1$ in the center square, write $2$ in the square to its right, then keep writing the following numbers along a counterclockwise spiral.

A square is addressed by integer coordinates $(x, y)$. The center square is $(0, 0)$, $x$ grows to the right, and $y$ grows upward, so every square of the grid satisfies $-n \le x \le n$ and $-n \le y \le n$. The grid for $n = 2$ looks like this.

You are given $q$ rectangular regions. For each region, compute the sum of the numbers inside it modulo $10^9+7$.

The first line contains the size of the grid $n$ and the number of queries $q$.

Each of the next $q$ lines contains four integers $x_1$, $y_1$, $x_2$, $y_2$. They describe the rectangular region with corners $(x_1, y_1)$ and $(x_2, y_2)$, that is, every square with $x_1 \le x \le x_2$ and $y_1 \le y \le y_2$.

For each query, print on its own line the sum of the numbers inside the region modulo $10^9+7$.

• $1 \le n \le 10^9$
• $1 \le q \le 100$
• $-n \le x_1 \le x_2 \le n$
• $-n \le y_1 \le y_2 \le n$