<p>You are given an <code>m x n</code> binary matrix <code>grid</code> where each cell is either <code>0</code> (empty) or <code>1</code> (occupied).</p>

<p>You are then given stamps of size <code>stampHeight x stampWidth</code>. We want to fit the stamps such that they follow the given <strong>restrictions</strong> and <strong>requirements</strong>:</p>

<ol>
	<li>Cover all the <strong>empty</strong> cells.</li>
	<li>Do not cover any of the <strong>occupied</strong> cells.</li>
	<li>We can put as <strong>many</strong> stamps as we want.</li>
	<li>Stamps can <strong>overlap</strong> with each other.</li>
	<li>Stamps are not allowed to be <strong>rotated</strong>.</li>
	<li>Stamps must stay completely <strong>inside</strong> the grid.</li>
</ol>

<p>Return <code>true</code> <em>if it is possible to fit the stamps while following the given restrictions and requirements. Otherwise, return</em> <code>false</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/11/03/ex1.png" style="width: 180px; height: 237px;" />
<pre>
<strong>Input:</strong> grid = [[1,0,0,0],[1,0,0,0],[1,0,0,0],[1,0,0,0],[1,0,0,0]], stampHeight = 4, stampWidth = 3
<strong>Output:</strong> true
<strong>Explanation:</strong> We have two overlapping stamps (labeled 1 and 2 in the image) that are able to cover all the empty cells.
</pre>

<p><strong class="example">Example 2:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/11/03/ex2.png" style="width: 170px; height: 179px;" />
<pre>
<strong>Input:</strong> grid = [[1,0,0,0],[0,1,0,0],[0,0,1,0],[0,0,0,1]], stampHeight = 2, stampWidth = 2 
<strong>Output:</strong> false 
<strong>Explanation:</strong> There is no way to fit the stamps onto all the empty cells without the stamps going outside the grid.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>m == grid.length</code></li>
	<li><code>n == grid[r].length</code></li>
	<li><code>1 &lt;= m, n &lt;= 10<sup>5</sup></code></li>
	<li><code>1 &lt;= m * n &lt;= 2 * 10<sup>5</sup></code></li>
	<li><code>grid[r][c]</code> is either <code>0</code> or <code>1</code>.</li>
	<li><code>1 &lt;= stampHeight, stampWidth &lt;= 10<sup>5</sup></code></li>
</ul>

class RegionSum():
    def __init__(self, matrix):
        n = len(matrix)
        m = len(matrix[0])
        self.prefix = [[0] * (m + 1) for i in range(n + 1)]
        # for i in range(n):
        #    self.prefix[i][0] = self.prefix[i-1][0] + self.matrix[i][0]

        # for j in range(m):
        #    self.prefix[0][m] = self.prefix[0][m-1] + self.matrix[0][j]

        for i in range(n):
            for j in range(m):
                a = self.prefix[i-1][j-1]
                b = self.prefix[i-1][j]
                c = self.prefix[i][j-1]
                self.prefix[i][j] = b+c-a+ matrix[i][j]

    def query(self, i, j, x, y):
        a = self.prefix[i-1][j-1]
        b = self.prefix[x][j-1]
        c = self.prefix[i-1][y]
        d = self.prefix[x][y]
        return d - b - c + a
                
class Solution:
    def possibleToStamp(self, grid: List[List[int]], stampHeight: int, stampWidth: int) -> bool:
        n = len(grid)
        m = len(grid[0])
        stamps = [[0] * m for i in range(n)]
        board = RegionSum(grid)
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                x = i + stampHeight - 1
                y = j + stampWidth - 1
                if x >= len(grid) or y >= len(grid[0]):
                    continue
                if board.query(i, j, x, y) == 0:
                    stamps[x][y] = 1

        board = RegionSum(stamps)
        for i in range(n):
            for j in range(m):
                if grid[i][j] == 1:
                    continue
                x = min(n-1, i + stampHeight - 1)
                y = min(m-1, j + stampWidth - 1)
                if board.query(i, j, x, y) == 0:
                    return False

        return True
59500