11660.py

# 구간 합 구하기 5 실패
# 시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
# 1 초	256 MB	88127	40444	29902	44.012%
# 문제
# N×N개의 수가 N×N 크기의 표에 채워져 있다. 
# (x1, y1)부터 (x2, y2)까지 합을 구하는 프로그램을 작성하시오. (x, y)는 x행 y열을 의미한다.

# 예를 들어, N = 4이고, 표가 아래와 같이 채워져 있는 경우를 살펴보자.

# 1	2	3	4
# 2	3	4	5
# 3	4	5	6
# 4	5	6	7
# 여기서 (2, 2)부터 (3, 4)까지 합을 구하면 3+4+5+4+5+6 = 27이고, (4, 4)부터 (4, 4)까지 합을 구하면 7이다.

# 표에 채워져 있는 수와 합을 구하는 연산이 주어졌을 때, 이를 처리하는 프로그램을 작성하시오.

# 입력
# 첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. 
# (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 
# 다음 M개의 줄에는 네 개의 정수 x1, y1, x2, y2 가 주어지며, (x1, y1)부터 (x2, y2)의 합을 구해 출력해야 한다. 
# 표에 채워져 있는 수는 1,000보다 작거나 같은 자연수이다. (x1 ≤ x2, y1 ≤ y2)

# 출력
# 총 M줄에 걸쳐 (x1, y1)부터 (x2, y2)까지 합을 구해 출력한다.


# Solution code
import sys
input = sys.stdin.readline
n, m = map(int, input().split())    # n: 2차원 리스트의 크기, m: 질의 횟수
A = [[0]*(n+1)] 
D = [[0]*(n+1) for _ in range(n+1)] 

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

# 해설
# 1. A: 입력받은 표의 값을 저장하는 리스트
# [0]을 n+1개 갖도록 초기화됨
# 즉, (1 x n+1) 크기의 리스트 [[0], ..., [0]]

# row = [0] + [int(x) for x in input().split()]
# 1열은 [0]으로 고정하고 나머지 요소들은 입력받은 값으로 초기화

# Q. 1행과 1열의 모든 요소를 공통적으로 [0]으로 초기화 한 이유?
# A. 구간이 1부터 주어지므로 표현을 맞추기 위해!


# 2. D: 누적합을 저장하는 리스트
# 각 요소를 [0]으로 하는 (n+1 x n+1) 크기의 2차원 리스트

# Q. 여기서는 고정적으로 1행과 1열을 [0]으로 초기화할 필요 없나?
# A. 이중for문에서 range(1, n+1)로 시작하므로 필요없음!


# 3. D[i][j] = D[i][j-1] + D[i-1][j] - D[i-1][j-1] + A[i][j]
# => D[i][j] = (i, j)까지의 합, 즉, 구간의 누적합 리스트의 요소


# 4. res = D[x2][y2] - D[x1-1][y2] - D[x2][y1-1] + D[x1-1][y1-1]
# => (x1, y1)부터 (x2, y2)까지의 합을 구하는 공식


# Keypoints
# 1. 입력을 1줄에 같이 받을 때 map 함수를 적절히 사용하자!
# x, y = map(int, input().split()) => x와 y에 각각 정수형으로 변환된 입력값을 할당