Galileo's latest project involves determining the density of stars in certain regions of the sky. For this purpose he started looking for datasets online, and discovered a dataset on Newton's blog. Newton had decomposed the night sky into a Voronoi tessellation with the generators arranged in a grid. He has stored the number of stars in a Voronoi cell at a position in a matrix that corresponds to the position of the generator in the grid.
This dataset does not directly help Galileo, because he needs to be able to query the number of stars in a rectangular portion of the sky. Galileo tried to write a program that does this on his own, but it turned out to be too slow. Can you help him?

-----Input Format-----
The first line contains two integers n and m that denote the height and width of the matrix respectively. This is followed by  n lines each containing m integers each.
The line following this would contain a single integer t, the number of queries to be run. Each query line consists of 4 integers px, py, qx, qy. The first two integers denote the row and column numbers of the upper left corner of the rectangular region, and the second pair of numbers correspond to the lower right corner.

-----Output Format-----
For each query output a single line containing the number of stars in that rectangular region.

-----Example-----
Input:

3 3
10 10 10
10 10 10
10 10 10
4
1 1 1 1
1 1 3 3
2 1 3 3
3 1 3 3

Output:

10
90
60
30

Difficulty: interview

Starter code:

Solutions:
import sys

def main():
 s=sys.stdin.readline
 n, m = list(map(int, s().split()))
 nums={}
 for i in range(1, n+1):
  nums[i]=list(map(int, s().split()))
 cases=int(s())
 for case in range(cases):
  px, py, qx, qy = list(map(int, s().split()))
  ans=[]
  for i in range(px, qx+1):
   for j in range(py-1, qy):
    ans.append(nums[i][j])
  print(sum(ans))

def __starting_point():
 main()
__starting_point()

arr = {}
temp = input().split(" ")
n = int(temp[0])
m = int(temp[1])
for i in range(n):
 temp1 = input().split(" ")
 for j in range(m):
  arr[i ,j] = int(temp1[j])

t = eval(input())
for k in range(int(t)):
 temp2 = input().split(" ")
 x1 = int(temp2[0])
 y1 = int(temp2[1])
 x2 = int(temp2[2])
 y2 = int(temp2[3])
 total = 0
 for l in range(x1,x2+1):
  for m in range(y1,y2+1):
   total = total + arr[l-1,m-1]
 print(total)


m,n = [int(i) for i in input().split()]
a = []
for i in range (0,m):
 x = [int(j) for j in input().split()]
 a.append (x)

t = int(input())
for ctr in range(0,t):
 sum = 0
 x1, y1, x2, y2 = [int(i)-1 for i in input().split()]
 for i in range(x1, x2+1):
  for j in range(y1,y2+1):
   sum += a[i][j]
 print(sum)


while True:
 try:
  n,m = list(map(int,input().strip().split()))
  matrix = []
  for row in range(n):
   matrix.append(list(map(int,input().strip().split())))
  #for row in matrix: print row
   
  queries = int(input())
  for q in range(queries):
   y1,x1,y2,x2 = list(map(int,input().strip().split()))
   s = 0
   for y in range(y1-1,y2):
    s += sum(matrix[y][x1-1:x2])
   print(s)
 except: break