Forest density

n,q = [int(x) for x in input().split()]


tab = [[0 for i in range(n+1)]]
for i in range (1,n+1):
    L = input()
    tab.append([0])
    for ind,x in enumerate(L):
        
        index = ind+1
        if x == '.':
            tab[i].append(tab[i][index-1]+tab[i-1][index]-tab[i-1][index-1])
        else :
            tab[i].append(tab[i][index-1]+tab[i-1][index]-tab[i-1][index-1]+1)


for _ in range (q):
    y1,x1,y2,x2 = [int(x) for x in input().split()]
    #print(tab[y2][x2],tab[y2][x1-1],tab[y1-1][x2],tab[y1-1][x1-1])
    print(tab[y2][x2]-tab[y2][x1-1]-tab[y1-1][x2]+tab[y1-1][x1-1])

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED