백준 11660 구간 합 구하기 2

#구간합 구하기 2
#백준 11660
#X1,Y1,X2,Y2에 대한 답을 구간합으로 구하는 방법
#D[X2][Y2]-D[X1-1][Y2]-D[X2][Y1-1]+D[X1-1][Y1-1]
#슈도코드 작성
#N(리스트 크기), M(질문 갯수)
#A(원본리스트), D(합 배열)
#for n만큼 반복 : 원본리스트 데이터 저장
#for i를 1부터 n까지 반복: for j를 1부터 n까지 반복: 합배열 저장
#for m만큼 반복 : 질의에 대한 결과 계산 및 출력
#결과 = d[x2][y2]-d[x1-1][y2]-d[x2][y1-1]+d[x1-1][y1-1]
import sys
n, m = map(int, input().split())
A = [[0] * (n+1)]
D = [[0] * (n+1) for _ in range(n+1)]

for i in range(n):
    A_row = [0] + [int(x) for x in input().split()]
    A.append(A_row)

for i in range(1, n+1):
    for j in range(1, n+1):
        D[i][j] = D[i-1][j] + D[i][j-1] - D[i-1][j-1] + A[i][j]
for _ in range(m):
    x1, y1, x2, y2 = map(int, input().split())
    print(D[x2][y2] - D[x1-1][y2] - D[x2][y1-1] + D[x1-1][y1-1])