Forest density

# cook your dish here
n, q = map(int, input().split())
k = [ [0]* (n + 1)]

h = [[0] * (n + 1) for i in range(n + 1)]

for i in range(1, n+1):
    row = input().strip()
    for j in range(1, n+1):
        if row[j-1] == '*':
            c = 1
        else:
            c = 0
        h[i][j] = h[i-1][j] + h[i][j-1] - h[i-1][j-1] + c
        

for i in range(q):
    y1,x1, y2,x2 = map(int, input().split())
    
    s = h[y2][x2] - h[y1-1][x2] - h[y2][x1-1] + h[y1-1][x1-1]
    print(s)
    
    

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED