2차원 배열 구간 합

정수로 이루어진 N행 M열 배열이 주어진다. 여러 질의에 대해, 각 질의가 지정하는 왼쪽 위 위치 (i, j)부터 오른쪽 아래 위치 (x, y)까지의 직사각형 영역에 들어 있는 모든 수의 합을 구하라.

배열의 위치 (i, j)는 i번째 행, j번째 열을 뜻한다.

첫째 줄에 배열의 크기 N, M이 주어진다. (1 <= N, M <= 300)

다음 N개의 줄에는 각 줄마다 M개의 정수가 주어진다. 배열의 각 수는 절댓값이 10,000 이하인 정수이다.

그다음 줄에 합을 구할 부분 직사각형의 개수 K가 주어진다. (1 <= K <= 10,000)

다음 K개의 줄에는 네 정수 i, j, x, y가 주어진다. 이는 (i, j)부터 (x, y)까지의 합을 묻는 질의이며, 항상 1 <= i <= x <= N, 1 <= j <= y <= M을 만족한다.

질의가 주어진 순서대로, 각 부분 직사각형에 포함된 수의 합을 한 줄에 하나씩 출력한다. 각 합은 2^31 - 1보다 작거나 같다.