Forest density

import sys 


input = sys.stdin.read().split()

n = int(input[0])
q = int(input[1])

p = [([0]*(n+1)) for _ in range(n+1)]

for i in range(1,n+1):
    tmp = input[i+1]
    for j in range(1,n+1): 
        if tmp[j-1] =="*":
            p[i][j] = 1 +p[i-1][j]+ p[i][j-1] - p[i-1][j-1]
        else : 
            p[i][j] = p[i-1][j]+ p[i][j-1] - p[i-1][j-1]

i = 2+n 
for _ in range(q): 
    y1,x1,y2,x2 = int(input[i]), int(input[i+1]), int(input[i+2]), int(input[i+3])
    print(p[y2][x2] - p[y1-1][x2] - p[y2][x1-1] + p[y1-1][x1-1])
    i = i+4

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED