Count
You have:
A matrix of natural numbers, with the property that all rows and all columns are sorted in ascending order (i.e. A[i, j] ≥ A[i-1, j] and A[i, j] ≥ A[i, j-1],
i, j)
One or several pairs of numbers (X, Y) with the property that Y ≥ X.
For each (X, Y) pair, count how many numbers from the matrix are greater than or equal to X but smaller than or equal to Y.
Input
The input file is a binary file containing 32-bit integer numbers. The input file consists of:
One integer N representing the number of rows (no more than 10000)
One integer M representing the number of columns (no more than 10000)
NxM integers, representing the values from the matrix, row by row
An unspecified number of integers, representing the (X, Y) pairs, one pair at a time. There will be at least one pair and at most 100 pairs in the file – and there will not be an incomplete pair at the end of the file.
Output
For each pair you should write to standard output a value representing how many numbers in the matrix are greater than or equal to X but smaller than or equal to Y.