Forest density

import sys

def main():
    input_data = sys.stdin.read().split()
    if not input_data:
        return

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

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

    for i in range(n):
        row = input_data[2 + i]
        for j in range(n):
            val = 1 if row[j] == '*' else 0
            pref[i + 1][j + 1] = val + pref[i][j + 1] + pref[i + 1][j] - pref[i][j]

    idx = 2 + n
    out = []

    for _ in range(q):
        y1 = int(input_data[idx])
        x1 = int(input_data[idx + 1])
        y2 = int(input_data[idx + 2])
        x2 = int(input_data[idx + 3])
        
        res = pref[y2][x2] - pref[y1 - 1][x2] - pref[y2][x1 - 1] + pref[y1 - 1][x1 - 1]
        out.append(str(res))
        idx += 4

    sys.stdout.write('\n'.join(out) + '\n')

if __name__ == '__main__':
    main()

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED