시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
15 초 512 MB 45 17 4 13.793%

문제

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] for all 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.

입력

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.

출력

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.

예제 입력

2 4
1 5 10 10
2 10 20 99

10 99
2 9
100 1000
10 10

예제 출력

5
2
0
3

힌트

Sample Input, here in text form, not binary, for obvious reasons.

바이너리 형식의 예제 입력은 https://www.acmicpc.net/data/9265.in 에서 받을 수 있다.