Forest density

import sys

input = sys.stdin.readline

class PrefixSum2D:
    def __init__(self, grid):
        r = len(grid)
        c = len(grid[0]) if r else 0
        self.p = [[0] * (c + 1) for _ in range(r + 1)]
        for i in range(r):
            for j in range(c):
                self.p[i + 1][j + 1] = (
                    grid[i][j]
                    + self.p[i][j + 1]
                    + self.p[i + 1][j]
                    - self.p[i][j]
                )

    def sum_rect(self, r1, c1, r2, c2):
        """Inclusive rectangle from (r1, c1) to (r2, c2)."""
        return (
            self.p[r2 + 1][c2 + 1]
            - self.p[r1][c2 + 1]
            - self.p[r2 + 1][c1]
            + self.p[r1][c1]
        )

def main():
    n, q = map(int, input().split())

    grid = [[0]*n]*n
    print(grid)

    for j in range(n):
        line = input()
        insert = [0]*n
        i = 0
        for emo in line:
            if emo == '*':
                insert[i] = 1
                print('yes')
            i += 1
        print(insert)
        grid[j] = insert
        print(grid)

    prefix = PrefixSum2D(grid)

    out = []

    for _ in range(q):
        a1, a2, b1, b2 = map(int, input().split())
        out.append(str(prefix.sum_rect(a1 - 1, a2 -1, b1 - 1, b2 -1)))

    sys.stdout.write("\n".join(out) + ("\n" if out else ""))


if __name__ == "__main__":
    main()

Test 1

Verdict: WRONG ANSWER

Test 2

Verdict: OUTPUT LIMIT EXCEEDED

Test 3

Verdict: OUTPUT LIMIT EXCEEDED