Numbers in a Grid

Let $S$ be the string formed by writing all positive integers in order from 1, with no spaces, from left to right:

12345678910111213141516171819202122232425···

Many problems about $S$ already exist. In a recent written exam, a problem asked to find the $2 \times 10^6$-th digit of $S$ by hand.

The string $S$ extends infinitely to the right, but the paper this problem is printed on, or the monitor displaying it, has a fixed width. If $S$ is printed in a font where every digit has the same width, or read in a suitable editor, every row contains $M$ digits in order, as shown below.

Suppose the first $10^9 \times M$ characters of $S$ are written in order into a $10^9 \times M$ matrix $A$ in this way. The figure above shows rows 1 through 7 of $A$ when $M = 31$.

Since the data forms a 2D matrix, don't you want to compute a 2D subarray sum? Given a rectangular region $[r_1, r_2] \times [c_1, c_2]$ of $A$, write a program that computes the sum of the numbers in that region, that is, $\sum_{i=r_1}^{r_2} \sum_{j=c_1}^{c_2} A_{i,j}$. Computing it only once feels like a waste, so compute it $Q$ times.

The first line contains two integers $M$ ($1 \le M \le 100,000$) and $Q$ ($1 \le Q \le 1,000$). Each of the next $Q$ lines contains four integers $r_1$, $c_1$, $r_2$, $c_2$ ($1 \le r_1 \le r_2 \le 10^9$, $1 \le c_1 \le c_2 \le M$).

For each query, print the value of $\sum_{i=r_1}^{r_2} \sum_{j=c_1}^{c_2} A_{i,j}$ on its own line, in the order the queries are given.