A, B, C, D 쿼리에 대한 답을 f(A, B, C, D)라 하자.


 B - A, D - C 가 모두 홀수거나 짝수면 대칭성에 의해 0이 아닌 칸에 쓰여진 모든 숫자의 평균은 ((A+B)/2-1) * M + (C+D)/2 으로 구할 수 있으므로


 0이 아닌 숫자가 쓰여진 칸의 갯수만 구하면 간단히 구할 수 있다.


 이제 B - A 와 D - C 가 홀짝, 또는 짝홀인 경우를 살펴보면


 B - A 가 홀수면 f(A, B, C, D) = f(A, B-1, C, D) + f(B, B, C, D) 

 D - C가 홀수면 f(A, B, C, D) = f(A, B, C, D-1) + f(A, B, D, D) 로 바꾸고 위에서 구한 방법 이용하면 끝