Count Values in a Sorted Matrix

You are given a matrix $A$ of natural numbers whose rows and columns are all sorted in ascending order, so $A[i][j] \ge A[i-1][j]$ and $A[i][j] \ge A[i][j-1]$ hold for every $i$ and $j$.

You are also given one or more integer pairs $(X, Y)$ with $Y \ge X$. For each pair, count how many values of the matrix are greater than or equal to $X$ and smaller than or equal to $Y$.

The first line has the number of rows $N$ and the number of columns $M$. ($1 \le N, M \le 10000$)

The next $N$ lines give the matrix values row by row, $M$ integers per line separated by spaces.

The query pairs $(X, Y)$ follow the matrix. Each pair is two integers, and you keep reading until the input ends. There is at least one pair and at most 100 pairs, and no truncated pair is left at the end.

Every matrix value is a natural number, and those values together with $X$ and $Y$ all fit in a signed 32-bit integer. $X \le Y$ always holds. Spaces and line breaks may appear freely between the numbers.

For each query pair, print how many matrix values are greater than or equal to $X$ and smaller than or equal to $Y$, one per line, in the order the pairs are given.