gold_mines_cummulative.py

import array
import sys

MIL = 10**6

def running_sum(a):
    tot = 0
    for item in a:
        i = int(item)
        if i < 0 or i > MIL:
            sys.exit(-1)
        tot += i
        yield tot

def find_gold(x1, y1, x2, y2):
    s = 0
    for x in xrange(x1-1, x2):
        s+=arr[x][y2-1] - (0 if y1-2 < 0 else arr[x][y1-2])
    return s
 
R, C = map(int, sys.stdin.readline().split())

arr = []
 
if 1 <= R and R <= 1000 and 1 <= C and C <= 1000:
    can_i = True
    for row in xrange(R):
        stritems = sys.stdin.readline().split()
        if len(stritems) > C:
            can_i = False
            break
        arr.append(list(running_sum(stritems)))
 
    if can_i:
        no_of_runs = long(sys.stdin.readline())
        #print "zZZZ", arr
        for run in xrange(no_of_runs):
            run_params = map(int, sys.stdin.readline().split())
            if len(run_params) != 4:
            	break

            x1, y1, x2, y2 = run_params
            if 1 <= x1 and x1 <= x2 and x2 <= R and 1 <= y1 and y2 <= y2 and y2 <= C:
                print find_gold(x1, y1, x2, y2)
            else:
                break