1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
| import sys
input = sys.stdin.readline
n,m = list(map(int, input().split()))
table_map = []
for _ in range(n):
table_map.append(list(map(int,input().split())))
sum_map = [[0] * n for _ in range(n)]
for i in range(n):
for j in range(n):
sum_map[i][j] = table_map[i][j]
if i - 1 >= 0:
sum_map[i][j] += sum_map[i-1][j]
if j - 1 >= 0:
sum_map[i][j] += sum_map[i][j-1]
if i - 1 >= 0 and j - 1 >= 0:
sum_map[i][j] -= sum_map[i-1][j-1]
def sum_val(x1,y1,x2,y2):
sum_value = sum_map[x2][y2]
if x1 - 1 >= 0:
sum_value -= sum_map[x1 - 1][y2]
if y1 - 1 >= 0:
sum_value -= sum_map[x2][y1 - 1]
if x1 - 1 >= 0 and y1 - 1 >= 0:
sum_value += sum_map[x1 - 1][y1-1]
return sum_value
for _ in range(m):
x1,y1,x2,y2 = list(map(int, input().split()))
print(sum_val(x1 - 1,y1 - 1,x2 - 1,y2 - 1))
|