Prefix Sum, Prefix Sum of Matrix

import sys
input = sys.stdin.readline

N, M = map(int, input().split())
lst = list(map(int, input().split()))
sum_lst = [0] * len(lst)
sum_lst[0] = lst[0]
for i in range(1, len(sum_lst)):
    sum_lst[i] = sum_lst[i - 1] + lst[i]

for _ in range(M):
    i, j = map(int, input().split())
    if i == 1: print(sum_lst[j - 1])
    else: print(sum_lst[j - 1] - sum_lst[i - 2])

'''
2차원에서 (N1, M1) 부터 (N2, M2)까지 구간합 수식
sums[N2][M2] - sums[N2][M1 - 1] - sum[N1-1][M2] + sum[N1 - 1][M1 - 1]
'''

import sys
input = sys.stdin.readline

N, M = map(int, input().split())
matrix = []
presum_matrix = [[0] * (N+1) for _ in range(N+1)]

for _ in range(N):
    a = list(map(int, input().split()))
    matrix.append(a[:])

for i in range(1, N+1):
    for j in range(1, N+1):
        presum_matrix[i][j] = matrix[i-1][j-1] + presum_matrix[i - 1][j] + presum_matrix[i][j-1] - presum_matrix[i-1][j-1]

for _ in range(M):
    x1, y1, x2, y2 = map(int, input().split())
    ans = presum_matrix[x2][y2] - presum_matrix[x1-1][y2] - presum_matrix[x2][y1-1] + presum_matrix[x1-1][y1-1]
    print(ans)