Forest density

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

forest = []

for _ in range(n):
    row = list(input().split())[0]
    forest.append([int(c=='*') for c in row])

prefix_sum_array = [[0 for _ in range(n+1)]]
for i in range(1, n+1):
    prefix_sum = [0 for _ in range(n+1)]
    sum_val = 0
    for j in range(1, n+1):
        sum_val += forest[i-1][j-1]
        prefix_sum[j] = prefix_sum_array[i-1][j] + sum_val
    prefix_sum_array.append(prefix_sum)

solution = []

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

for elt in solution:
    print(elt)

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED