Given a m * n matrix mat and an integer K, return a matrix answer where each answer[i][j] is the sum of all elements mat[r][c] for i - K <= r <= i + K, j - K <= c <= j + K, and (r, c) is a valid position in the matrix.
 
Example 1:
Input: mat = [[1,2,3],[4,5,6],[7,8,9]], K = 1
Output: [[12,21,16],[27,45,33],[24,39,28]]

Example 2:
Input: mat = [[1,2,3],[4,5,6],[7,8,9]], K = 2
Output: [[45,45,45],[45,45,45],[45,45,45]]

 
Constraints:

m == mat.length
n == mat[i].length
1 <= m, n, K <= 100
1 <= mat[i][j] <= 100

Difficulty: interview

Starter code:

class Solution:
    def matrixBlockSum(self, mat: List[List[int]], K: int) -> List[List[int]]:
        

Solutions:
class Solution:
    def matrixBlockSum(self, mat: List[List[int]], K: int) -> List[List[int]]:
        \"\"\"
        Brute force solution is to perform the sum for each position
        (r, c). This would require K * K operations for each of m * n positions.
        
        Instead, assuming we compute sums left to right and top down, we can
        use our previous solution to calculate the next one, subtracting the
        sums that fell out of the window and adding the sums that are in.
        
        Pseudo code would be something like this:
        
        prevBlockSum = ...
        for r in range(m):
            for c in range(n):
                if c - K > 0:
                    prevBlockSum -= sum()
        \"\"\"
        m = len(mat)
        n = len(mat[0])
        
        cum = []
        prevSums = [0] * n
        for r in range(m):
            rowSum = 0
            cumSums = []
            for c in range(n):
                rowSum += mat[r][c]
                cumSums.append(prevSums[c] + rowSum)
            cum.append(cumSums)
            prevSums = cumSums
        
        out = []
        for i in range(m):
            blockSums = []
            for j in range(n):
                r = i + K if i + K < m else m - 1
                c = j + K if j + K < n else n - 1
                
                blockSum = cum[r][c]
                if i - K > 0:
                    blockSum -= cum[i-K-1][c]
                if j - K > 0:
                    blockSum -= cum[r][j-K-1]
                if i - K > 0 and j - K > 0:
                    blockSum += cum[i-K-1][j-K-1]
                blockSums.append(blockSum)
            out.append(blockSums)
        
        return out

class Solution:
    def matrixBlockSum(self, mat: List[List[int]], K: int) -> List[List[int]]:
        m, n = len(mat), len(mat[0])        
        mat[:] = [[0] * (n + 1)] + [[0] + row for row in mat]
        res = [[0 for _ in range(n)] for _ in range(m)]
        
        # cum sum 
        for i in range(1, m+1):
            for j in range(1, n+1):
                mat[i][j] += mat[i-1][j] + mat[i][j-1] - mat[i-1][j-1]
        
        # compute sums
        for i in range(m):
            for j in range(n):
                r1, c1 = max(i-K, 0), max(j-K, 0)
                r2, c2 = min(i+K+1, m), min(j+K+1, n)
                res[i][j] = mat[r2][c2] - mat[r1][c2] - mat[r2][c1] + mat[r1][c1]
        
        return res
                    
                    
        
                        


class Solution:
    def matrixBlockSum(self, mat: List[List[int]], K: int) -> List[List[int]]:
        n, m = len(mat), len(mat[0])
        k = K
        range_sum = [[0] * m for _ in range(n)]
        for i in range(n):
            for j in range(m):
                top_left = range_sum[i-1][j-1] if j-1 >= 0 and i-1 >= 0 else 0
                top = range_sum[i-1][j] if i-1 >=0 else 0
                left = range_sum[i][j-1] if j-1>=0 else 0
                range_sum[i][j] = top + left - top_left + mat[i][j]
        print(range_sum)
        dp = [[0] * m for _ in range(n)]
        for i in range(n):
            for j in range(m):
                # right_buttom point
                col = min(m-1, j+k)
                row = min(n-1, i+k)
                print([row, col])
                dp[i][j] = (range_sum[row][col]
                           + (range_sum[i-k-1][j-k-1] if i-k-1>=0 and j-k-1>=0 else 0)
                           - (range_sum[row][j-k-1] if j-k-1>=0 else 0)
                           - (range_sum[i-k-1][col] if i-k-1>=0 else 0))
        return dp

class Solution:
    def matrixBlockSum(self, mat: List[List[int]], K: int) -> List[List[int]]:
        m = len(mat)
        n = len(mat[0])
        
        answer = [[0]*n for _ in range(m)]
        dp = [[0]*n for _ in range(m)]
        
        for i in range(m):
            for j in range(n):
                if j == 0:
                    dp[i][j] = mat[i][j]
                else:
                    dp[i][j] = dp[i][j-1] + mat[i][j]
        
        for i in range(m):
            for j in range(n):
                for x in range(i-K, i+K+1):
                    if x >= 0 and x < m:
                        if j-K <=0:
                            if j+K >= n:
                                answer[i][j] += dp[x][-1]
                            else:
                                answer[i][j] += dp[x][j+K]
                        elif j-K <= n:
                            if j+K >= n:
                                answer[i][j] += dp[x][-1] - dp[x][j-K-1]
                            else:
                                answer[i][j] += dp[x][j+K] - dp[x][j-K-1]
                            
        return answer


class Solution:
    def matrixBlockSum(self, mat: List[List[int]], K: int) -> List[List[int]]:
        m, n = len(mat), len(mat[0])
        def get_sum(i, j):
            ssum = 0
            for a in range(-K, K+1):
                for b in range(-K, K+1):
                    ssum += mat[i+a][j+b] if (0<=(i+a)<m and 0<=(j+b)<n) else 0 
            return ssum
        
        res = [[0 for _ in range(n)] for _ in range(m)]

        for i in range(m):
            for j in range(n):
                if i==0 and j==0:
                    res[i][j] = get_sum(0, 0)
                else:
                    if i == 0:
                        # reuse the result from left cell
                        res[i][j] = res[i][j-1] - sum([mat[b][j-K-1] if (0<=(j-K-1)<n and 0<=b<m) else 0 for b in range(i-K, i+K+1)]) + sum([mat[b][j+K] if (0<=(j+K)<n and 0<=b<m) else 0 for b in range(i-K, i+K+1)])
                    else:
                        # reuse the result from top cell
                        res[i][j] = res[i-1][j] - sum([mat[i-K-1][b] if (0<=(i-K-1)<m and 0<=b<n) else 0 for b in range(j-K, j+K+1)]) + sum([mat[i+K][b] if (0<=(i+K)<m and 0<=b<n) else 0 for b in range(j-K, j+K+1)])
                        
        return res
                        


class Solution:
    def matrixBlockSum(self, mat: List[List[int]], K: int) -> List[List[int]]:
        
        def calc(mat, area):
            (a, b), (c, d) = area
            return sum([sum(row[b:d+1])for row in mat[a:c+1]])
        
        m = len(mat)-1
        n = len(mat[0])-1
        row = []
        lookup = {}
        for i, r in enumerate(mat):
            col = []
            for j, c in enumerate(mat[0]):
                area = (0 if i-K < 0 else i-K, 0 if j-K < 0 else j-K), (m if i+K > m else i+K, n if j+K > n else j+K)
                key = str(area)
                if key not in lookup:
                    lookup[key] = calc(mat, area)
                col += [lookup[key]]
            row += [col]
        return row

class Solution:
    def matrixBlockSum(self, A: List[List[int]], K: int) -> List[List[int]]:
      m, n = len(A), len(A[0])
      def force_inside(ra, rb, ca, cb):
        return max(0, ra), min(m, rb), max(0, ca), min(n, cb)

      def rect(i, j):
        return force_inside(i-K, i+K+1, j-K, j+K+1)

      def sum_rect(ra, rb, ca, cb):
        ra, rb, ca, cb = force_inside(ra, rb, ca, cb)
        s = 0
        for p in range(ra,rb):
          for q in range(ca, cb):
            s += A[p][q]
        return s

      S = [[0 for j in range(n)] for i in range(m)]
      for i in range(m):
        for j in range(n):
          ra, rb, ca, cb = rect(i,j)
          if i == 0 and j == 0:
            S[i][j] = sum_rect(ra, rb, ca, cb)
          else:
            if j == 0:
              i0, j0 = i-1, 0
            else:
              i0, j0 = i, j-1
            ra0, rb0, ca0, cb0 = rect(i0,j0)
            S[i][j] = S[i0][j0]
            S[i][j] -= sum_rect(ra0, ra, ca, cb)
            S[i][j] -= sum_rect(ra, rb, ca0, ca)
            S[i][j] += sum_rect(rb0, rb, ca, cb)
            S[i][j] += sum_rect(ra, rb, cb0, cb)
      return S

class Solution:
    def matrixBlockSum(self, mat: List[List[int]], K: int) -> List[List[int]]:
        
        rows = collections.defaultdict(list)
        
        for i,row in enumerate(mat):
            s = 0
            for v in row:
                s+=v
                rows[i].append(s)
        # print(rows)
            
        m,n = len(mat), len(mat[0])
        ans = [ [0]*n for _ in range(m) ]
        for i in range(m):
            for j in range(n):
                ind = [max(0,j-K), min(n-1,j+K)]
                
                # print((i,j),(max(0,i-K), min(m,i+K+1)),ind)
                for k in range(max(0,i-K), min(m,i+K+1)):
                    sum = rows[k][ind[1]]
                    if ind[0]>0: sum = rows[k][ind[1]]- rows[k][ind[0]-1]
                    
                    # print((k,ind),sum)
                    ans[i][j]+=sum
                # print('--------------------')
        return ans

class Solution:
    def matrixBlockSum(self, mat: List[List[int]], K: int) -> List[List[int]]:
        def calc(mat, area):
            (a, b), (c, d) = area
            return sum([sum(row[b:d+1])for row in mat[a:c+1]])
        
        m = len(mat)-1
        n = len(mat[0])-1
        row = []
        lookup = {}
        for i, r in enumerate(mat):
            col = []
            for j, c in enumerate(mat[0]):
                
                # make sure to have out-of-boundary case
                area = (0 if i-K < 0 else i-K, 0 if j-K < 0 else j-K), \\
                        (m if i+K > m else i+K, n if j+K > n else j+K)
                
                key = str(area)
                if key not in lookup:
                    lookup[key] = calc(mat, area)
                col += [lookup[key]]
            row += [col]
        return row

class Solution:
    def matrixBlockSum(self, mat: List[List[int]], K: int) -> List[List[int]]:
        
        def calc(mat, area):
            (a, b), (c, d) = area
            return sum([sum(row[b:d+1])for row in mat[a:c+1]])
        
        m = len(mat)-1
        n = len(mat[0])-1
        row = []
        lookup = {}
        for i, r in enumerate(mat):
            col = []
            for j, c in enumerate(mat[0]):
                
                # make sure to have out-of-boundary case
                area = (0 if i-K < 0 else i-K, 0 if j-K < 0 else j-K), (m if i+K > m else i+K, n if j+K > n else j+K)
                
                key = str(area)
                if key not in lookup:
                    lookup[key] = calc(mat, area)
                col += [lookup[key]]
            row += [col]
        return row

from scipy import signal, ndimage
import numpy as np

class Solution:
    def matrixBlockSum(self, mat: List[List[int]], K: int) -> List[List[int]]:
        N = 2*K + 1
        return signal.convolve2d(mat, np.ones((N,N)), mode='same').astype(int)
        


class Solution:
    def matrixBlockSum(self, mat: List[List[int]], K: int) -> List[List[int]]:
        
        def calc(mat, area):
            (a, b), (c, d) = area
            return sum([sum(row[b:d+1])for row in mat[a:c+1]])
        
        m = len(mat)-1
        n = len(mat[0])-1
        row = []
        lookup = {}
        for i, r in enumerate(mat):
            col = []
            for j, c in enumerate(mat[0]):
                
                # make sure to have out-of-boundary case
                area = (0 if i-K < 0 else i-K, 0 if j-K < 0 else j-K), (m if i+K > m else i+K, n if j+K > n else j+K)
                
                key = str(area)
                if key not in lookup:
                    lookup[key] = calc(mat, area)
                col += [lookup[key]]
            row += [col]
        return row


from scipy import signal
import numpy as np

class Solution:
    def matrixBlockSum(self, mat: List[List[int]], K: int) -> List[List[int]]:
        N = 2*K + 1
        return signal.convolve2d(mat, np.ones((N,N)), mode='same').astype(int)
        


# class Solution:
#     def matrixBlockSum(self, mat: List[List[int]], K: int) -> List[List[int]]:
        
#         row = len(mat)
#         col = len(mat[0])
        
#         answer = [[0 for i in range(col)] for j in range(row)]
        
#         for i in range(row):
#             for j in range(1,col):
#                 # answer[i][j] = self.new_matrix(mat,i,j,K,row,col)
#                 mat[i][j] = mat[i][j-1]+mat[i][j]
#         print(mat)
        
#         for i in range(row):
#             for j in range(col):
#                 answer[i][j] = self.new_matrix(mat,i,j,K,row,col)
#         return answer
                
#     def new_matrix(self,mat,i,j,k,row,col):
#         ans = 0 
#         new_row_low = i-k
#         new_row_high = i + k
#         new_col_low = j-k
#         new_col_high = j+k
        
        
#         while(new_row_low < 0):
#             new_row_low +=1
#         while(new_row_high > row-1):
#             new_row_high -=1
#         while(new_col_low < 0):
#             new_col_low +=1
#         while(new_col_high > col-1):
#             new_col_high-=1
        
        
        
#         for a in range(new_row_low, new_row_high+1):
            
#             ans+= mat[a][new_col_high]
            
#             if(new_col_low-1 >= 0):
                
#                 ans -= mat[a][new_col_low-1]
                
#         return ans
                    
            
        
class Solution:
    def matrixBlockSum(self, mat: List[List[int]], K: int) -> List[List[int]]:
        blockSum = [[0] * len(mat[0]) for _ in range(len(mat))]
        
        accumSum = [[0] * (len(mat[0]) + 1) for _ in range(len(mat) + 1)]
        for x in range(len(mat)):
            for y in range(len(mat[0])):
                accumSum[x + 1][y + 1] = (accumSum[x][y + 1] if x >= 0 else 0) + (accumSum[x + 1][y] if y >= 0 else 0) - (accumSum[x][y] if x >= 0 and y >= 0 else 0) + mat[x][y]
                
        for x in range(len(mat)):
            for y in range(len(mat[0])):
                blockSum[x][y] = accumSum[max(x - K, 0)][max(y - K, 0)] + accumSum[min(x + K + 1, len(mat))][min(y + K + 1, len(mat[0]))] - accumSum[max(x - K, 0)][min(y + K + 1, len(mat[0]))] - accumSum[min(x + K + 1, len(mat))][max(y - K, 0)]
        
        return blockSum        
        


class Solution:
    def matrixBlockSum(self, mat: List[List[int]], k: int) -> List[List[int]]:
        m = len(mat)
        n = len(mat[0])
        p = []
        for i in range(m):
            row = [0]
            s = 0
            for j in range(n):
                s += mat[i][j]
                row.append(s)
            p.append(row)
        
        ans = []
        for i in range(m):
            row = []
            for j in range(n):
                s = 0
                top = max(0, i - k)
                bottom = min(m, i + k + 1)
                for g in range(top, bottom):
                    left = max(0, j - k)
                    right = min(n, j + k + 1)
                    s += p[g][right] - p[g][left]
                row.append(s)
            ans.append(row)
        return ans


# # Brute Force: TLE
# def matrixBlockSum(self, mat: List[List[int]], K: int) -> List[List[int]]:
#     m, n = len(mat), len(mat[0])
#     ans = [[0 for _ in range(n)] for _ in range(m)]
#     for i in range(m):
#         for j in range(n):
#             res = 0
#             for block_row in range(max(0, i-K), min(m, i+K+1)):
#                 for block_col in range(max(0, j-K), min(n, j+K+1)):
#                     res += mat[block_row][block_col]
#             ans[i][j] = res                                           
#     return ans    

class Solution:
    def matrixBlockSum(self, mat: List[List[int]], K: int) -> List[List[int]]:
        m, n = len(mat), len(mat[0])
        ans = [[0 for _ in range(n)] for _ in range(m)]
        
        # Convert mat to accumulate sum for each row
        for i in range(m):
            for j in range(1, n):
                mat[i][j] += mat[i][j-1]
        
        for i in range(m):
            for j in range(n):
                res = 0
                for block_row in range(max(0, i-K), min(m, i+K+1)):
                    res += mat[block_row][min(n-1, j+K)]
                    if j - K - 1 >= 0:
                        res -= mat[block_row][j-K-1]
                ans[i][j] = res                                           
        return ans        

class Solution:
    def matrixBlockSum(self, mat: List[List[int]], K: int) -> List[List[int]]:
        acc = [[0] + list(accumulate(m)) for m in mat]
        print(acc)
        m, n = len(mat), len(mat[0])
        ans = [[0] * n for _ in range(m)]
        for i in range(m):
            for j in range(n):
                for k in range(max(i - K, 0), min(i + K, m - 1) + 1):
                    l, r = max(j - K, 0), min(j + K, n - 1)
                    ans[i][j] += acc[k][r + 1] - acc[k][l]
        return ans


class Solution:
    def matrixBlockSum(self, mat: List[List[int]], K: int) -> List[List[int]]:
        # the last index of rows
        m = len(mat) - 1
        # the last index of columns
        n = len(mat[0]) - 1
        row = []
        lookup = {}
        for i, r in enumerate(mat):
            col = []
            for j, c in enumerate(mat[0]):
                area = (0 if i-K<0 else i-K, 0 if j-K<0 else j-K), (m if i+K>m else i+K, n if j+K>n else j+K)
                key = str(area)
                if key not in lookup:
                    lookup[key] = self.matrixBlockSumHelp(mat, area)
                col += [lookup[key]]
            row += [col]
            
        return row
    
    def matrixBlockSumHelp(self, mat, area):
        (a, b), (c, d) = area
        return sum([sum(row[b:d+1]) for row in mat[a:c+1]])

class Solution:
    def matrixBlockSum(self, mat: List[List[int]], K: int) -> List[List[int]]:
        
        # mat2 = mat[:]   # can not 2-d matrix
        mat2 = copy.deepcopy(mat)
        
        def help(i,j, K):
            res = 0
            for ii in range(i-K, i+K+1):
                for jj in range(j-K, j+K+1):
                    if 0<=ii<len(mat) and 0<=jj<len(mat[0]):
                        res += mat[ii][jj]
            return res
        
        for i in range(len(mat)):
            for j in range(len(mat[0])):
                # print(mat)
                if j == 0:
                    mat2[i][j] = help(i,j, K)
                else:
                    mat2[i][j] = mat2[i][j-1]
                    if j+K<len(mat[0]):
                        for ii in range(i-K, i+K+1):
                            if 0<=ii<len(mat):
                                mat2[i][j] += mat[ii][j+K]
                    if j-K-1>=0:
                        for ii in range(i-K, i+K+1):
                            if 0<=ii<len(mat):
                                mat2[i][j] -= mat[ii][j-K-1]
                    
        return mat2


from itertools import accumulate 
class Solution:
    def matrixBlockSum(self, mat: List[List[int]], K: int) -> List[List[int]]:
        A = mat.copy()
        for i in range(len(A)):
            A[i] = [0]+list(accumulate(A[i]))
        Ans = [[0 for i in range(len(A[0]))] for j in range(len(A))] 
        for i in range(len(A)):
            for j in range(1,len(A[0])):
                #print(max(0,i-K),min(len(A),i+K))
                for p in range(max(0,i-K),min(len(A)-1,i+K)+1):
                    #print(A[p],p)
                    #print(min(j+K,len(A[0])),max(0,j-K))
                    Ans[i][j] += A[p][min(j+K,len(A[0])-1)]-A[p][max(0,j-K-1)]
        for i in range(len(Ans)):
            Ans[i] = Ans[i][1:]
        return Ans    
                
        


from itertools import accumulate 
class Solution:
    def matrixBlockSum(self, mat: List[List[int]], K: int) -> List[List[int]]:
        A = mat.copy()
        for i in range(len(A)):
            A[i] = [0]+list(accumulate(A[i]))
        Ans = [[0 for i in range(len(A[0]))] for j in range(len(A))] 
        for i in range(len(A)):
            for j in range(1,len(A[0])):
                for p in range(max(0,i-K),min(len(A)-1,i+K)+1):
                    Ans[i][j] += A[p][min(j+K,len(A[0])-1)]-A[p][max(0,j-K-1)]
        for i in range(len(Ans)):
            Ans[i] = Ans[i][1:]
        return Ans    
                
        


class Solution:
    def matrixBlockSum(self, mat: List[List[int]], k: int) -> List[List[int]]:
        m,n = len(mat), len(mat[0])
        ans = [[0]*n for i in range(m)]
        prefix = [[0]*(n+1) for i in range(m)]
        for i in range(m):
            for j in range(n):
                prefix[i][j] = prefix[i][j-1] + mat[i][j]

        for i in range(m):
            for j in range(n):
                for s in range(k+1):
                    if i-s < 0: break
                    ans[i][j] += prefix[i-s][min(n-1,j+k)]-prefix[i-s][max(-1,j-k-1)]
                for s in range(1,k+1):
                    if i+s > m-1: break
                    ans[i][j] += prefix[i+s][min(n-1,j+k)]-prefix[i+s][max(-1,j-k-1)]
        return ans 

class Solution:
    def matrixBlockSum(self, mat: List[List[int]], k: int) -> List[List[int]]:
            m,n = len(mat), len(mat[0])
            ans = [[0]*n for i in range(m)]
            prefix = [[0]*(n+1) for i in range(m)]
            for i in range(m):
                for j in range(n):
                    prefix[i][j] = prefix[i][j-1] + mat[i][j]

            for i in range(m):
                for j in range(n):
                    for s in range(k+1):
                        if i-s < 0: break
                        ans[i][j] += prefix[i-s][min(n-1,j+k)]-prefix[i-s][max(-1,j-k-1)]
                    for s in range(1,k+1):
                        if i+s > m-1: break
                        ans[i][j] += prefix[i+s][min(n-1,j+k)]-prefix[i+s][max(-1,j-k-1)]
            return ans 

import numpy as np


class Solution:
    
    def matrixBlockSum(self, mat, k):
        p = 2*k + 1
        m, n = len(mat), len(mat[0])
        array = np.zeros((m + p, n + p), dtype=np.uint32)
        array[k+1:-k,k+1:-k] = mat
        np.cumsum(array, axis=0, out=array)
        np.cumsum(array, axis=1, out=array)
        return array[p:,p:] - array[p:,:-p] - array[:-p,p:] + array[:-p,:-p]



class Solution:
    def matrixBlockSum(self, mat: List[List[int]], K: int) -> List[List[int]]:
        if not mat: return []
        
        m = len(mat)
        n = len(mat[0])
        
        get = lambda i, j: mat[i][j] if 0 <= i < m and 0 <= j < n else 0
        row = lambda i, j: sum([get(i, y) for y in range(j - K, j + K + 1)])
        col = lambda i, j: sum([get(x, j) for x in range(i - K, i + K + 1)])
        

        answer = [[0] * n for _ in range(m)]
        
        for i in range(0, K + 1):
            for j in range(0, K + 1):
                answer[0][0] += get(i, j)

        for i in range(m):
            for j in range(n):
                if i == 0 and j == 0: continue
                if j == 0:
                    answer[i][j] = answer[i - 1][j] - row(i - K - 1, j) + row(i + K, j)
                else:
                    answer[i][j] = answer[i][j - 1] - col(i, j - K - 1) + col(i, j + K)
                
        return answer


import numpy as np
import scipy.signal
#convolve2d as convolv

class Solution:
    def matrixBlockSum(self, mat: List[List[int]], K: int) -> List[List[int]]:
        mat = np.array(mat)
        return scipy.signal.convolve2d(mat, np.ones((2*K +1, 2*K + 1)), mode=\"same\").astype('int')
        

class Solution:
    def matrixBlockSum(self, mat: List[List[int]], K: int) -> List[List[int]]:
        n = len(mat)
        m = len(mat[0])
        answer = [[0] * m for i in range(n)]
      
        maxo = max
        sumo = sum
        for i in range(n):
            for j in range(m):
                r = maxo(0, i-K)           
                sum1 = 0
                while r <= i+K and r < n:
                    
                    if j-K < 0:
                        if j+K < m:
                            sum1 += sumo(mat[r][:j+K+1])
                        else:
                            sum1 += sumo(mat[r])
                    else:
                        if j+K < m:
                            sum1 += sumo(mat[r][j-K:j+K+1])
                        else:
                            sum1 += sumo(mat[r][j-K:])
                        
                    r += 1
                answer[i][j] = sum1
            
        return answer

class Solution:
    def matrixBlockSum(self, mat: List[List[int]], K: int) -> List[List[int]]:
        n = len(mat)
        m = len(mat[0])
        answer = [[0] * m for i in range(n)]
        r = 0
        c = 0
        maxo = max
        sumo = sum
        for i in range(n):
            for j in range(m):
                r = maxo(0, i-K)           
                sum1 = 0
                while r <= i+K and r < n:
                    if j-K < 0:
                        if j+K < m:
                            sum1 += sumo(mat[r][:j+K+1])
                        else:
                            sum1 += sumo(mat[r])
                    else:
                        if j+K < m:
                            sum1 += sumo(mat[r][j-K:j+K+1])
                        else:
                            sum1 += sumo(mat[r][j-K:])
                        
                    r += 1
                answer[i][j] = sum1
            
        return answer

class Solution:
    def matrixBlockSum(self, mat: List[List[int]], K: int) -> List[List[int]]:
        n = len(mat)
        m = len(mat[0])
        answer = [[0] * m for i in range(n)]
        r = 0
        c = 0
        
        for i in range(n):
            tmp = []
            for j in range(m):
                if i - K < 0:
                    r = 0
                else:
                    r = i-K
                
                sum1 = 0
                while r <= i+K and r < n:
                    if j-K < 0:
                        if j+K < m:
                            sum1 += sum(mat[r][:j+K+1])
                        else:
                            sum1 += sum(mat[r])
                    else:
                        if j+K < m:
                            sum1 += sum(mat[r][j-K:j+K+1])
                        else:
                            sum1 += sum(mat[r][j-K:])
                        
                    r += 1
                answer[i][j] = sum1
            
        return answer

class Solution:
    def sumHelper(self, mat: List[List[int]], rowLow: int, rowHigh: int, colLow: int, colHigh: int) -> int:
        res = sum(sum(row[colLow:colHigh+1]) for row in mat[rowLow:rowHigh + 1])
        return res
    
    def matrixBlockSum(self, mat: List[List[int]], K: int) -> List[List[int]]:
        rows = len(mat)
        cols = len(mat[0])
        res = [[0 for c in range(cols)] for r in range(rows)]
        
        for r in range(rows):
            for c in range(cols):
                lowR = r - K
                if (lowR < 0): lowR = 0
                highR = r + K
                if (highR >= rows): highR = rows - 1
                    
                lowC = c - K
                if (lowC < 0): lowC = 0
                highC = c + K
                if (highC >= cols): highC = cols - 1
        
                res[r][c] = self.sumHelper(mat, lowR, highR, lowC, highC)
        
        return res

class Solution:
    def matrixBlockSum(self, mat: List[List[int]], K: int) -> List[List[int]]:
        answer = [[0 for j in i] for i in mat]
        def calc(mat,a,b,c,d):
            return sum([sum(row[b:d+1])for row in mat[a:c+1]])
        for i in range(len(mat)):
            for j in range(len(mat[0])):
                a = i-K if i-K>=0 else 0
                b = j-K if j-K>=0 else 0
                c = i+K if i+K<=len(mat) else len(mat)
                d = j+K if j+K<=len(mat[0]) else len(mat[0])
                answer[i][j]=calc(mat,a,b,c,d)
        return answer

class Solution:
    def matrixBlockSum(self, mat: List[List[int]], K: int) -> List[List[int]]:
        m, n = len(mat[0]), len(mat)
        dp = [[0]*m for _ in range(n)]
        for i in range(n):
            for j in range(m):
                dp[i][j] = sum(sum(mat[col][max(0,j-K):j+K+1]) for col in
                               range(max(0,i-K),min(i+K+1,n)))
        return dp
        


class Solution:
    def matrixBlockSum(self, mat: List[List[int]], K: int) -> List[List[int]]:
        
        def matsum(mat, x1, y1, x2, y2):
            sumi = 0
            #print(x1, y1, x2, y2)
            for row in mat[x1:x2+1]:
                #print(row)
                sumi += sum(row[y1:y2+1])
                #print(sumi)
            return sumi
        
        newmat = [[0]*len(row) for row in mat]
        for ri, row in enumerate(mat):
            
            for ci, i in enumerate(row):
                #print(ri, ci)
                newmat[ri][ci] = matsum(mat, max(0, ri-K), max(0, ci-K), min(len(mat)-1, ri+K), min(len(row)-1, ci+K))
        return newmat


class Solution:
    def prefix(self, d, i, j):
        if i<0 or j<0:
            return 0
        if i>=len(d):
            i = len(d)-1
        if j>=len(d[0]):
            j = len(d[0])-1
        return d[i][j]
            
    def matrixBlockSum(self, mat: List[List[int]], k: int) -> List[List[int]]:
        d = mat
        row = len(mat)
        col = len(mat[0])
        for i in range(row):
            for j in range(col):
                d[i][j]+=self.prefix(d, i-1,j) + self.prefix(d, i,j-1) - self.prefix(d, i-1,j-1)
        res = [[0]*col for _ in range(row)]
        for i in range(row):
            for j in range(col):
                res[i][j] = self.prefix(d, i+k, j+k) \\
                            - self.prefix(d, i+k, j-k-1) \\
                            - self.prefix(d, i-k-1, j+k) \\
                            + self.prefix(d, i-k-1, j-k-1)
                            
        return res
        

class Solution:
    def matrixBlockSum(self, mat: List[List[int]], K: int) -> List[List[int]]:
        answer = []
        r = 0
        c = 0
        
        for i in range(len(mat)):
            tmp = []
            for j in range(len(mat[0])):
                if i - K < 0:
                    r = 0
                else:
                    r = i-K
                
                sum1 = 0
                while r <= i+K and r < len(mat):
                    if j-K < 0:
                        if j+K < len(mat[0]):
                            sum1 += sum(mat[r][:j+K+1])
                        else:
                            sum1 += sum(mat[r])
                    else:
                        if j+K < len(mat[0]):
                            sum1 += sum(mat[r][j-K:j+K+1])
                        else:
                            sum1 += sum(mat[r][j-K:])
                        
                    r += 1
                tmp.append(sum1)
            answer.append(tmp)
        return answer

class Solution:
    def matrixBlockSum(self, mat: List[List[int]], K: int) -> List[List[int]]:
        def sumMatrix(center: tuple):
            Sum = 0
            
            start_i = max(center[0] - K, 0)
            stop_i = min(center[0] + K + 1, len(mat[0]))
            
            start_j = max(center[1] - K, 0)
            stop_j = min(center[1] + K + 1, len(mat))
            
            for j in range(start_j, stop_j):
                Sum += sum(mat[j][start_i:stop_i])
            print('start_i', start_i, 'stop_i', stop_i, 'start_j', start_j, 'stop_j', stop_j)
            print('sum', Sum)
            return Sum
        res = []
        for i in range(len(mat)):
            res.append([])
            for j in range(len(mat[i])):
                res[i].append(sumMatrix((j ,i)))
        return res

class Solution:
    def matrixBlockSum(self, mat: List[List[int]], K: int) -> List[List[int]]:
        
        
        m = len(mat)
        n = len(mat[0])
        out = [[ 0 for x in range ( 0 , n)] for y in range ( m)]
        for i in range ( 0,m):
            for j in range ( 0,n):
                
                r_low= max ( 0, i-K)
                r_high= min(i+K, m)
                
                c_low=max( 0, j-K)
                c_high=min(j+K, n)
                #print(r_low, r_high)
                #print(c_low, c_high)
                
                s = 0 
                for i2 in range ( r_low, min(r_high+1,m) ):
                    #print(  mat[i2] [ c_low:c_high+1])
                    s += sum ( mat[i2] [ c_low:c_high+1] )
                print((i,j, n,m))
                out[i][j] = s 
                #print(s,out[i][j])
                #print(out)
                #print(\"--\")
        
        return out 


class Solution:   
    def matrixBlockSum(self, mat: List[List[int]], K: int) -> List[List[int]]:
        valid_row_indexes = range(len(mat))
        valid_col_indexes = range(len(mat[0]))
        answer = [[0]*len(mat[0]) for _ in range(len(mat))]
        for r in valid_row_indexes:
            for c in valid_col_indexes:
                left = c-K if c-K in valid_col_indexes else None
                right = c+K+1 if c+K in valid_col_indexes else None
                answer[r][c] += sum([sum(mat[i][left:right]) for i in range(r-K, r+K+1) if i in valid_row_indexes])
        return answer                

class Solution:
    def matrixBlockSum(self, mat: list, K: int):
        def calc_surround(r, c):
            nonlocal mat, K
            total = 0
            for i in range(r-K, r+K+1):
                for j in range(c-K, c+K+1):
                    if 0 <= i < len(mat) and 0 <= j < len(mat[0]):
                        total += mat[i][j]
            return total

        def calc_left_column(r, c):
            nonlocal mat, K
            total = 0
            for i in range(r-K, r+K+1):
                if 0 <= i < len(mat) and 0 <= c - K - 1 < len(mat[0]):
                    total += mat[i][c-K-1]
            return total

        def calc_right_column(r, c):
            nonlocal mat, K
            total = 0
            for i in range(r-K, r+K+1):
                if 0 <= i < len(mat) and 0 <= c + K < len(mat[0]):
                    total += mat[i][c+K]
            return total

        grid = [[0] * len(mat[0]) for _ in range(len(mat))]
        for i in range(len(mat)):
            cache = 0
            for j in range(len(mat[0])):
                if j == 0:
                    cache = calc_surround(i, j)
                else:
                    left_c = calc_left_column(i, j)
                    right_c = calc_right_column(i, j)
                    cache = cache - left_c + right_c
                grid[i][j] = cache
        return grid

from copy import deepcopy

class Solution:
    def matrixBlockSum(self, mat: List[List[int]], K: int) -> List[List[int]]:
        matrix = deepcopy(mat)
        for i in range(len(matrix)):
            for j in range(len(matrix[0])):
                top = max(0, i - K)
                bottom = min(len(mat), i + K + 1)
                left = max(0, j - K)
                right = min(len(mat[0]), j + K + 1)
                matrix[i][j] = sum(map(sum, [row[left:right] for row in mat][top:bottom]))
        return matrix

class Solution:
    def matrixBlockSum(self, mat: List[List[int]], K: int) -> List[List[int]]:
        n= len(mat)
        m = len(mat[0])
        matx = []
        for i in range (n):
            row = []
            for j in range (m):
                summ = 0
                for y in range (max(0,i-K),min(n,i+K+1)):
                    summ = summ + sum(mat[y][max(0,j-K):min(m,j+K+1)])
                row.append(summ)
            print (row)
            matx.append(row)
        return(matx)

class Solution:
    def matrixBlockSum(self, mat: List[List[int]], K: int) -> List[List[int]]:
        
        if K==0:
            return mat.copy()
        
        answers = []
        dp = []
        for row in mat:
            answers.append(row.copy())
            dp.append(row.copy())
            
        # add first line of dp
        count = mat[0][0]
        for j in range(1,len(mat[0])):
            count += mat[0][j]
            dp[0][j] = count
            
        for i in range(1,len(mat)):
            count = 0
            for j in range(len(mat[0])):
                count += mat[i][j]
                dp[i][j] = count + dp[i-1][j]
        
        
        for i in range(len(mat)):
            for j in range(len(mat[0])):
                
                x_outer = i+K if i+K < len(mat)-1 else len(mat)-1
                y_outer = j+K if j+K < len(mat[0])-1 else len(mat[0])-1
                
                total = dp[x_outer][y_outer]
                if i-K > 0 and j-K > 0:
                    total += dp[i-K-1][j-K-1]
                if j-K > 0:
                    total -= dp[x_outer][j-K-1]
                if i-K > 0:
                    total -= dp[i-K-1][y_outer]
                
                print((i,j,[i-K-1,j-K-1],[x_outer,y_outer], total))
                answers[i][j] = total
                
        print(dp)
            
        return answers
        
        
        
        


class Solution:
    def matrixBlockSum(self, mat: List[List[int]], K: int) -> List[List[int]]:
        m,n=len(mat),len(mat[0])
        if K>=max(m-1,n-1):
            return [[sum([sum(i) for i in mat])]*n for _ in range(m)]
        res=[[0]*n for _ in range(m)]
        for r in range(m):
            for c in range(n):
 
                res[r][c]=sum([sum(i[max(c-K,0):min(n,c+K+1)]) for i in mat[max(0,r-K):min(m,r+K+1)]])
        return res

class Solution:
    def matrixBlockSum(self, mat: List[List[int]], K: int) -> List[List[int]]:
        m,n = len(mat), len(mat[0])
        # result_mat = [[0]*n]*m
        result_mat = []
        for i in range(m):
            result_mat.append([0]*n)
        
        for i in range(m):
            for j in range(n):
                result_mat[i][j] = sum([sum(mat[k][max(0,j-K):min(n,j+K+1)]) for k in range(max(0,i-K),min(m,i+K+1))])
        
        return result_mat

class Solution:
    def matrixBlockSum(self, mat, K):


        def idx(i, j):

            return i * len(mat[j]) + j

        prefixSum = dict()
        prefixSum[-1] = 0
        currSum = 0
        for i in range(len(mat)):
            for j in range(len(mat[i])):
                currSum += mat[i][j]
                prefixSum[idx(i, j)] = currSum

        answer = [[0 for c in range(len(mat[r]))] for r in range(len(mat))]

        for r in range(len(mat)):
            for c in range(len(mat[r])):
                currSum = 0
                for i in range(max(r - K, 0), min(r + K + 1, len(mat))):
                    currSum += prefixSum[idx(i, min(c + K, len(mat[i]) - 1))] - \\
                        prefixSum[idx(i, max(c - K, 0) - 1)]

                answer[r][c] = currSum

        return answer

        
        

class Solution:
    def matrixBlockSum(self, mat: List[List[int]], K: int) -> List[List[int]]:
        n = len(mat)
        m = len(mat[0])
        answer = [[0] * m for i in range(n)]
      
        maxo = max
        sumo = sum
        mino = min
        for i in range(n):
            for j in range(m):
                r = maxo(0, i-K)           
                sum1 = 0
                while r <= i+K and r < n:
                    sum1 += sumo(mat[r][maxo(0,j-K):mino(m, j+K+1)])
                        
                    r += 1
                answer[i][j] = sum1
            
        return answer

class Solution:
    def distk(self,k,rowsum,colsum,i,j):
        s=0
        m=len(rowsum)
        n=len(rowsum[0])
        if(i-k>=0):
            l=max(-1,j-k-1)
            h=min(n-1,j+k)
            s+=rowsum[i-k][h]
            if(l>-1):
                s-=rowsum[i-k][l]
       
        if(i+k<m):
            l=max(-1,j-k-1)
            h=min(n-1,j+k)
            s+=rowsum[i+k][h]
            if(l>-1):
                s-=rowsum[i+k][l]
      
        if(j-k>=0):
            l=max(-1,i-k)
            h=min(m-1,i+k-1)
            s+=colsum[h][j-k]
            if(l>-1):
                s-=colsum[l][j-k]
       
        if(j+k<n):
            l=max(-1,i-k)
            h=min(m-1,i+k-1)
            s+=colsum[h][j+k]
            if(l>-1):
                s-=colsum[l][j+k]

        return s
            
            
            
    def matrixBlockSum(self, mat: List[List[int]], K: int) -> List[List[int]]:
        m=len(mat)
        n=len(mat[0])
        if(K<=0):
            return mat
        rowsum=[[0 for i in range(n)] for j in range(m)]
        colsum=[[0 for i in range(n)] for j in range(m)]
        for i in range(m):
            rowsum[i][0]=mat[i][0]
            for j in range(1,n):
                rowsum[i][j]+=rowsum[i][j-1]+mat[i][j]
        for i in range(n):
            colsum[0][i]=mat[0][i]
            for j in range(1,m):
                colsum[j][i]+=colsum[j-1][i]+mat[j][i]
        # print(rowsum,colsum)
        ans=[[mat[j][i] for i in range(n)] for j in range(m)]
        
        for k in range(1,K+1):
            for i in range(m):
                for j in range(n):
                    x=self.distk(k,rowsum,colsum,i,j)
                    
                    ans[i][j]+=x
        return ans
                    
            
        


class Solution:
    def distk(self,k,rowsum,colsum,i,j):
        s=0
        m=len(rowsum)
        n=len(rowsum[0])
        if(i-k>=0):
            l=max(-1,j-k-1)
            h=min(n-1,j+k)
            s+=rowsum[i-k][h]
            if(l>-1):
                s-=rowsum[i-k][l]
       
        if(i+k<m):
            l=max(-1,j-k-1)
            h=min(n-1,j+k)
            s+=rowsum[i+k][h]
            if(l>-1):
                s-=rowsum[i+k][l]
      
        if(j-k>=0):
            l=max(-1,i-k)
            h=min(m-1,i+k-1)
            s+=colsum[h][j-k]
            if(l>-1):
                s-=colsum[l][j-k]
       
        if(j+k<n):
            l=max(-1,i-k)
            h=min(m-1,i+k-1)
            s+=colsum[h][j+k]
            if(l>-1):
                s-=colsum[l][j+k]

        return s      
    def matrixBlockSum(self, mat: List[List[int]], K: int) -> List[List[int]]:
        m=len(mat)
        n=len(mat[0])
        if(K<=0):
            return mat
        rowsum=[[0 for i in range(n)] for j in range(m)]
        colsum=[[0 for i in range(n)] for j in range(m)]
        for i in range(m):
            rowsum[i][0]=mat[i][0]
            for j in range(1,n):
                rowsum[i][j]+=rowsum[i][j-1]+mat[i][j]
        for i in range(n):
            colsum[0][i]=mat[0][i]
            for j in range(1,m):
                colsum[j][i]+=colsum[j-1][i]+mat[j][i]
        # print(rowsum,colsum)
        ans=[[mat[j][i] for i in range(n)] for j in range(m)]
        
        for k in range(1,K+1):
            for i in range(m):
                for j in range(n):
                    x=self.distk(k,rowsum,colsum,i,j)
                    
                    ans[i][j]+=x
        return ans
                    
            
        


class Solution:
    def matrixBlockSum(self, mat: List[List[int]], K: int) -> List[List[int]]:
        # naive: always recomput block k*k for O(N*M) positions
        # better: for large k, compute once then advance j by removing leftcol and adding rightcol, etc
          # save rowsum and colsum O(N+M) mem then use to derive a given block?
            # BUT we can't derive middle k slices of row/col  unless we do k rows....
          # O(N*M)*()
        N,M = len(mat),len(mat[0])
        ans = [[0]*M for i in range(N)]
        
        def getBlockSum(i,j):
          # print(f'{i},{j}')
          rows = mat[max(0,i-K):i+K+1]  # [-1:2] -> empty!!
          # print(f'{rows}')
          block = list(zip(*rows))[max(0,j-K):j+K+1]
          # print(f'{block}')
          return sum(sum(blockrow) for blockrow in block)
        
        for i in range(N):
          for j in range(M):
            ans[i][j] = getBlockSum(i,j)
        
        return ans
        
        # rowSums,colSums = [0]*N,[0]*M
        # for i in range(N):
        #   rowSums[i] = sum(mat[i])
        # for j in range(M):
          # colSums[i] = sum(zip(*mat)[j])  #sum([mat[i][j] for i in range(N)])   # 
        


class Solution:
    
    numRows = 0
    numCols = 0
    mat = [[]]
    K = 0
    
    def getBounds(self, row, col):
        return [(max(row-self.K, 0), max(col-self.K, 0)),   \\
                (min(row+self.K,self.numRows-1), min(col+self.K,self.numCols-1))]
    
    def getBlockSum(self, bounds):
        ret = 0
        rowRestricted = self.mat[bounds[0][0] : bounds[1][0]+1]
        for row in rowRestricted:
            ret += sum(row[bounds[0][1]:bounds[1][1]+1])
        return ret
    
    def matrixBlockSum(self, mat: List[List[int]], K: int) -> List[List[int]]:
        ret = []
        self.numRows = len(mat)
        self.numCols = len(mat[0])   #numCols >= 1
        self.mat = mat
        self.K = K
        
        for row in range(self.numRows):
            tmpRow = []
            for col in range(self.numCols):
                bounds = self.getBounds(row, col)
                tmpRow.append(self.getBlockSum(bounds))
            ret.append(tmpRow)
        
        return ret

class Solution:
    def matrixBlockSum(self, mat: List[List[int]], K: int) -> List[List[int]]:
        m, n = len(mat), len(mat[0])
        
        for r in range(m):
            mat[r] = [0]*K + mat[r] + [0]*K
        for i in range(K):
            mat = [[0]*(n+2*K)] + mat + [[0]*(n+2*K)]
        ret = []
        print(mat)
        for i in range(m):
            this = []
            for j in range(n):
                I, J = i+K, j+K
                add = sum([sum(mat[r][J-K:J+K+1]) for r in range(I-K, I+K+1)])
                # print(mat[r][J-K:J+K])
                this.append(add)
                # this.append(sum([sum(mat[r][c] for c in range(J-K, J+K)) for r in range(I-K, I+K)]))
            ret.append(this)
        return ret
                
            
              


class Solution:
    def getArrIJ(self, i: int, j: int, arr: List[List[int]]) -> int:
        if i >= len(arr) and j >= len(arr[0]):
            return arr[len(arr) - 1][len(arr[0]) - 1]
        if i >= len(arr):
            return arr[len(arr) - 1][j]
        if j >= len(arr[0]):
            return arr[i][len(arr[0]) - 1]

        if i < 0 and j < 0:
            return arr[0][0]
        if i < 0:
            return arr[0][j]
        if j < 0:
            return arr[i][0]
        
        return arr[i][j]
    
    def matrixBlockSum(self, mat: List[List[int]], K: int) -> List[List[int]]:
        m = len(mat)
        n = len(mat[0])
        
        res = []
        for i in range(K + 1):
            res.append([0] * (n + 2 * (K + 1)))
        for i in range(m):
            res.append([0] * (K + 1) + mat[i] + [0] * (K + 1))
        for i in range(K + 1):
            res.append([0] * (n + 2 * (K + 1)))

        for i in range(1,m+2*(K+1)):
            for j in range(1,n+2*(K+1)):
                res[i][j] = res[i][j] + res[i-1][j] + res[i][j - 1] - res[i - 1][j - 1]

        # print(res)       
        for i in range(K+1,m+K+1):
            for j in range(K+1,n+K+1):
                # print(f'mat[{i-K}][{j-K}] = res[{i + K}][{j + K}] - (res[{i + K}][{j - K - 1}] + res[{i - K - 1}][{j + K}] - res[{i - K - 1}][{j - K - 1}])')
                mat[i-K-1][j-K-1] = res[i + K][j + K] - (res[i + K][j - K - 1] + res[i - K - 1][j + K] - res[i - K - 1][j - K - 1])
        return mat
        


class Solution:
    def matrixBlockSum(self, mat: List[List[int]], K: int) -> List[List[int]]:
        m=len(mat)
        n=len(mat[0])
        ans=[[0 for i in range(n)] for j in range(m)]
        for i in range(m):
            for j in range(n):
                for l in range(max(0,i-K),min(i+K+1,m)):
                    ans[i][j]+=sum(mat[l][max(0,j-K):min(j+K+1,n)])
                    
        return ans

class Solution:
    def matrixBlockSum(self, mat: List[List[int]], K: int) -> List[List[int]]:
        
        m, n = len(mat), len(mat[0])
        
        padded_mat = []
        for i in range(K):
            padded_mat.append([0]*(n+2*K))
            
        for i in range(m):
            padded_mat.append([0]*K+mat[i]+[0]*K)
            
        for i in range(K):
            padded_mat.append([0]*(n+2*K))
        
        sum_mat = []
        for i in range(m):
            sum_mat.append([0]*n)

        for i in range(m):
            for j in range(n):
                sum_mat[i][j] = sum([sum(row[j:j+2*K+1]) for row in padded_mat[i:i+2*K+1]])
            
        return sum_mat

class Solution:
    def matrixBlockSum(self, mat: List[List[int]], K: int) -> List[List[int]]:
        row_size,col_size = len(mat),len(mat[0])
        ans = [[0 for _ in range(len(mat[0]))] for _ in range(len(mat))]
        for x in mat:
            for _ in range(K):
                x.append(0)
                x.insert(0,0)
        row = [[0 for _ in range(len(mat[0]))] for _ in range(K)]
        mat =  row + mat + row
        print(mat)
        
        for r in range(K,K+row_size):
            for c in range(K,K+col_size):
                ans[r-K][c-K] = sum(sum(s[c-K:c+K+1]) for s in mat[r-K:r+K+1])
        return ans


class Solution:
    def matrixBlockSum(self, mat: List[List[int]], K: int) -> List[List[int]]:
        
        height = len(mat)
        width = len(mat[0])
        
        z = [[None for _ in range(width)] for _ in range(height)]
        
        for x in range(width):
            for y in range(height):
                z[y][x] = sum(
                    [
                        i for j in [
                        row[max(x - K, 0): x + K + 1] for row in mat[max(y - K, 0): y + K + 1]
                        ] for i in j
                    ]
                ) 
        
        
        return z

class Solution:
    def matrixBlockSum(self, mat: List[List[int]], k: int) -> List[List[int]]:
        prev = 0
        
        answer = []
        
        for row in range(len(mat)):
            answer.append([])
            for col in range(len(mat[0])):
                # sub = 0
                # if col-k >= 0:
                l = max(0, col-k)
                r = min(col+k+1, len(mat[0]))
                t = max(0, row-k)
                b = min(row+k+1, len(mat))
                #print(row, col)
                submat = [mat[i][l:r] for i in range(t,b)]
                
                total = 0
                for one in submat:
                    for two in one:
                        total += two
                answer[-1].append(total)
                
                #print(submat)
                #print(total)
#                 add = 0
                
#                 value = prev - () + ()
#                 answer.append(value)

        return answer

class Solution:
    def matrixBlockSum(self, mat: List[List[int]], K: int) -> List[List[int]]:
        m = len(mat)
        n = len(mat[0])
        dp = []
        for i in range(m + 2 * K):
            row = []
            for j in range(n + 2 * K):
                row.append(0)
            dp.append(row)
                
        for i in range(m):
            for j in range(n):
                dp[K + i][K + j] = mat[i][j]
        
        for i in range(m):
            
            for j in range(n):
                temp = 0
                for i1 in range(-K, K + 1):
                    temp += sum(dp[i1 + K + i][j:j + 2 * K + 1])
                
                mat[i][j] = temp
        return mat

class Solution:
    def matrixBlockSum(self, mat: List[List[int]], K: int) -> List[List[int]]:
        m = len(mat)
        n = len(mat[0])
        answer = [[0 for i in range(n)] for i in range(m)]
        
        '''
        answer[i][j] = sum(mat[r][c]) 
            for K <= r <= i + K 
            for j - K <= c <= j + K
        '''
        
        for i in range(n):
            for j in range(m):
                c_lower = max(0, i - K)
                c_upper = min(i + K + 1, n)
                r_lower = max(0, j - K)
                r_upper = min(j + K + 1, m)
                print((m, n))
                print(((r_lower, r_upper),(c_lower, c_upper)))
                answer[j][i] = sum([mat[r][c] for r in range(r_lower, r_upper) for c in range(c_lower, c_upper)])
                
        return answer


class Solution:
    def matrixBlockSum(self, mat: List[List[int]], K: int) -> List[List[int]]:
        M = len(mat)
        N = len(mat[0])
        
        def get_sum(i,j):
            def get_range(v, lim):
                return [x for x in range(v-K,v+K+1) if x >= 0 and x < lim]
            ir = get_range(i, M)
            jr = get_range(j, N)
            return sum([mat[x][y] for x in ir for y in jr])

        res = []
        for i in range(len(mat)):
            res.append([])
            for j in range(len(mat[i])):
                res[i].append(get_sum(i,j))
        return res

class Solution:
    def matrixBlockSum(self, mat: List[List[int]], K: int) -> List[List[int]]:
        answer = [[None for _ in range(len(mat[0]))] for __ in range(len(mat))]
        prefix_sum = [[0 for _ in range(len(mat[0]))] for __ in range(len(mat))]
        for i in range(len(mat)):
            for j in range(len(mat[0])):
                prefix_sum[i][j] += mat[i][j]
                prefix_sum[i][j] += prefix_sum[i - 1][j] if 0 <= i - 1 else 0
                prefix_sum[i][j] += prefix_sum[i][j - 1] if 0 <= j - 1 else 0
                prefix_sum[i][j] -= prefix_sum[i - 1][j - 1] if (0 <= i - 1 and 0 <= j - 1) else 0
        print(prefix_sum)
        for i in range(len(mat)):
            for j in range(len(mat[0])):
                bottom_right = prefix_sum[min(i + K, len(mat) - 1)][min(j + K, len(mat[0]) - 1)]
                bottom_left = prefix_sum[min(i + K, len(mat) - 1)][j - K - 1] if (j - K - 1) >= 0 else 0
                top_left = prefix_sum[i - K - 1][j - K - 1] if 0 <= i - K - 1 and 0 <= j - K - 1 else 0
                top_right = prefix_sum[i - K - 1][min(j + K, len(mat[0]) - 1)] if 0 <= i - K - 1 else 0
                answer[i][j] = bottom_right - bottom_left - top_right + top_left
        return answer

class Solution:
    def matrixBlockSum(self, mat: List[List[int]], k: int) -> List[List[int]]:
        m =len(mat)
        n = len(mat[0])
        arr=[]
        for i in range(m):
            temp=[]
            for j in range(n):
                s=0
                
                r_s=i-k
                r_e=i+k+1
                if r_s<0:
                    r_s=0
                if r_e>m:
                    r_e=m
                c_s=j-k
                c_e=j+k+1
                if c_s<0:
                    c_s=0
                if c_e>n:
                    c_e=n
                for ki in range(r_s,r_e):
                    for l in range(c_s,c_e):
                        s=mat[ki][l]+s
                temp.append(s)
            arr.append(temp)
        return arr
                


class Solution:
    def matrixBlockSum(self, mat: List[List[int]], K: int) -> List[List[int]]:
        
        
        m = len(mat)
        n = len(mat[0])
        
        answer = [[0 for _ in range(n)] for _ in range(m)]
        
        for i in range(m):
            for j in range(n):
                
                lower_row = max(0, i-K)
                upper_row = min(m-1, i+K)
                left_col = max(0, j-K)
                right_col = min(n-1, j+K)
                
                total = 0
                
                for x in range(lower_row, upper_row + 1):
                    for y in range(left_col, right_col + 1):
                        total += mat[x][y]
                
                answer[i][j] = total
                
                
                
        return answer

class Solution:
    def matrixBlockSum(self, mat: List[List[int]], K: int) -> List[List[int]]:
        \"\"\"
        Brute force solution is to perform the sum for each position
        (r, c). This would require K * K operations for each of m * n positions.
        
        Instead, assuming we compute sums left to right and top down, we can
        use our previous solution to calculate the next one, subtracting the
        sums that fell out of the window and adding the sums that are in.
        
        Pseudo code would be something like this:
        
        prevBlockSum = ...
        for r in range(m):
            for c in range(n):
                if c - K > 0:
                    prevBlockSum -= sum()
        \"\"\"
        m = len(mat)
        n = len(mat[0])
        
        out = []
        for r in range(m):
            new_row = []
            for c in range(n):
                blockSum = 0
                
                rs = r-K if r-K >= 0 else 0
                re = r+K if r+K < m else m-1
                cs = c-K if c-K >= 0 else 0
                ce = c+K if c+K < n else n-1
                
                for i in range(rs, re+1):
                    for j in range(cs, ce+1):
                        blockSum += mat[i][j]
                
                new_row.append(blockSum)
            out.append(new_row)
        return out

class Solution:
    def matrixBlockSum(self, mat: List[List[int]], K: int) -> List[List[int]]:
        ans = []
        # answer[0][0] = -1 <= r <= 1 , -1 <= c <= 1
        # answer[1][1] = 0 <= r <= 2, 0 <= c <= 2
        
        for i in range(0, len(mat)):
            ans.append([])
            for j in range(0, len(mat[0])):
                rL = max(0, i - K)
                rR = min(len(mat)-1, i + K)
                cL = max(0, j - K)
                cR = min(len(mat[0])-1, j + K)
                posVal = 0
                for rVal in range(rL, rR+1):
                    for cVal in range(cL, cR+1):
                        posVal += mat[rVal][cVal]
                ans[i].append(posVal)
        return ans

class Solution:
    def matrixBlockSum(self, mat: List[List[int]], K: int) -> List[List[int]]:
        res=[]
        for i in range(len(mat)):
            row=[]
            for j in range(len(mat[0])):
                #print(mat[i][j])
                # find the index limits of sub matrix
                up= max(i-K, 0)
                bottom= min(i+K, len(mat)-1)
                left= max(j-K, 0)
                right= min(j+K, len(mat[0])-1)
                sum=0
                for x in range(up, bottom+1):
                    for y in range(left, right+1):
                        sum += mat[x][y]
                row.append(sum)
            res.append(row)
        return res

class Solution:
    def matrixBlockSum(self, mat: List[List[int]], k: int) -> List[List[int]]:
        m, n = len(mat), len(mat[0])
        ans = []
        for i in range(m):
            temp = []
            for j in range(n):
                temp.append(sum([mat[r][c] for r in range(max(0, i-k), min(i+k+1, m)) for c in range(max(0, j-k), min(n, j+k+1))]))
            ans.append(temp)
        return ans

class Solution:
    def matrixBlockSum(self, mat: List[List[int]], k: int) -> List[List[int]]:
        arr = [[0 for _ in range(len(mat[0]))] for _ in range(len(mat))]
        def addsum(i,j):
            i_start = i-k
            i_end = i+k
            j_start = j-k
            j_end = j+k
            ans = 0
            if i-k<0:
                i_start = 0
            if i+k>=len(mat):
                i_end = len(mat)-1
            if j-k<0:
                j_start = 0
            if j+k>=len(mat[0]):
                j_end = len(mat[0])-1
            for m in range(i_start,i_end+1):
                for n in range(j_start,j_end+1):
                    ans+=mat[m][n]
            arr[i][j] = ans
            return 
        for i in range(len(mat)):
            for j in range(len(mat[0])):
                addsum(i,j)
        return arr

class Solution:
    def matrixBlockSum(self, mat: List[List[int]], K: int) -> List[List[int]]:
        res_mat = []
        M = len(mat)
        N = len(mat[0])
        # print(M,N)
        for i, m in enumerate(mat):
            res_list = []
            for j, n in enumerate(m):
                val = 0
                r_min = i-K if i-K > 0 else 0
                r_max = i+K+1 if i+K+1 < M else M
                c_min = j-K if j-K > 0 else 0
                c_max = j+K+1 if j+K+1 < N else N
                # print(r_min, r_max, c_min, c_max)
                for k in range(r_min, r_max):
                    for l in range(c_min, c_max):
                        val += mat[k][l]
                res_list.append(val)
                # print(res_list)
            res_mat.append(res_list)
            # print(res_mat)
        return res_mat

class Solution:
    def sumHelper(self, mat: List[List[int]], rowLow: int, rowHigh: int, colLow: int, colHigh: int) -> int:
        res = 0
        for r in range(rowLow, rowHigh + 1):
            for c in range(colLow, colHigh + 1):
                res += mat[r][c]
        return res
    
    def matrixBlockSum(self, mat: List[List[int]], K: int) -> List[List[int]]:
        rows = len(mat)
        cols = len(mat[0])
        res = [[0 for c in range(cols)] for r in range(rows)]
        
        for r in range(rows):
            for c in range(cols):
                lowR = r - K
                if (lowR < 0): lowR = 0
                highR = r + K
                if (highR >= rows): highR = rows - 1
                    
                lowC = c - K
                if (lowC < 0): lowC = 0
                highC = c + K
                if (highC >= cols): highC = cols - 1
        
                res[r][c] = self.sumHelper(mat, lowR, highR, lowC, highC)
        
        return res

class Solution:
    def suma(self,mat,m,n,red,stupac,K):
        s = 0
        poc_red = max(red-K,0)
        kraj_red = min(red+K+1,m)
        
        poc_stupac = max(stupac-K,0)
        kraj_stupac = min(stupac+K+1,n)
        
        for i in range(poc_red, kraj_red):
            for j in range(poc_stupac, kraj_stupac):
                s += mat[i][j]        
        return s
    
        
    def matrixBlockSum(self, mat: List[List[int]], K: int) -> List[List[int]]:
        m = len(mat)
        n = len(mat[0])
        res = [[0 for j in range(n)] for i in range(m)]
        
        for i in range(m):
            for  j in range(n):
                res[i][j] = self.suma(mat,m,n,i,j,K)
        return res

class Solution:
    def matrixBlockSum(self, mat: List[List[int]], K: int) -> List[List[int]]:
        m = len(mat)
        n = len(mat[0])
        
        res = []
        for i in range(K + 1):
            res.append([0] * (n + 2 * (K + 1)))
        for i in range(m):
            res.append([0] * (K + 1) + mat[i] + [0] * (K + 1))
        for i in range(K + 1):
            res.append([0] * (n + 2 * (K + 1)))
        
        for i in range(1, m + 2*(K + 1)):
            for j in range(1, n + 2*(K + 1)):
                res[i][j] = res[i][j] + res[i - 1][j] + res[i][j - 1] - res[i - 1][j - 1]

        for i in range(K + 1, m + K + 1):
            for j in range(K + 1, n + K + 1):
                mat[i - K - 1][j - K - 1] = res[i + K][j + K] - (res[i + K][j - K - 1] + res[i - K - 1][j + K] - res[i - K - 1][j - K - 1])
        return mat
        


class Solution:
    def matrixBlockSum(self, mat: List[List[int]], K: int) -> List[List[int]]:
        rows, cols = len(mat), len(mat[0])
        dp = [[0]*cols for _ in range(rows)]
        
        
        def g(x,y):
            nonlocal rows, cols
            if x < 0 or y < 0: return 0
            return dp[min(x,rows-1)][min(y,cols-1)]
        
        for i in range(rows):
            for j in range(cols):
                dp[i][j] = mat[i][j]+g(i-1,j)+g(i,j-1)-g(i-1,j-1)
        ans = [[0]*cols for _ in range(rows)]
        for i in range(rows):
            for j in range(cols):
                ans[i][j] = g(i+K,j+K)+g(i-K-1,j-K-1)-g(i+K,j-K-1)-g(i-K-1,j+K)
        
        return ans


class Solution:
    def matrixBlockSum(self, mat: List[List[int]], K: int) -> List[List[int]]:
        m, n = len(mat[0]), len(mat)
        dp = [[0]*(m+1) for _ in range(n+1)]
        for i in range(1,n+1):
            for j in range(1,m+1):
                dp[i][j] = dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1] + mat[i-1][j-1]
                
        for i in range(n):
            for j in range(m):
                l, r = max(0, i - K), max(0, j - K)
                p, q = min(n, i + K + 1), min(m, j + K + 1)
                mat[i][j] = dp[p][q] - dp[p][r] - dp[l][q] + dp[l][r]
        return mat


class Solution:
    def matrixBlockSum(self, mat: List[List[int]], K: int) -> List[List[int]]:
        

        
        k = K
        # separable, so do two 1-d convolutions
        def convolve(values):
            acc = sum( values[:k] )
            result = []
            for i in range(len(values)):
                if i + k < len(values):
                    acc += values[i+k]
                if i - k - 1 >= 0:
                    acc -= values[i-k-1]
                result.append(acc)
            return result

        def transpose(matrix):
            m = len(matrix)
            n = len(matrix[0])
            transposed = []
            for j in range(n):
                col = [matrix[i][j] for i in range(m)]
                row = col
                transposed.append(row)
            return transposed

        convolved_rows = [convolve(row) for row in mat]
        tranposed = transpose(convolved_rows)
        convolved = [convolve(row) for row in tranposed]

        return transpose(convolved)


import numpy as np
class Solution:
    def matrixBlockSum(self, mat: List[List[int]], k: int) -> List[List[int]]:
        m = len(mat)
        n = len(mat[0])
        pre = [[0]*n for j in range(m)]

        for i in range(m):
            pre[i][0] = mat[i][0]
            for j in range(1, n):
                pre[i][j] = pre[i][j - 1] + mat[i][j]
    
    
        for i in range(n):
            pre[0][i] = pre[0][i]
            for j in range(1, m):
                pre[j][i] = pre[j - 1][i] + pre[j][i]
                
        for i in range(m):
            ru = max(i - k, 0)
            rd = min(i + k, m - 1)
            for j in range(n):
                cl = max(0, j - k)
                cr = min(n - 1, j + k)
                value = pre[rd][cr]
                
                if ru - 1 >= 0:
                    value -= pre[ru - 1][cr]
                    
                if cl - 1 >= 0:
                    value -= pre[rd][cl - 1]
                    
                if ru - 1 >= 0 and cl - 1 >= 0:
                    value += pre[ru - 1][cl - 1]
        
                mat[i][j] = value
            
        return mat

class Solution:
  def matrixBlockSum(self, mat: List[List[int]], K: int) -> List[List[int]]:
    # Obvious DP for O(MNK), do a second DP to bring down to O(MN)
    M, N = len(mat), len(mat[0])
    tsum, lsum = [[0 for _ in range(N)] for _ in range(M)], [[0 for _ in range(N)] for _ in range(M)]
    for i in range(M):
      for j in range(N):
        tsum[i][j] = (0 if i == 0 else tsum[i-1][j]) + mat[i][j]
        lsum[i][j] = (0 if j == 0 else lsum[i][j-1]) + mat[i][j]
    
    ans = [[0 for _ in range(N)] for _ in range(M)]
    def l(i, j):
      if j >= N:
        return l(i, N-1)
      elif 0 <= i < M and 0 <= j < N:
        return lsum[i][j]
      return 0
    def t(i, j):
      if i >= M:
        return t(M-1, j)
      elif 0 <= i < M and 0 <= j < N:
        return tsum[i][j]
      return 0
    
    for i in range(min(M, K+1)):
      for j in range(min(N, K+1)):
        ans[0][0] += mat[i][j]
    for i in range(1, M):
      ans[i][0] = ans[i-1][0] + l(i+K, K) - l(i-K-1, K)
    for j in range(1, N):
      ans[0][j] = ans[0][j-1] + t(K, j+K) - t(K, j-K-1)
    for i in range(1, M):
      for j in range(1, N):
        tl = ans[i-1][j-1]
        add = l(i+K, j+K) - l(i+K, j-K-1) + t(i+K-1, j+K) - t(i-K-1, j+K)
        sub = t(i+K-1, j-K-1) - t(i-K-2, j-K-1) + l(i-K-1, j+K-1) - l(i-K-1, j-K-1)
        ans[i][j] = tl + add - sub
    return ans


class Solution:
    def matrixBlockSum(self, mat: List[List[int]], K: int) -> List[List[int]]:
        \"\"\"
        neighbors=[(1,0),(0,1),(-1,0),(0,-1),(1,1),(-1,-1),(-1,1),(1,-1)]
        dp=[[0 for i in range(len(mat[0]))] for i in range(len(mat))]
        for i in range(len(mat)):
            for j in range(len(mat[0])):
                queue=[(i,j)]
                visited=set()
                sm=0
                k=-1
                while queue:
                    if k==K:
                        #print(sm)
                        break
                    for each in range(len(queue)):
                        row,col=queue.pop(0)
                        if (row,col) in visited:
                            continue
                        visited.add((row,col))
                        sm+=mat[row][col]
                        for r,c in neighbors:
                            if 0<=row+r<len(mat) and 0<=col+c<len(mat[0]):
                                queue.append((row+r,col+c))
                    k+=1
                dp[i][j]=sm
        return dp
        \"\"\"
        prefix=[[0 for i in range(len(mat[0])+1)] for i in range(len(mat)+1)]
        for i in range(1,len(prefix)):
            for j in range(1,len(prefix[0])):
                prefix[i][j]=(mat[i-1][j-1]+prefix[i-1][j]+prefix[i][j-1])-prefix[i-1][j-1]
        
        
        ans=[[0 for i in range(len(mat[0]))] for i in range(len(mat))]
        for i in range(len(ans)):
            for j in range(len(ans[0])):
                r1=max(0,i-K)
                c1=max(0,j-K)
                r2=min(len(mat)-1,i+K)
                c2=min(len(mat[0])-1,j+K)
                
                ans[i][j]=(prefix[r2+1][c2+1]-prefix[r1][c2+1]-prefix[r2+1][c1])+prefix[r1][c1]
        return ans

class Solution:
    def matrixBlockSum(self, mat, K):
        # ok
        n = len(mat) ; m = len(mat[0])
        arr = [[0]*(m) for i in range(n)]
        for i in range( n ):
            for j in range(1, m):
                mat[i][j]+=mat[i][j-1]
        for j in range(m):
            for i in range(1,n):
                mat[i][j]+=mat[i-1][j]
        # [print(mat[i]) for i in range(n)]
        for i in range(n):
            for j in range(m):
                min_row, max_row = max( 0, i-K), min( n-1, i+K)
                min_col, max_col = max( 0, j-K), min( m-1, j+K)

                arr[i][j] = mat[max_row][max_col]

                if min_row > 0:
                    arr[i][j] -= mat[min_row-1][max_col]

                if min_col > 0:
                    arr[i][j] -= mat[max_row][min_col-1]

                if min_col > 0 and min_row > 0:
                    arr[i][j] += mat[min_row-1][min_col-1]
        return arr

class Solution:
    def matrixBlockSum(self, mat: List[List[int]], K: int) -> List[List[int]]:
        \"\"\"
        Assume:
        
        Algorithm:
        
        prefixsum
        1. row: from left to right
        2. col: from top to bottom
        
        xxxxxx
        xxxxxx
        xXXXXx
        xXXXXx
        xxxxxx
        
        result[i][j] = mat[i+K][j+K] - mat[i-K][j+K] - mat[i+K][j-K] + mat[i-K][j-K]
                            rmax cmax       rmin                 cmin
        need to consider boundary conditions
        
        \"\"\"
        
        m, n = len(mat), len(mat[0])
        range_sum = [[0]*(n+1) for _ in range(m+1)]
        result = [[0]*n for _ in range(m)]
        
        for i in range(m):
            for j in range(n):
                range_sum[i+1][j+1] = range_sum[i][j+1] + range_sum[i+1][j] - range_sum[i][j] + mat[i][j]
        print(range_sum)
        for i in range(m):
            for j in range(n):
                rmin, rmax = max(0, i - K), min(m, i + K + 1)
                cmin, cmax = max(0, j - K), min(n, j + K + 1)
                result[i][j] = range_sum[rmax][cmax] - range_sum[rmin][cmax] - range_sum[rmax][cmin] + range_sum[rmin][cmin]
        return result
        
                

class Solution:
    def matrixBlockSum(self, mat: List[List[int]], K: int) -> List[List[int]]:
        
        if not mat:
            self.cum_matrix = [[]]
        else:
            nrow = len(mat)
            ncol = len(mat[0])
            
            self.cum_matrix = [[0]*ncol for _ in range(nrow)]
            
            # initialize
            self.cum_matrix[0][0] = mat[0][0]
            for i in range(1,ncol):
                self.cum_matrix[0][i] = self.cum_matrix[0][i-1]+mat[0][i]
            for j in range(1,nrow):
                self.cum_matrix[j][0] = self.cum_matrix[j-1][0]+mat[j][0]
                
            for c in range(1, ncol):
                for r in range(1, nrow):
                    self.cum_matrix[r][c] = (self.cum_matrix[r-1][c] + self.cum_matrix[r][ c-1] 
                                            - self.cum_matrix[r-1][c-1] + mat[r][c])
        
        res = [[0]*ncol for _ in range(nrow)]
        
        if not self.cum_matrix:
            return []
        
        for r in range(nrow):
            for c in range(ncol):
                row1 = max(0, r-K)
                col1 = max(0, c-K)
                row2 = min(nrow-1, r+K)
                col2 = min(ncol-1, c+K)

                if row1 == 0 and col1 == 0:
                    res[r][c] = (self.cum_matrix[row2][col2])
                elif row1 == 0 and col1 > 0:
                    res[r][c] = (self.cum_matrix[row2][col2]
                        - self.cum_matrix[row2][col1-1] )
                elif row1 > 0 and col1 == 0:
                    res[r][c] = (self.cum_matrix[row2][col2]
                        - self.cum_matrix[row1-1][col2] )
                else:
                    res[r][c] = (self.cum_matrix[row2][col2] - self.cum_matrix[row1-1][ col2] 
                            - self.cum_matrix[row2][col1-1] + self.cum_matrix[row1-1][col1-1])
                    
        return res


# Your NumMatrix object will be instantiated and called as such:
# obj = NumMatrix(matrix)
# param_1 = obj.sumRegion(row1,col1,row2,col2)


class Solution:
    def matrixBlockSum(self, mat: List[List[int]], K: int) -> List[List[int]]:
        iMax = len(mat)
        jMax = len(mat[0])
        ans = [[0 for j in range(jMax)] for i in range(iMax)]
        
        i = 0
        j = 0
        ans[i][j] = sum([sum([mat[i0][j0] for j0 in range(j, min(jMax, j+K+1))]) for i0 in range(i, min(iMax, i + K +1))])
        # print(ans)
        
        i = 0
        for j in range(1, jMax):
            ans[i][j] = ans[i][j-1]
            if j + K < jMax:
                ans[i][j] += sum([mat[i0][j + K] for i0 in range(max(0, i-K), min(iMax, i+K+1))])
            if j - K-1 >= 0:
                ans[i][j] -= sum([mat[i0][j - K - 1] for i0 in range(max(0, i-K), min(iMax, i+K+1))])
        # print(ans)
        
        j = 0
        for i in range(1, iMax):
            ans[i][j] = ans[i-1][j]
            if i + K < iMax:
                ans[i][j] += sum([mat[i+K][j0] for j0 in range(max(0, j-K), min(jMax, j+K+1))])
            if i - K-1 >= 0:
                ans[i][j] -= sum([mat[i-K-1][j0] for j0 in range(max(0, j-K), min(jMax, j+K+1))])
                
        for i in range(1, iMax):
            for j in range(1, jMax):
                ans[i][j] = ans[i][j-1]
                if j + K < jMax:
                    ans[i][j] += sum([mat[i0][j + K] for i0 in range(max(0, i-K), min(iMax, i+K+1))])
                if j - K-1 >= 0:
                    ans[i][j] -= sum([mat[i0][j - K - 1] for i0 in range(max(0, i-K), min(iMax, i+K+1))])           
                
        # print(ans) 
        return ans
#         for i in range(iMax):
#             for j in range(jMax):
#                 if i == 0 and j== 0:
#                     continue


class Solution:
    def matrixBlockSum(self, mat: List[List[int]], K: int) -> List[List[int]]:
        rc, cc = len(mat), len(mat[0])
        acc = [[0]*(cc+1) for _ in range(rc+1)]
        for r in range(rc):
            for c in range(cc):
                acc[r+1][c+1] = acc[r][c+1] + acc[r+1][c]- acc[r][c]+mat[r][c]
        res = [[0]*cc for _ in range(rc)]
        for r in range(rc):
            for c in range(cc):
                res[r][c] = acc[min(r+K+1, rc)][min(c+K+1, cc)] - acc[max(r-K, 0)][min(c+1+K, cc)] - acc[min(r+1+K, rc)][max(c-K, 0)] + acc[max(r-K, 0)][max(c-K, 0)]
        return res

import copy
class Solution:
    def matrixBlockSum(self, G: List[List[int]], K: int) -> List[List[int]]:
        M, N, G[0] = len(G), len(G[0]), list(itertools.accumulate(G[0])); A = [[0]*N for _ in range(M)]
        for i in range(1,M):
            s = 0
            for j in range(N): s += G[i][j]; G[i][j] = s + G[i-1][j]
        for i,j in itertools.product(list(range(M)),list(range(N))):
            R, C = min(M-1,i+K), min(N-1,j+K)
            A[i][j] = G[R][C] - (i-K > 0 and G[i-K-1][C]) - (j-K > 0 and G[R][j-K-1]) + (i-K > 0 and j-K > 0 and G[i-K-1][j-K-1])
        return A


from itertools import accumulate as acc
class Solution:
    def matrixBlockSum(self, mat: List[List[int]], K: int) -> List[List[int]]:
        ##dp 
        N = len(mat)
        M = len(mat[0])
        ## how do we accumulate
        prefix = [*list(zip(*list(map(acc, list(zip(*list(map(acc, mat))))))))]
        for i in prefix:
            print(i)
        dp = [[0 for _ in range(M)] for _ in range(N)]
        
        for i in range(N):
            for j in range(M):
                r = min(i+K,N-1)
                b = min(j+K,M-1);
                l = max(0,i-K)
                t = max(0,j-K)
                cursum = prefix[r][b]
                #print(cursum)
                if(l-1 >=0):
                    cursum-=prefix[l-1][b]
                if(t-1 >=0):
                    cursum -= prefix[r][t-1];
                if(l-1 >=0 and t-1 >=0):
                    cursum += prefix[l-1][t-1];
                dp[i][j] = cursum
        return dp


class Solution:
    def matrixBlockSum(self, mat: List[List[int]], K: int) -> List[List[int]]:
        m, n = len(mat), len(mat[0])
        rangeSum = [[0] * (n + 1) for _ in range(m + 1)]
        for i in range(m):
            for j in range(n):
                rangeSum[i + 1][j + 1] = rangeSum[i + 1][j] + rangeSum[i][j + 1] - rangeSum[i][j] + mat[i][j]
        ans = [[0] * n for _ in range(m)]        
        for i in range(m):
            for j in range(n):
                r1, c1, r2, c2 = max(0, i - K), max(0, j - K), min(m, i + K + 1), min(n, j + K + 1)
                ans[i][j] = rangeSum[r2][c2] - rangeSum[r1][c2] - rangeSum[r2][c1] + rangeSum[r1][c1]
        return ans

#753

from copy import deepcopy

class Solution:
  def matrixBlockSum(self, mat: List[List[int]], K: int) -> List[List[int]]:
    ret = deepcopy(mat)
    m = len(mat)
    n = len(mat[0])
    
    @lru_cache(None)
    def row_sum(x, y):
      if not 0 <= x < m:
        return 0
      ret = 0
      for j in range(max(0, y), min(n, y + 2 * K + 1)):
        ret += mat[x][j]
      return ret
    
    @lru_cache(None)
    def col_sum(x, y):
      if not 0 <= y < n:
        return 0
      ret = 0
      for i in range(max(0, x), min(m, x + 2 * K + 1)):
        ret += mat[i][y]
      #print(\"colsum\", x, y, ret)
      return ret    
    
    
    for i in range(m):
      for j in range(n):
        if i == 0 and j == 0:
          t = 0
          for u in range(0, min(K+1, m)):
            for v in range(0, min(K+1, n)):
              t += mat[u][v]
          ret[0][0] = t
          continue
        
        if i > 0:
          ret[i][j] = ret[i-1][j] - row_sum(i-1-K, j-K) + row_sum(i+K, j-K)
        else:
          ret[i][j] = ret[i][j-1] - col_sum(i-K, j-K-1) + col_sum(i-K, j+K)
          
    return ret


#753

from copy import deepcopy

class Solution:
  def matrixBlockSum(self, mat: List[List[int]], K: int) -> List[List[int]]:
    ret = deepcopy(mat)
    m = len(mat)
    n = len(mat[0])
    
    @lru_cache(4)
    def row_sum(x, y):
      if not 0 <= x < m:
        return 0
      ret = 0
      for j in range(max(0, y), min(n, y + 2 * K + 1)):
        ret += mat[x][j]
      return ret
    
    @lru_cache(4)
    def col_sum(x, y):
      if not 0 <= y < n:
        return 0
      ret = 0
      for i in range(max(0, x), min(m, x + 2 * K + 1)):
        ret += mat[i][y]
      #print(\"colsum\", x, y, ret)
      return ret    
    
    
    for i in range(m):
      for j in range(n):
        if i == 0 and j == 0:
          t = 0
          for u in range(0, min(K+1, m)):
            for v in range(0, min(K+1, n)):
              t += mat[u][v]
          ret[0][0] = t
          continue
        
        if i > 0:
          ret[i][j] = ret[i-1][j] - row_sum(i-1-K, j-K) + row_sum(i+K, j-K)
        else:
          ret[i][j] = ret[i][j-1] - col_sum(i-K, j-K-1) + col_sum(i-K, j+K)
          
    return ret


class Solution:
    def matrixBlockSum(self, mat: List[List[int]], K: int) -> List[List[int]]:
        m = len(mat)
        n = len(mat[0])
        cum_sum = [[0 for x in range(n+1)] for y in range(m+1)]
        for i in range(1, m+1):
            for j in range(1, n+1):
                if i == 0 and j == 0:
                    cum_sum[i][j] = mat[i-1][j-1]
                elif i == 0:
                    cum_sum[i][j] = mat[i-1][j-1] + cum_sum[i][j-1]
                elif j == 0:
                    cum_sum[i][j] = mat[i-1][j-1] + cum_sum[i-1][j]
                else:
                    cum_sum[i][j] = mat[i-1][j-1] + cum_sum[i-1][j] + cum_sum[i][j-1] - cum_sum[i-1][j-1]
        ans = [[0 for x in range(n)] for y in range(m)]
        for i in range(m):
            for j in range(n):
                maxr = min(i+K, m-1)+1
                maxc = min(j+K, n-1)+1
                minr = max(i-K-1, -1)+1
                minc = max(j-K-1, -1)+1
                ans[i][j] = cum_sum[maxr][maxc] - cum_sum[maxr][minc] - cum_sum[minr][maxc] + cum_sum[minr][minc]
        return ans
                    


class Solution:
    def matrixBlockSum(self, mat: List[List[int]], K: int) -> List[List[int]]:
        rows, cols = len(mat), len(mat[0])
        dic , seen = {} , {} 
        for i, row in enumerate(mat):
            prefix_sum = [0] * (cols + 1)
            for j, num in enumerate(row):
                prefix_sum[j] = prefix_sum[j-1] + num
            
            dic[i] = prefix_sum
            
        for i in range(rows):
            for j in range(cols):
                start_col = j-K if j-K >=0 else 0
                end_col = j+K if j+K < cols else cols-1
                start_row = i-K if i-K >=0 else 0
                end_row = i+K if i+K < rows else rows-1
                if (start_col, end_col, start_row, end_row) in seen:
                    mat[i][j] = seen[start_col, end_col, start_row, end_row]
                    continue
                res = 0
                for idx in range(start_row, end_row+1):
                    res += dic[idx][end_col]- dic[idx][start_col-1]
                mat[i][j] = res
                seen[start_col, end_col, start_row, end_row] = res
        return mat


class Solution:
    def matrixBlockSum(self, mat: List[List[int]], K: int) -> List[List[int]]:
        m = len(mat)
        n = len(mat[0])
        
        res = []
        for i in range(K + 1):
            res.append([0] * (n + 2 * (K + 1)))
        for i in range(m):
            res.append([0] * (K + 1) + mat[i] + [0] * (K + 1))
        for i in range(K + 1):
            res.append([0] * (n + 2 * (K + 1)))

        for i in range(1, m + 2*(K + 1)):
            for j in range(1, n + 2*(K + 1)):
                res[i][j] = res[i][j] + res[i - 1][j] + res[i][j - 1] - res[i - 1][j - 1]

        for i in range(K + 1, m + K + 1):
            for j in range(K + 1, n + K + 1):
                mat[i - K - 1][j - K - 1] = res[i + K][j + K] - (res[i + K][j - K - 1] + res[i - K - 1][j + K] - res[i - K - 1][j - K - 1])
        return mat
        


class Solution:
    def matrixBlockSum(self, mat: List[List[int]], K: int) -> List[List[int]]:
        M = len(mat)
        if M == 0:
            return mat
        N = len(mat[0])
        
        for i in range(1, M):
            mat[i][0] += mat[i-1][0]
        
        for j in range(1, N):
            mat[0][j] += mat[0][j-1]
        
        
        for i in range(1, M):
            for j in range(1, N):
                mat[i][j] = (mat[i][j] + mat[i-1][j] + mat[i][j-1] - mat[i-1][j-1])
        
        answer = [[0 for _ in range(N)] for _ in range(M)]
        
        for i in range(M):
            for j in range(N):
                rl = max(i-K, 0)
                cl = max(j-K, 0)
                rr = min(i+K, M-1)
                cr = min(j+K, N-1)
                
                A, B, C, D = 0, 0, 0, mat[rr][cr]
                
                if rl - 1 >= 0:
                    B = mat[rl-1][cr]
                if cl - 1 >= 0:
                    C = mat[rr][cl-1]
                if rl - 1 >= 0 and cl - 1 >= 0:
                    A = mat[rl-1][cl-1]
                
                answer[i][j] = D + A - B - C
        
        return answer
                


class Solution:
    
    def __init__(self):
        from functools import lru_cache
        return
    
    
    def matrixBlockSum(self, mat: List[List[int]], K: int) -> List[List[int]]:
        self.cache = {}
        k = K
        n, m = len(mat), len(mat[0]) if len(mat) else 0
                      
        def brute_force():
            def kernel(i, j, k):
                minx, maxx = max(i-k,0), min(i+k+1, n)
                miny, maxy = max(j-k,0), min(j+k+1, m)
                s = 0
                for ii in range(minx, maxx):
                    for jj in range(miny, maxy):
                        s += mat[ii][jj]
                return s

            ans = [[0 for j in range(m)] for i in range(n)]
            for i in range(n):
                for j in range(m):
                    ans[i][j] = kernel(i,j, k)
            return ans
        
        #return brute_force()
            
        
        def partials():
            @lru_cache
            def getrowsum(i,j,k):
                if i < 0: return 0
                if i >= n: return 0
                miny, maxy = max(j-k,0), min(j+k+1,m)
                return sum([mat[i][jj] for jj in range(miny, maxy)])

            #@lru_cache
            def getcolsum(ans,i,j,k):
                if j < 0: return 0
                if j >= m: return 0
                if (i-1, j) in self.cache:
                    self.cache[(i,j)] = self.cache[(i-1,j)] \\
                           - (ans[i-k-1][j] if i-k-1 >= 0 else 0) \\
                           + (ans[i+k][j] if i+k < n  else 0)
                else:
                    minx, maxx = max(i-k,0), min(i+k+1,n)
                    self.cache[(i, j)] = sum([ans[ii][j] for ii in range(minx, maxx)])
                return self.cache[(i, j)]

            ans = [[0 for j in range(m)] for i in range(n)]
            for i in range(n):
                for j in range(m):
                    ans[i][j] = getrowsum(i,j,k)

            res = [[0 for j in range(m)] for i in range(n)]
            for i in range(n):
                for j in range(m):
                    res[i][j] = getcolsum(ans,i,j,k)
            return res
        
        return partials()


class Solution:
    def matrixBlockSum(self, mat: List[List[int]], K: int) -> List[List[int]]:
        m, n = len(mat), len(mat[0])
        f = [[0] * n for _ in range(m)]
        for i in range(m):
            for j in range(n):
                if i == 0 and j == 0:
                    for i_ in range(i, i + K + 1):
                        for j_ in range(j, j + K + 1):
                            if i_ < m and j_ < n:
                                f[i][j] += mat[i_][j_]
                elif j == 0:
                    f[i][j] = f[i - 1][j]
                    if i - 1 - K >= 0:
                        for j_ in range(j, j + K + 1):
                            if j_ < n:
                                f[i][j] -= mat[i - 1 - K][j_]
                                
                    if i + K < m:
                        for j_ in range(j, j + K + 1):
                            if j_ < n:
                                f[i][j] += mat[i + K][j_]
                else:
                    f[i][j] = f[i][j - 1]
                    if j - 1 - K >= 0:
                        for i_ in range(i - K, i + K + 1):
                            if 0 <= i_ < m:
                                f[i][j] -= mat[i_][j - 1 - K]
                                
                    if j + K < n:
                        for i_ in range(i - K, i + K + 1):
                            if 0 <= i_ < m:
                                f[i][j] += mat[i_][j + K]
        return f

import numpy as np
class Solution:
    def matrixBlockSum(self, mat: List[List[int]], K: int) -> List[List[int]]:
        m = len(mat)
        n = len(mat[0])
        matrix= np.zeros((m+1, n+1))
        for i in range (m):
            for j in range (n):
                matrix[i+1][j+1]=matrix[i+1][j]+matrix[i][j+1]-matrix[i][j]+mat[i][j]
        result = np.zeros((m, n))
        for i in range(m):
            for j in range(n):
                x1=max(i-K, 0)
                y1=max(j-K, 0)
                x2=min(i+K+1, m)
                y2=min(j+K+1, n)
                result[i][j]=matrix[x2][y2]-matrix[x1][y2]-matrix[x2][y1]+matrix[x1][y1]
        return (result.astype(int))


class Solution:
    def matrixBlockSum(self, mat: List[List[int]], K: int) -> List[List[int]]:
        m, n = len(mat), len(mat[0])
        res = [[0] * n for _ in range(m)]
        dp = [[0] * (n+1) for _ in range(m+1)]
        for i in range(m):
            for j in range(n):
                dp[i+1][j+1] = dp[i][j+1] + dp[i+1][j] - dp[i][j] + mat[i][j]
        
        for i in range(m):
            for j in range(n):
                r1, c1, r2, c2 = max(0, i-K), max(0, j-K), min(m, i+K+1), min(n, j+K+1)
                res[i][j] = dp[r2][c2] + dp[r1][c1] - dp[r2][c1] - dp[r1][c2]
        return res

class Solution:
    
    def __init__(self):
        from functools import lru_cache
        return
    
    
    def matrixBlockSum(self, mat: List[List[int]], K: int) -> List[List[int]]:
        self.cache = {}
        k = K
        n, m = len(mat), len(mat[0]) if len(mat) else 0
                      
        def brute_force():
            def kernel(i, j, k):
                minx, maxx = max(i-k,0), min(i+k+1, n)
                miny, maxy = max(j-k,0), min(j+k+1, m)
                s = 0
                for ii in range(minx, maxx):
                    for jj in range(miny, maxy):
                        s += mat[ii][jj]
                return s

            ans = [[0 for j in range(m)] for i in range(n)]
            for i in range(n):
                for j in range(m):
                    ans[i][j] = kernel(i,j, k)
            return ans
        
        #return brute_force()
            
        
        def partials():
            @lru_cache
            def getrowsum(i,j,k):
                miny, maxy = max(j-k,0), min(j+k+1,m)
                # row cache also needed
                return sum([mat[i][jj] for jj in range(miny, maxy)])

            #@lru_cache
            def getcolsum(ans,i,j,k):
                if (i-1, j) in self.cache:
                    self.cache[(i,j)] = self.cache[(i-1,j)] \\
                                        - (ans[i-k-1][j] if i-k-1 >= 0 else 0) \\
                                        + (ans[i+k][j] if i+k < n  else 0)
                else:
                    minx, maxx = max(i-k,0), min(i+k+1,n)
                    self.cache[(i, j)] = sum([ans[ii][j] for ii in range(minx, maxx)])
                return self.cache[(i, j)]

            ans = [[0 for j in range(m)] for i in range(n)]
            for i in range(n):
                for j in range(m):
                    ans[i][j] = getrowsum(i,j,k)

            res = [[0 for j in range(m)] for i in range(n)]
            for i in range(n):
                for j in range(m):
                    res[i][j] = getcolsum(ans,i,j,k)
            return res
        
        return partials()


class Solution:
    def matrixBlockSum(self, mat: List[List[int]], K: int) -> List[List[int]]:
        m, n = len(mat), len(mat[0])
        k = K
\t\t
        cumsum = [[0]*n for _ in range(m)]
        answer = [[0]*n for _ in range(m)]

        cumsum[0][0]=mat[0][0]
        for j in range(1,n):
            cumsum[0][j] = cumsum[0][j-1] + mat[0][j]
        for i in range(1,m):
            cumsum[i][0] = cumsum[i-1][0] + mat[i][0]
        for j in range(1,n):
            for i in range(1,m):
                cumsum[i][j] = cumsum[i][j-1] + cumsum[i-1][j] - cumsum[i-1][j-1] + mat[i][j]
        
        def getcumsum(i,j):
            if i >=0 and j>=0:
                return cumsum[min(max(0,i), m-1)][min(max(0,j), n-1)]
            else: return 0
            
        for r in range(m):
            for c in range(n):
                answer[r][c] = getcumsum(r+k,c+k) - getcumsum(r+k,c-(k+1)) - getcumsum(r-(k+1),c+k) + getcumsum(r-(k+1),c-(k+1))
        return answer

class Solution:
    def matrixBlockSum(self, mat: List[List[int]], K: int) -> List[List[int]]:
        if not mat or not mat[0]:
            return mat
        answer = [[0 for _ in mat[0]] for _ in mat]
        # create left->right horizontal running sums in each row of mat
        for i in range(len(mat)):
            for j in range(1, len(mat[0])):
                mat[i][j] += mat[i][j - 1]
        # create horizontal 2K+1-sums in answer
        for i in range(len(mat)):
            for j in range(len(mat[0])):
                answer[i][j] = mat[i][min(j + K, len(mat[i]) - 1)]
                if j - K > 0:
                    answer[i][j] -= mat[i][j - K - 1]
        mat, answer = answer, [[0 for _ in mat[0]] for _ in mat]
        for i in range(len(mat)):
            for j in range(len(mat[0])):
                answer[i][j] = sum([mat[k][j] for k in range(max(0, i - K), min(len(mat), i + K + 1))])
        
        
        return answer

import numpy as np

class Solution:
    def matrixBlockSum(self, mat: List[List[int]], K: int) -> List[List[int]]:
        mat = np.array(mat)
        answer = np.zeros(mat.shape)
        for i, row in enumerate(mat):
            row_start = max([0, i - K])
            row_end = min([mat.shape[0] -1, i + K])
            # Each new row, reinitialize the value and add/remove newly in/out of range items
            if i > 0:
                col_start = 0
                col_end = min([mat.shape[1] -1, K])
                val = answer[i - 1][0]
                # Add the new row to the sum
                if i + K <= mat.shape[0] -1:
                    val += np.sum(mat[row_end,col_start:col_end + 1])
                # Remove out of range row
                if row_start > 0:
                    val -= np.sum(mat[row_start -1,col_start:col_end + 1])
            for j, col in enumerate(row):
                col_start = max([0, j - K])
                col_end = min([mat.shape[1] -1, j + K])
                print((row_start, row_end, col_start, col_end))
                if i == 0 and j == 0:
                    val = np.sum(mat[row_start:row_end + 1, col_start:col_end + 1])
                else:
                    # Add the new column to the sum
                    if j + K <= mat.shape[1] -1 and j != 0:
                        val += np.sum(mat[row_start:row_end + 1,col_end])
                    # Remove out of range column
                    if col_start > 0:
                        val -= np.sum(mat[row_start:row_end + 1,col_start - 1])
                answer[i][j] = val
        return answer.astype(np.int)
            
            


class Solution:
    def matrixBlockSum(self, mat: List[List[int]], K: int) -> List[List[int]]:
        pre = [[0] * len(mat[0]) for i in range(len(mat))]
        pre2 = [[0] * len(mat[0]) for i in range(len(mat))]
        res = [[0] * len(mat[0]) for i in range(len(mat))]
        for i in range(len(mat)):
            for j in range(len(mat[0])):
                pre[i][j] = sum(mat[i][y] for y in range(0, j+1))
        for i in range(len(mat)): 
            for j in range(len(mat[0])):
                pre2[i][j] = sum(pre[x][j] for x in range(0, i+1))
        \"\"\"
        [[1,2,3], 1 3 6     1   3   6
         [4,5,6], 4 9 15    5   12  21
         [7,8,9]] 7 15 24   12  27  45
        \"\"\"
        for i in range(len(mat)):
            ru = max(i-K, 0)
            rd = min(i+K, len(mat)-1)
            for j in range(len(mat[0])):
                cl = max(0, j-K)
                cr = min(len(mat[0])-1, j + K)
                v = pre2[rd][cr]
                if ru - 1 >= 0:
                    v -= pre2[ru-1][cr]
                if cl - 1 >= 0:
                    v -= pre2[rd][cl-1]
                if ru - 1 >= 0 and cl - 1 >= 0:
                    v += pre2[ru-1][cl-1]
                res[i][j] = v
        return res

import numpy as np

class Solution:
    def matrixBlockSum(self, mat: List[List[int]], K: int) -> List[List[int]]:
        x_dim = len(mat[0])
        y_dim = len(mat)

        def move_down(mat, y, x_bounds):
            if y >= y_dim or y < 0:
                return 0

            ans = 0
            for x in range(x_bounds[0], x_bounds[1]):
                if -1 < x < x_dim:
                    ans += mat[y][x]
            return ans

        def move_right(mat, y_bounds, x):
            if x >= x_dim or x < 0:
                return 0

            ans = 0
            for y in range(y_bounds[0], y_bounds[1]):
                if -1 < y < y_dim:
                    ans += mat[y][x]
            return ans

        ans = np.array([[0] * len(mat[0])] * len(mat))

        for i in range(0, min(K + 1, y_dim)):
            for j in range(0, min(K + 1, x_dim)):
                ans[0][0] += mat[i][j]

        for i in range(1, y_dim):
            ans[i][0] = ans[i - 1][0] - move_down(mat, i-K-1, (0, K + 1)) + \\
                        move_down(mat, i + K, (0, K + 1))

        for i in range(y_dim):
            for j in range(1, x_dim):
                if (i, j) == (0, 0):
                    continue
                ans[i][j] = ans[i][j - 1] - move_right(mat, (i - K, i + K + 1), j - K - 1) + \\
                            move_right(mat, (i - K, i + K + 1), j + K)
        return ans
        

import numpy as np

class Solution:
    def matrixBlockSum(self, mat: List[List[int]], K: int) -> List[List[int]]:
        A = np.array(mat)
        m, n = A.shape
        return [[A[max(i-K, 0):i+K+1, max(j-K, 0):j+K+1].sum()
                 for j in range(n)] for i in range(m)]

class Solution:
    def matrixBlockSum(self, mat: List[List[int]], K: int) -> List[List[int]]:
        res = [[0 for j in range(len(mat[0]))] for i in range(len(mat))]
        
        for i in range(0, min(len(mat), K + 1)):
            for j in range(0, min(len(mat[0]), K + 1)):
                res[0][0] += mat[i][j]
        
        for i in range(0, len(mat)):
            for j in range(0, len(mat[0])):
                
                if i == 0 and j == 0:
                    continue
                
                
                if j == 0:
                    
                    res[i][j] = res[i - 1][j]
                    
                    old_i = i - K - 1
                    
                    if old_i >= 0:
                        for curr_j in range(max(0, j - K), min(len(mat[0]), j + K + 1)):
                            res[i][j] -= mat[old_i][curr_j]
                                           
                    
                    new_i = i + K
                    
                    if new_i < len(mat):
                        for curr_j in range(max(0, j - K), min(len(mat[0]), j + K + 1)):
                            res[i][j] += mat[new_i][curr_j]
                else:
                    res[i][j] = res[i][j - 1]
                
                    old_j = j - K - 1
                    
                    if old_j >= 0:
                        for curr_i in range(max(0, i - K), min(len(mat), i + K + 1)):
                            res[i][j] -= mat[curr_i][old_j]

                    new_j = j + K

                    if new_j < len(mat[0]):
                        for curr_i in range(max(0, i - K), min(len(mat), i + K + 1)):
                            res[i][j] += mat[curr_i][new_j]
                        
        return res
                


class Solution:
    def matrixBlockSum(self, mat: List[List[int]], K: int) -> List[List[int]]:
        if not mat or not mat[0]:
            return []
        
        height = len(mat)
        width = len(mat[0])
        
        prefix_sum = [[0]*width for _ in range(height)]
        for i in range(height):
            for j in range(width):
                up = prefix_sum[i-1][j] if i > 0 else 0
                left = prefix_sum[i][j-1] if j > 0 else 0
                diag = prefix_sum[i-1][j-1] if i > 0 and j > 0 else 0
                prefix_sum[i][j] = up + left - diag + mat[i][j]
        
        answer = [[0]*width for _ in range(height)]
        for i in range(height):
            for j in range(width):
                lri = min(height - 1, i + K)  # lower right i
                lrj = min(width - 1, j + K)  # lower right j
                uli = i - K - 1  # upper left i
                ulj = j - K - 1  # upper left j
                
                total = prefix_sum[lri][lrj]
                up = prefix_sum[uli][lrj] if uli >= 0 else 0
                left = prefix_sum[lri][ulj] if ulj >= 0 else 0
                diag = prefix_sum[uli][ulj] if uli >= 0 and ulj >= 0 else 0
                
                answer[i][j] = total - up - left + diag
                
        return answer

import numpy as np

class Solution:
    def matrixBlockSum(self, mat: List[List[int]], K: int) -> List[List[int]]:
        n = len(mat)
        m = len(mat[0])
        arr = np.array([[0]*m]*n)
        mat = np.array(mat)
        
        for i in range(n):
            for j in range(m):
                cur = mat[i,j]
                if j-K < 0:
                    hor_s = slice(0, j+K+1)
                    # hor = mat[i, 0:j+K+1]
                else:
                    hor_s = slice(j-K, j+K+1)
                    # hor = mat[i, j-K:j+K+1]
                    
                if i-K < 0:
                    ver_s = slice(0, i+K+1)
                    # ver = mat[0:i+K+1, j]
                else:
                    ver_s = slice(i-K, i+K+1)
                    # ver = mat[i-K:i+K+1, j]
                
                arr[i,j] = mat[ver_s, hor_s].sum()
        
        return arr.tolist()
        


# Matrix Block Sum
# Ваш код ниже
import numpy as np

class Solution:
    def matrixBlockSum(self, mat: List[List[int]], K: int) -> List[List[int]]:
        size_row=len(mat)
        size_col=len(mat[0])
        in_mat=np.array(mat)
        res = np.zeros((size_row,size_col),dtype = np.int32)

        res_cell=0

        r_min = 0
        r_max = min(size_row-1, K)
        c_min = 0
        c_max = min(size_col-1, K)
        for row in in_mat[0:r_max+1:,0:c_max+1:]:
            res_cell+=sum(row)
        
        remove_sum_right=0
        add_sum_right=0

        for i in range(size_row):#i - строка
            if i != 0:
                r_min = max(0, i-K)
                r_max = min(size_row-1, i+K)
                remove_sum_down = 0 if i-K<=0 else np.sum(in_mat[r_min-1:r_min:,:min(K+1,size_col):],axis=1)
               
                add_sum_down = 0 if i+K>size_row-1 else np.sum(in_mat[r_max:r_max+1:,:min(K+1,size_col):],axis=1)
               
                res_cell=res[i-1][0]+add_sum_down-remove_sum_down
           
            for j in range(size_col):#j - столбец
                if j==0:
                    res[i][j]=res_cell
                    continue
                
                c_min = max(0, j-K)
                c_max = min(size_col-1, j+K)
                remove_sum_right = 0 if j-K<=0 else np.sum(in_mat[r_min:r_max+1:,c_min-1:c_min:],axis=0)
               
                add_sum_right = 0 if j+K>size_col-1 else np.sum(in_mat[r_min:r_max+1:,c_max:c_max+1:],axis=0)
                
                res[i][j]=res_cell+add_sum_right-remove_sum_right
                res_cell=res[i][j]
             
        return res

import numpy as np

class Solution:
    def matrixBlockSum(self, mat: List[List[int]], K: int) -> List[List[int]]:
        size_row=len(mat)
        size_col=len(mat[0])
        in_mat=np.array(mat)
        res = np.zeros((size_row,size_col),dtype = np.int32)

        res_cell=0

        r_min = 0
        r_max = min(size_row-1, K)
        c_min = 0
        c_max = min(size_col-1, K)
        for row in in_mat[0:r_max+1:,0:c_max+1:]:
            res_cell+=sum(row)
        #print('res_sel',res_cell)
        remove_sum_right=0
        add_sum_right=0

        for i in range(size_row):#i - строка
            if i != 0:
                r_min = max(0, i-K)
                r_max = min(size_row-1, i+K)
                remove_sum_down = 0 if i-K<=0 else np.sum(in_mat[r_min-1:r_min:,:min(K+1,size_col):],axis=1)
               # print('remove_sum_down ',remove_sum_down)
                add_sum_down = 0 if i+K>size_row-1 else np.sum(in_mat[r_max:r_max+1:,:min(K+1,size_col):],axis=1)
               # print('add_sum_down ',add_sum_down)
                res_cell=res[i-1][0]+add_sum_down-remove_sum_down
           
            for j in range(size_col):#j - столбец
                if j==0:
                    res[i][j]=res_cell
                    continue
                
                c_min = max(0, j-K)
                c_max = min(size_col-1, j+K)
                remove_sum_right = 0 if j-K<=0 else np.sum(in_mat[r_min:r_max+1:,c_min-1:c_min:],axis=0)
                #print('remove_sum_right ',remove_sum_right)

                add_sum_right = 0 if j+K>size_col-1 else np.sum(in_mat[r_min:r_max+1:,c_max:c_max+1:],axis=0)
                #print('add_sum_right ',add_sum_right)
                #сумма, которую надо вычесть при движении вправо
                res[i][j]=res_cell+add_sum_right-remove_sum_right
                res_cell=res[i][j]
                #print('новая ячейка')
             
        return res

class Solution:
    def matrixBlockSum(self, mat: List[List[int]], K: int) -> List[List[int]]:
        nR = len(mat)
        nC = len(mat[0])
        newMat = [[None for j in range(nC)] for i in range(nR)]
        for r,row in enumerate(mat):
            i = 0
            while i<nC:
                if i-K>=0:
                    newMat[r][i] = sum(row[(i-K):(i+K+1)])
                    i+=1
                else:
                    newMat[r][i] = sum(row[0:(i+K+1)])
                    i+=1
        
        finalAns = [[0 for j in range(nC)] for i in range(nR)]
        
        rowNum = 0
        while rowNum<nR:
            print(\"This is rowNum:\",rowNum)
            if rowNum-K<=0:
                minRow = 0
            else:
                minRow = rowNum-K

            if rowNum+K>=nR:
                maxRow = nR
            else:
                maxRow = rowNum+K+1
                
            print(minRow,maxRow)    
            for col in range(nC):
                for r in range(minRow,maxRow):
                    finalAns[rowNum][col] += newMat[r][col]
            rowNum+=1
        
        return finalAns

class Solution:
    def matrixBlockSum(self, mat: List[List[int]], K: int) -> List[List[int]]:
        if not mat:
            return 
        
        m = len(mat)
        n = len(mat[0])
        sumMat = [[0 for i in range (n)] for j in range (m)]
        verMat = [[0 for i in range (n)] for j in range (m)]
        ansMat = [[0 for i in range (n)] for j in range (m)]
        fnlMat = [[0 for i in range (n)] for j in range (m)]
        #fill sumMat with running sum of row
        for i in range (m):
            running_sum = 0 
            for j in range (n):
                running_sum += mat[i][j]
                sumMat[i][j] = running_sum 

        #fill verMat with results from sumMat 
        for i in range(m):
            for j in range (n): 
                verMat[i][j] = self.sumRowWindow(sumMat, i, j, K)
        
        
        for j in range (n):
            running_sum = 0 
            for i in range (m):
                running_sum += verMat[i][j]
                ansMat[i][j] = running_sum 
        
        for i in range (m): 
            for j in range (n): 
                fnlMat[i][j] = self.sumColWindow(ansMat, i,j,K)

#        for i in range (m):
#            print(fnlMat[i])   
        return fnlMat

            
    def sumColWindow(self, verMat, row_i, col_j, window_k):    
        col = [verMat[i][col_j] for i in range(len(verMat))]
        #print(col)
        
        window_left = max(-1, row_i-window_k-1)
        window_right = min(len(col)-1, row_i+window_k)
        
        if window_left == -1: 
            return col[window_right]
        
        return col[window_right] - col[window_left]

    
    # O(1) operation 
    def sumRowWindow(self, sumMat, row_i, col_j, window_k): 
        row = sumMat[row_i]
        
        window_left = max(-1, col_j-window_k-1)
        window_right = min(len(row)-1, col_j+window_k)
        
        if window_left == -1: 
            return row[window_right]
        
        return row[window_right] - row[window_left]
        


class Solution:
    def matrixBlockSum(self, mat: List[List[int]], K: int) -> List[List[int]]:
        h, w = len(mat), len(mat[0])
        
        dp = [[0 for i in range(w)] for j in range(h)]
        for y in range(h):
            for x in range(w):
                sum = 0
                for i in range(x - K if x - K >= 0 else 0, x + K + 1 if x + K + 1 <= w else w):
                    sum += mat[y][i]
                dp[y][x] = sum
        
        res = [[0 for i in range(w)] for j in range(h)]
        for y in range(h):
            for x in range(w):
                sum = 0
                for j in range(y - K if y - K >= 0 else 0, y + K + 1 if y + K + 1 <= h else h):
                    sum += dp[j][x]
                res[y][x] = sum
                
        return res

import numpy as np
class Solution:
    def matrixBlockSum(self, mat: List[List[int]], k: int) -> List[List[int]]:
        ans = [[0 for i in range(len(mat[0]))] for j in range(len(mat))]
        print(ans)
        mat = np.array(mat)
        for i in range(len(mat)):
            for j in range(len(mat[0])):
                a = i - k if i - k >= 0 else 0
                b = i + k if i + k <= len(mat) else len(mat)
                c = j - k if j - k >= 0 else 0
                d = j + k if j + k <= len(mat[0]) else len(mat[0])
                ans[i][j] = np.sum(mat[a : b + 1, c : d + 1])
        return ans
        


class Solution:
    def matrixBlockSum(self, mat: List[List[int]], K: int) -> List[List[int]]:
        k = K
        n, m = len(mat), len(mat[0])
        matrix = []
        for i in range(n):
            temp = []
            for  j in range(m):
                temp.append(0)
            matrix.append(temp)
        
        for i in range(n):
            for j in range(m):
                if i == 0 and j == 0:
                    summ = 0
                    for o in range(min(n, k+1)):
                        for l in range(min(m, k+1)):
                            summ += mat[o][l]
                    matrix[i][j] = summ
                elif j == 0:
                    summ = 0
                    remSumm = 0
                    for l in range(min(m, k+1)):
                        if i+k <= n-1:
                            summ += mat[i+k][l]
                        if i-k-1>= 0:
                            remSumm += mat[i-k-1][l]
                    matrix[i][j] = matrix[i-1][j] + summ - remSumm
                else:
                    summ = 0
                    remSumm = 0
                    for l in range(max(0, i-k), min(n, i+k+1)):
                        if j + k <= m-1:
                            summ += mat[l][j+k]
                        if j-k-1 >= 0:
                            remSumm += mat[l][j-k-1]
                    matrix[i][j] = matrix[i][j-1] + summ - remSumm
        return matrix


class Solution:
    def matrixBlockSum(self, mat: List[List[int]], K: int) -> List[List[int]]:
        n = len(mat)
        m = len(mat[0])
        result = [[0 for _ in range(m)] for _ in range(n)]
        for i in range(n):
            for j in range(m):
                if i == 0 and j == 0:
                    for r in range(max(i - K, 0), min(i + K + 1, n)):
                        for c in range(max(j - K, 0), min(j + K + 1, m)):
                            result[i][j] += mat[r][c]
                elif j > 0:
                    prev_c = j - 1
                    result[i][j] += result[i][prev_c]
                    for r in range(max(i - K, 0), min(i + K + 1, n)):
                        if j - K - 1 >= 0:
                            result[i][j] -= mat[r][j - K - 1]
                        if j + K < m:
                            result[i][j] += mat[r][j + K]
                else:
                    prev_r = i - 1
                    result[i][j] += result[prev_r][j]
                    for c in range(max(j - K, 0), min(j + K + 1, m)):
                        if i - K - 1 >= 0:
                            result[i][j] -= mat[i - K - 1][c]
                        if i + K < n:
                            result[i][j] += mat[i + K][c]
        return result

class Solution:
    def matrixBlockSum(self, mat: List[List[int]], K: int) -> List[List[int]]:
        m = len(mat)
        n = len(mat[0])
        
        RangeSum = [[0 for _ in range(n+1)] for _ in range(m+1)]
        
        for i in range(1, m+1):
            for j in range(1, n+1):
                RangeSum[i][j] = RangeSum[i-1][j] + RangeSum[i][j-1] - RangeSum[i-1][j-1] + mat[i-1][j-1]
        
        ans = [[0 for _ in range(n)] for _ in range(m)]
        
        print(RangeSum)
        
        for r in range(m):
            for c in range(n):
                i2 = min(m-1, r+K)
                j2 = min(n-1, c+K)
                i1 = max(0, r-K)
                j1 = max(0, c-K)
                # print(i1, j1, i2, j2)
                ans[r][c] = RangeSum[i2+1][j2+1] - RangeSum[i2+1][j1] - RangeSum[i1][j2+1] + RangeSum[i1][j1]
        
        return ans

import numpy as np

class Solution:

    def matrixBlockSum(self, mat: List[List[int]], K: int) -> List[List[int]]:

        mat_np = np.array(mat)

        M, N = mat_np.shape # same shape with the sum_matrix

        sum_np = np.zeros((M,N), dtype=int)

        

        for m in range(M):

            for n in range(N):

                sum_np[m,n] = np.sum(mat_np[max(0, m-K):min(m+K+1, M+1), 

                                            max(0, n-K):min(n+K+1, N+1)])

                

        return sum_np.tolist()

class Solution:
    def matrixBlockSum(self, mat: List[List[int]], K: int) -> List[List[int]]:
        m, n = len(mat), len(mat[0])
        res = [[0]*n for _ in range(m)]
        
        # vert_slid_win = [0]*(K*2+1)
        # for ii in range(0, K+1):
        #     if ii>=0 and ii<m:
        #         vert_slid_win[ii] = sum([mat[ii][c] for c in range(0, K+1) if c >=0 and c<m])
                    
        for i in range(m):
            
            hori_slid_win = [0]*(K*2+1)
            for jj in range(0, K+1):
                if jj>=0 and jj<n:
                    hori_slid_win[jj+K] = sum([mat[r][jj] for r in range(i - K, i+K+1) if r >=0 and r<m])
                    
            for j in range(n):
                res[i][j] = sum(hori_slid_win)
                hori_slid_win.pop(0)
                if j+K+1< n:
                    hori_slid_win.append(sum([mat[r][j+K+1] for r in range(i - K, i+K+1) if r >=0 and r<m]))
                # print(hori_slid_win)
        return res 

class Solution:
    
    def __init__(self):
        from functools import lru_cache
        return
    
    
    def matrixBlockSum(self, mat: List[List[int]], K: int) -> List[List[int]]:
        self.cache = {}
        k = K
        # 2d kernel
        n, m = len(mat), len(mat[0]) if len(mat) else 0
                        
        @lru_cache
        def kernel(i,j, k):
            minx, maxx = max(i-k,0), min(i+k+1, n)
            miny, maxy = max(j-k,0), min(j+k+1, m)
            s = 0
            
        def getrowsum(i,j,k):
            if i < 0: return 0
            if i >= n: return 0
            miny, maxy = max(j-k,0), min(j+k+1,m)
            return sum([mat[i][jj] for jj in range(miny, maxy)])

        def getcolsum(ans,i,j,k):
            if j < 0: return 0
            if j >= m: return 0
            minx, maxx = max(i-k,0), min(i+k+1,n)
            return sum([ans[ii][j] for ii in range(minx, maxx)])
            
        ans = [[0 for j in range(m)] for i in range(n)]
        for i in range(n):
            for j in range(m):
                ans[i][j] = getrowsum(i,j,k)

        res = [[0 for j in range(m)] for i in range(n)]
        for i in range(n):
            for j in range(m):
                res[i][j] = getcolsum(ans,i,j,k)
        return res

        # brute force
        ans = [[0 for j in range(m)] for i in range(n)]
        for i in range(n):
            for j in range(m):
                ans[i][j] = kernel(i,j, K)
                
        return ans

class Solution:
    def matrixBlockSum(self, mat: List[List[int]], k: int) -> List[List[int]]:
        m, n = len(mat), len(mat[0])
        arr = [[0 for i in range(n+1)] for i in range(m)]
        for i in range(m):
            for j in range(n):
                arr[i][j+1] = arr[i][j] + mat[i][j]

        narr = [[0 for i in range(n)] for i in range(m)]
        for i in range(m):
            for j in range(n):
                x1, x2, y1, y2 = max(0, j-k), min(n-1, j+k), max(0, i-k), min(m-1, i+k)
                a = 0
                for t in range(y1, y2+1):
                    a += arr[t][x2+1]-arr[t][x1]
                narr[i][j] = a
        return narr

class Solution:
    def matrixBlockSum(self, mat: List[List[int]], K: int) -> List[List[int]]:
        rows, cols = len(mat), len(mat[0])
        dic = {}
        for i, row in enumerate(mat):
            prefix_sum = [0] * (cols + 1)
            for j, num in enumerate(row):
                prefix_sum[j] = prefix_sum[j-1] + num
            dic[i] = prefix_sum
       
        for i in range(rows):
            for j in range(cols):
                start_col, end_col = max(j-K, 0), min(j+K, cols-1)
                start_row, end_row = max(i-K, 0), min(i+K, rows-1)
                res = 0
                for idx in range(start_row, end_row+1):
                    res += dic[idx][end_col]- dic[idx][start_col-1]
                mat[i][j] = res
        return mat


import numpy as np

class Solution:
    def matrixBlockSum(self, mat: List[List[int]], K: int) -> List[List[int]]:
        mat = np.array(mat)
        answer = np.zeros(mat.shape)
        for i, row in enumerate(mat):
            row_start = max([0, i - K])
            row_end = min([mat.shape[0], i + K])
            for j, col in enumerate(row):
                col_start = max([0, j - K])
                col_end = min([mat.shape[1], j + K])
                # TODO: 
                answer[i][j] = np.sum(mat[row_start:row_end + 1, col_start:col_end + 1])
        return answer.astype(np.int)
            
            


class Solution:
    
    def __init__(self):
        from functools import lru_cache
        return
    
    
    def matrixBlockSum(self, mat: List[List[int]], K: int) -> List[List[int]]:
        self.cache = {}
        k = K
        n, m = len(mat), len(mat[0]) if len(mat) else 0
                      
        def brute_force():
            def kernel(i, j, k):
                minx, maxx = max(i-k,0), min(i+k+1, n)
                miny, maxy = max(j-k,0), min(j+k+1, m)
                s = 0
                for ii in range(minx, maxx):
                    for jj in range(miny, maxy):
                        s += mat[ii][jj]
                return s

            ans = [[0 for j in range(m)] for i in range(n)]
            for i in range(n):
                for j in range(m):
                    ans[i][j] = kernel(i,j, k)
            return ans
        
        #return brute_force()
            
        
        def partials():
            @lru_cache
            def getrowsum(i,j,k):
                if i < 0: return 0
                if i >= n: return 0
                miny, maxy = max(j-k,0), min(j+k+1,m)
                return sum([mat[i][jj] for jj in range(miny, maxy)])

            #@lru_cache
            def getcolsum(ans,i,j,k):
                if j < 0: return 0
                if j >= m: return 0
                minx, maxx = max(i-k,0), min(i+k+1,n)
                return sum([ans[ii][j] for ii in range(minx, maxx)])

            ans = [[0 for j in range(m)] for i in range(n)]
            for i in range(n):
                for j in range(m):
                    ans[i][j] = getrowsum(i,j,k)

            res = [[0 for j in range(m)] for i in range(n)]
            for i in range(n):
                for j in range(m):
                    res[i][j] = getcolsum(ans,i,j,k)
            return res
        
        return partials()


class Solution:
    def matrixBlockSum(self, mat: List[List[int]], k: int) -> List[List[int]]:
        r, c = len(mat), len(mat[0])
        rsums = [[0] for i in range(r)]
        for i in range(r):
            for j in range(c):
                rsums[i].append(rsums[i][-1]+mat[i][j])
        for i in range(r):
            for j in range(c):
                mat[i][j] = 0
                lr = 0 if i-k < 0 else i-k
                rr = r-1 if i+k >= r else i+k
                lc = 0 if j-k < 0 else j-k
                rc = c-1 if j+k >= c else j+k
                rc += 1
                for x in range(lr, rr+1):
                    mat[i][j] += (rsums[x][rc] - rsums[x][lc])
        return mat

class Solution:
    def matrixBlockSum(self, mat: List[List[int]], K: int) -> List[List[int]]:
        m=len(mat)
        n=len(mat[0])
        answer=[]
        temp=[]
        val,i,j=0,0,0
        for r in range(max(0,i-K),min(i+K+1,m)):
            for c in range(max(0,j-K),min(j+K+1,n)):
                val+=mat[r][c]
        temp.append(val)
        for i in range(m):
            if i==0:
                row=temp
            else:
                row=[]
                r1=i-K-1
                r2=i+K
                subs2,adds2=0,0
                for c in range(max(0,-K),min(K+1,n)):
                    if r1>=0:
                        subs2+=mat[r1][c]
                    if r2<m:
                        adds2+=mat[r2][c]
                row.append(answer[-1][0]+adds2-subs2)
            for j in range(1,n):
                subs,adds=0,0
                c1=j-K-1
                c2=j+K
                for r in range(max(0,i-K),min(i+K+1,m)):
                    if c1>=0:
                        subs+=mat[r][c1]
                    if c2<n:
                        adds+=mat[r][c2]
                row.append(row[-1]+adds-subs)
            answer.append(row)
        return answer

class Solution:
    def matrixBlockSum(self, mat: List[List[int]], K: int) -> List[List[int]]:
        #   积分图
        M = len(mat)
        N = len(mat[0])
        
        if (K) >= (M-1) and (K) >= (N-1):
            t = 0
            for h in mat:
                for w in h:
                    t += w
            rtv = [[t] * N for _ in range(M)]
            return rtv

        def calc(presums, h, w, K):
            h1 = h - K
            h2 = h + K+1
            w1 = w - K
            w2 = w + K+1
            
            w1 = max(w1, 0)
            h1 = max(h1, 0)
            w2 = min(w2, N)
            h2 = min(h2, M)
            
            return presums[h1][w1] + presums[h2][w2] - presums[h1][w2] - presums[h2][w1]
        
        presums = [[0] * (N+1) for _ in range(M+1)]
        
        for h in range(M):
            for w in range(N):
                presums[h+1][w+1] = presums[h+1][w] + presums[h][w+1] - presums[h][w] + mat[h][w]
        
        rtv = [[0] * (N) for _ in range(M)]
        
        for h in range(M):
            for w in range(N):
                rtv[h][w] = calc(presums, h, w, K)
        
        
        return rtv

class Solution:
    def matrixBlockSum(self, mat: List[List[int]], K: int) -> List[List[int]]:
        k = K
        n, m = len(mat), len(mat[0])
        matrix = []
        for i in range(n):
            temp = []
            for  j in range(m):
                temp.append(0)
            matrix.append(temp)
        
        for i in range(n):
            for j in range(m):
                if i == 0 and j == 0:
                    summ = 0
                    for o in range(min(n, k+1)):
                        for l in range(min(m, k+1)):
                            summ += mat[o][l]
                    matrix[i][j] = summ
                elif j == 0:
                    summ = 0
                    remSumm = 0
                    for l in range(min(m, k+1)):
                        if i+k <= n-1:
                            summ += mat[i+k][l]
                        if i-k-1>= 0:
                            remSumm += mat[i-k-1][l]
                    print((i, j, matrix[i-1][j], summ, remSumm))
                    matrix[i][j] = matrix[i-1][j] + summ - remSumm
                else:
                    summ = 0
                    remSumm = 0
                    for l in range(max(0, i-k), min(n, i+k+1)):
                        if j + k <= m-1:
                            summ += mat[l][j+k]
                        if j-k-1 >= 0:
                            remSumm += mat[l][j-k-1]
                    print((i, j, matrix[i][j-1], summ, remSumm))
                    matrix[i][j] = matrix[i][j-1] + summ - remSumm
        return matrix


class Solution:
    def matrixBlockSum(self, mat: List[List[int]], k: int) -> List[List[int]]:
        rows, cols = len(mat), len(mat[0])
        ans = [[0 for _ in range(cols)] for _ in range(rows)]
        
        for i in range(rows):
            for j in range(1, cols):
                mat[i][j] += mat[i][j - 1]
                if i > 0:
                    mat[i][j - 1] += mat[i - 1][j - 1]
            if i > 0:
                mat[i][cols - 1] += mat[i - 1][cols - 1]
        
        for i in range(rows):
            for j in range(cols):
                top, bottom, left, right = i, i, j, j
                
                countT = k
                while top > 0 and countT > 0:
                    top -= 1
                    countT -= 1
                    
                countB = k
                while bottom < rows - 1 and countB > 0:
                    bottom += 1
                    countB -= 1
                
                countL = k
                while left > 0 and countL > 0:
                    left -= 1
                    countL -= 1
                
                countR = k
                while right < cols - 1 and countR > 0:
                    right += 1
                    countR -= 1
                
                ans[i][j] += mat[bottom][right]

                if top - 1 >= 0 and countT == 0:
                    ans[i][j] -= mat[top - 1][right]
                if left - 1 >= 0 and countL == 0:
                    ans[i][j] -= mat[bottom][left - 1]
                if top - 1 >= 0 and left - 1 >= 0 and countT == 0 and countL == 0:
                    ans[i][j] += mat[top - 1][left - 1]
                
        return ans

class Solution:
    def matrixBlockSum(self, mat: List[List[int]], k: int) -> List[List[int]]:
        r, c = len(mat), len(mat[0])
        rsums = [[0] for i in range(r)]
        for i in range(r):
            for j in range(c):
                rsums[i].append(rsums[i][-1]+mat[i][j])
        res = [[0 for i in range(c)] for j in range(r)]
        for i in range(r):
            for j in range(c):
                mat[i][j] = 0
                lr = 0 if i-k < 0 else i-k
                rr = r-1 if i+k >= r else i+k
                lc = 0 if j-k < 0 else j-k
                rc = c-1 if j+k >= c else j+k
                rc += 1
                for x in range(lr, rr+1):
                    mat[i][j] += (rsums[x][rc] - rsums[x][lc])
        return mat

class Solution:
    def matrixBlockSum(self, mat: List[List[int]], K: int) -> List[List[int]]:
        
        row = len(mat)
        col = len(mat[0])
        
        answer = [[0 for i in range(col)] for j in range(row)]
        
        for i in range(row):
            for j in range(1,col):
                # answer[i][j] = self.new_matrix(mat,i,j,K,row,col)
                mat[i][j] = mat[i][j-1]+mat[i][j]
        print(mat)
        
        for i in range(row):
            for j in range(col):
                answer[i][j] = self.new_matrix(mat,i,j,K,row,col)
        return answer
                
    def new_matrix(self,mat,i,j,k,row,col):
        ans = 0 
        new_row_low = i-k
        new_row_high = i + k
        new_col_low = j-k
        new_col_high = j+k
        
        
        while(new_row_low < 0):
            new_row_low +=1
        while(new_row_high > row-1):
            new_row_high -=1
        while(new_col_low < 0):
            new_col_low +=1
        while(new_col_high > col-1):
            new_col_high-=1
        
        
        
        for a in range(new_row_low, new_row_high+1):
            
            ans+= mat[a][new_col_high]
            
            if(new_col_low-1 >= 0):
                
                ans -= mat[a][new_col_low-1]
                
        return ans
                    
            
        
        
        


class Solution:
    def matrixBlockSum(self, mat: List[List[int]], K: int) -> List[List[int]]:
        if not mat or not mat[0]:
            return mat
        R, C = len(mat), len(mat[0])
        l2r = [[0] * C for _ in range(R)]
        t2b = [[0] * C for _ in range(R)]
        
        for r in range(R):
            for c in range(C):
                l2r[r][c] += mat[r][c]
                if c != 0:
                    l2r[r][c] += l2r[r][c-1]
                
                t2b[r][c] += mat[r][c]
                if r != 0:
                    t2b[r][c] += t2b[r-1][c]
        
        ret = [[0] * C for _ in range(R)]
        for r in range(R):
            for c in range(C):
                temp = 0
                left = max(0, c-K)
                right = min(C-1, c+K)
                for _r in range(max(0, r - K), min(R, r+K+1)):
                    if left == 0:
                        temp += l2r[_r][right]
                    else:
                        temp += l2r[_r][right] - l2r[_r][left-1]
                
                ret[r][c] = temp
        
        return ret

import copy
class Solution:    
    def matrixBlockSum(self, mat: List[List[int]], K: int) -> List[List[int]]:
        n_row = len(mat)
        n_column = len(mat[0])        
        
        print(n_row, n_column, K , \"n_row, n_column, K\")
        
        memo = [[0 for _ in range(n_column)] for _ in range(n_row)]
        new_mat = [[0 for _ in range(n_column)] for _ in range(n_row)]
        
        ## column wise memoization    
        if n_row > n_column:        
            for i in range(n_row):
                for j in range(n_column):                    
                    start_row= 0 if i-K <0 else i-K
                    end_row = n_row-1 if i+K > n_row-1 else i+K
                    
                    for r in range(start_row, end_row+1):
                        memo[i][j] +=mat[r][j]                        
        else:
            for i in range(n_row):
                for j in range(n_column):                    
                    start_column= 0 if j-K <0 else j-K
                    end_column = n_column-1 if j+K > n_column-1 else j+K
                    
                    for r in range(start_column, end_column+1):
                        memo[i][j] +=mat[i][r]                                            
                    
        print(len(memo), len(memo[0]), \"n_row , n_columns of memo\")
                        
        ## main calculation
        if n_row > n_column:
            for i in range(n_row):
                for j in range(n_column):    
                    start_column= 0 if j-K <0 else j-K
                    end_column = n_column-1 if j+K > n_column-1 else j+K                    
                    
                    for r in range(start_column, end_column+1):
                        new_mat[i][j] += memo[i][r] 
        else:
            for i in range(n_row):
                for j in range(n_column):
                    start_row= 0 if i-K <0 else i-K
                    end_row = n_row-1 if i+K > n_row-1 else i+K
                    
                    for r in range(start_row, end_row+1):
                        new_mat[i][j] += memo[r][j] 
                    
        return new_mat

import numpy as np

class Solution:
    def matrixBlockSum(self, A, K):
        A = np.array(A)
        m, n = A.shape
        return [[A[max(i-K, 0):i+K+1, max(j-K, 0):j+K+1].sum()
                 for j in range(n)] for i in range(m)]

class Solution:
    def matrixBlockSum(self, mat: List[List[int]], K: int) -> List[List[int]]:
        n, m = len(mat), len(mat[0])

        def blockSum(x, y, vertical=K, horizontal=K):
            s = 0
            for i in range(x - vertical, x + vertical + 1):
                for j in range(y - horizontal, y + horizontal + 1):
                    if 0 <= i < n and 0 <= j < m:
                        s += mat[i][j]
            return s

        result = [[0 for j in range(m)] for i in range(n)]

        for i in range(n):
            result[i][0] = blockSum(0, 0) if i == 0 \\
                else result[i - 1][0] \\
                     + (blockSum(i + K, 0, 0, K) if i < n - K else 0) \\
                     - (blockSum(i - (K + 1), 0, 0, K) if i >= K + 1 else 0)

            for j in range(1, m):
                result[i][j] = result[i][j - 1] \\
                               + (blockSum(i, j + K, K, 0) if j < m - K else 0) \\
                               - (blockSum(i, j - (K + 1), K, 0) if j >= K + 1 else 0)

        return result


class Solution:
    def matrixBlockSum(self, mat: List[List[int]], K: int) -> List[List[int]]:
        #i - K <= r <= i + K
        #[0][0]
        #0 - 1 <= r <= 1
        #   -1 <= r <= 1
        #j - K <= c <= j + K
        #   -1 <= c <= 1
        # => square with x=2
        #a[0][0] = row0+row1+col0+col1
        #        = 1+2=3+4+5 = 12
        
        #k = 1
        #[1][0]
        #1-1=0 <= r <= 2
        #1+2+4+5+7+8=?=27 yes
        
        
        sum_mtx = [[0 for col in range(len(mat[0]))] for row in range( len(mat)) ]
        
        #new matrix that is sum of prev_sum + curr_val
        #[31, 2, 4]
        #[12, 26, 9]
        #=>
        #[31, 33, 37] #curr_sum = left_sum + curr_val
        #[43, 71 84] #1:43+ 2 + 26 = 71 = 
        #                                   71  + 9 + 4 = 84
        #sum_mtx[0][0] = mat[0][0] #don't need
        for row in range(len(mat)):
            #reset each row
            summ = 0
            for col in range(len(mat[0])):
                #left_sum(without the its above_sum) + curr_val
                summ += mat[row][col] #ONLY summing horizontals
                sum_mtx[row][col] = summ
                
                #for !row=0
                if row > 0:
                    #(left_sum* + curr_val + above_sum)
                    sum_mtx[row][col] += sum_mtx[row-1][col]
        #above mtx allows us to just select the 4 idxes instead of having to repeatedly compute the sums of the blocks:a,b,c,d every time
        #print(sum_mtx)
        
        output_img = [[0 for col in range(len(mat[0]))] for row in range( len(mat)) ]
        
        
        for row in range(len(mat)):
            for col in range(len(mat[0])):
                #the \"window\": like a zoom feature
                max_row = min( len(mat)-1, K + row)
                min_row = max( 0       , row - K)
                min_col = max( col - K, 0)
                max_col = min( col + K, len(mat[0])-1)
                a_val, b_val, c_val = 0,0,0
                d_val = sum_mtx[max_row][max_col]
                
                if min_col > 0:
                    c_val = sum_mtx[max_row][min_col-1]
                
                if min_row > 0:
                    b_val = sum_mtx[min_row-1][max_col]
                
                if c_val and b_val: #both exist
                    a_val = sum_mtx[min_row-1][min_col-1]
                
                output_img[row][col] = d_val - b_val - c_val + a_val
        return output_img



import numpy as np
class Solution:
    def matrixBlockSum(self, mat: List[List[int]], K: int) -> List[List[int]]:
        m = len(mat)
        n = len(mat[0])
        if m == 1 and n == 1: return mat
        mat = np.array(mat)        
        ans = np.array([[0 for _ in range(n)] for _ in range(m)])
        ans[0, 0] += mat[:min(m, K+1), :min(n, K+1)].sum()
        for j in range(1, n):
            ans[0, j] = ans[0, j - 1]
            if j + K < n: ans[0, j] += mat[:min(K + 1, m), j + K].sum()
            if j - K > 0: ans[0, j] -= mat[:min(K + 1, m), j - K - 1].sum()
        for i in range(1, m):
            ans[i, 0] = ans[i - 1, 0]
            if i + K < m: ans[i, 0] += mat[i + K, :min(K + 1, n)].sum()
            if i - K > 0: ans[i, 0] -= mat[i - K - 1, :min(K + 1, n)].sum()
        for i in range(1, m):
            for j in range(1, n):
                ans[i, j] = ans[i, j - 1]
                if j + K < n: ans[i, j] += mat[max(0, i - K): min(i + K + 1, m), j + K].sum()
                if j - K > 0: ans[i, j] -= mat[max(0, i - K): min(i + K + 1, m), j - K - 1].sum()
        return ans

class Solution:
    def matrixBlockSum(self, mat: List[List[int]], K: int) -> List[List[int]]:
        import numpy as np
        mat = np.array(mat)
        ans = []
        for i in range(mat.shape[0]):
            temp = []
            for j in range(mat.shape[1]):
                left = 0 if i-K <0 else i-K
                right = i+K+1
                up = 0 if j-K <0 else j-K
                down = j+K+1
                temp.append(np.sum(mat[left:right,up:down]))
            ans.append(temp)
        return(ans)

import numpy as np
class Solution:
    def matrixBlockSum(self, mat: List[List[int]], K: int) -> List[List[int]]:
        # Edge case
        if not mat or not mat[0]:
            return []
        # General case
        mat = np.array(mat)
        m, n = mat.shape
        output = np.zeros((m, n), dtype=np.int)
        for i in range(m):
            for j in range(n):
                rowLB, rowUB = max(0, i - K), min(i + K, m - 1) + 1
                colLB, colUB = max(0, j - K), min(j + K, n - 1) + 1
                output[rowLB: rowUB, colLB: colUB] += mat[i][j] * np.ones((rowUB - rowLB, colUB - colLB), dtype=np.int)
        return output

import numpy as np
class Solution:
    def matrixBlockSum(self, mat: List[List[int]], K: int) -> List[List[int]]:
        n = len(mat)
        m = len(mat[0])
        padded = np.pad(np.asarray(mat), K)
        result = [[0] * m for _ in range(n)]
        for i in range(n):
            for j in range(m):
                result[i][j] = np.sum(padded[i:i + 2 * K + 1, j:j + 2 * K + 1])
        return result

import numpy as np
class Solution:
    def matrixBlockSum(self, mat: List[List[int]], K: int) -> List[List[int]]:
        n = len(mat)
        m = len(mat[0])
        padded = np.pad(np.asarray(mat), K)
        # conv = np.ones(2 * K + 1, 2 * K + 1)
        result = [[0] * m for _ in range(n)]
        # print(padded)
        for i in range(n):
            for j in range(m):
                result[i][j] = np.sum(padded[i:i + 2 * K + 1, j:j + 2 * K + 1])
                # for row in padded[i:i + 2 * K + 1, j:j + 2 * K + 1]:
                    # print(i,j, row, 2 * K)
                # print()
        return result

class Solution:
    def matrixBlockSum(self, mat: List[List[int]], K: int) -> List[List[int]]:
        
        m, n = len(mat), len(mat[0])
        k = K
        row = [[0 for _ in range(n)] for _ in range(m)]
        ans = [[0 for _ in range(n)] for _ in range(m)]
        
        for i in range(m):
            for j in range(n):        
                for r in range(max(0, i-k), min(m, i+k+1)):
                    row[i][j] += mat[r][j]

        
        for i in range(m):
            for j in range(n):
                    for c in range(max(0, j-k), min(n, j+k+1)):
                        ans[i][j] += row[i][c]
        
        return ans

class Solution:
    def matrixBlockSum(self, mat: List[List[int]], K: int) -> List[List[int]]:
        res=[]
        t=[]
        for i in range(len(mat)):
            t.append([0]*len(mat[0]))
            res.append([0]*len(mat[0]))
            for j in range(len(mat[0])):
                t[i][j]=mat[i][j]
                if j>0:
                    mat[i][j]+=mat[i][j-1]
                    
                
        #print(mat,t)
        for i in range(len(mat)):
            for j in range(len(mat[0])):
                s = 0
                top = i-K
                bot = i+K
                left = j-K
                if left<0: left =0
                right = j+K
                if right>=len(mat[0]):
                    right=len(mat[0])-1
                for k in range(top,bot+1):
                    if k>=0 and k<len(mat):
                        s+=(mat[k][right]-mat[k][left]+t[k][left])
                res[i][j]=s
        return res
                
                


class Solution:
    def matrixBlockSum(self, mat: List[List[int]], K: int) -> List[List[int]]:
        cumMat = [[0 for _ in range(len(mat[0]) + 2)] for _ in range(len(mat) + 2)]
        cumMat[1][1] = mat[0][0]
        for i in range(2, len(mat) + 1):
            cumMat[i][1] = mat[i - 1][0] + cumMat[i - 1][1]
        for j in range(2, len(mat[0]) + 1):
            cumMat[1][j] = mat[0][j - 1] + cumMat[1][j - 1]
        for i in range(2, len(mat) + 1):
            for j in range(2, len(mat[0]) + 1):
                cumMat[i][j] = mat[i - 1][j - 1] + cumMat[i - 1][j] + cumMat[i][j - 1] - cumMat[i - 1][j - 1]
          
        answer = [[0 for _ in mat[0]] for _ in mat]
        for i in range(1, len(cumMat) - 1):
            for j in range(1, len(cumMat[0]) - 1):
                i1 = max(1, i - K)
                i2 = min(len(cumMat) - 2, i + K)
                j1 = max(1, j - K)
                j2 = min(len(cumMat[0]) - 2, j + K)
                # print(i1)
                # print(j1)
                # print(i2)
                # print(j2)
                answer[i - 1][j - 1] = cumMat[i2][j2] - cumMat[i1 - 1][j2] - cumMat[i2][j1 - 1] + cumMat[i1 - 1][j1 - 1]
                print(answer[i - 1][j - 1])
        return answer

class Solution:
    def matrixBlockSum(self, mat: List[List[int]], K: int) -> List[List[int]]:
        res=[]
        t=[]
        for i in range(len(mat)):
            t.append([0]*len(mat[0]))
            for j in range(len(mat[0])):
                t[i][j]=mat[i][j]
        for i in range(len(mat)):
            res.append([0]*len(mat[0]))
            t.append([0]*len(mat[0]))
            for j in range(1,len(mat[0])):
                
                mat[i][j]+=mat[i][j-1]
                
        #print(mat,t)
        for i in range(len(mat)):
            for j in range(len(mat[0])):
                s = 0
                top = i-K
                bot = i+K
                left = j-K
                if left<0: left =0
                right = j+K
                if right>=len(mat[0]):
                    right=len(mat[0])-1
                #print(left,right)
                for k in range(top,bot+1):
                    if k>=0 and k<len(mat):
                        s+=(mat[k][right]-mat[k][left]+t[k][left])
                        #print(s)
                res[i][j]=s
        return res
                
                


class Solution:
    def matrixBlockSum(self, mat: List[List[int]], k: int) -> List[List[int]]:
        r, c = len(mat), len(mat[0])
        rsums = [[0] for i in range(r)]
        for i in range(r):
            for j in range(c):
                rsums[i].append(rsums[i][-1]+mat[i][j])
        #for i in rsums:
        #    print(*i)
        res = [[0 for i in range(c)] for j in range(r)]
        for i in range(r):
            for j in range(c):
                mat[i][j] = 0
                lr = 0 if i-k < 0 else i-k
                rr = r-1 if i+k >= r else i+k
                lc = 0 if j-k < 0 else j-k
                rc = c-1 if j+k >= c else j+k
                rc += 1
                #print((i,j),lr,rr,lc,rc)
                for x in range(lr, rr+1):
                    mat[i][j] += (rsums[x][rc] - rsums[x][lc])
        return mat


class Solution:
    def matrixBlockSum(self, mat: List[List[int]], K: int) -> List[List[int]]:
        m,n = len(mat), len(mat[0])
        ans = [[0] *n for i in range(m)]
        
        def in_range(i,j):
            return i>=0 and i<m and j>=0 and j<n
        
        ans[0][0] = sum([mat[i][j] for i in range(0,K+1) for j in range(0,K+1) if in_range(i,j)])
        
        for r in range(1,m):
            add = sum([mat[r+K][j] for j in range(0,K+1) if r+K<m and j<n])
            sub = sum([mat[r-K-1][j] for j in range(0,K+1) if r-K-1>=0 and j<n])
            ans[r][0] = ans[r-1][0] + add - sub
            
        for r in range(0,m):
            for c in range(1,n):
                add = sum([mat[i][c+K] for i in range(r-K, r+K+1) if i>=0 and i<m and c+K<n])
                sub = sum([mat[i][c-K-1] for i in range(r-K, r+K+1) if i>=0 and i<m and c-K-1>=0])
                ans[r][c] = ans[r][c-1] + add - sub
        
        return ans                   


class Solution:
    def matrixBlockSum(self, mat: List[List[int]], K: int) -> List[List[int]]:
        dp = []
        result = []
        for y in range(len(mat)):
            dp.append([])
            s = 0
            for x in range(len(mat[y])):
                s += mat[y][x]
                dp[y].append(s)
        
        for y in range(len(mat)):
            result.append([])
            for x in range(len(mat[y])):    
                cur = 0
                for y1 in range(max(y-K, 0), min(y+K+1, len(mat))):
                    if x-K-1 >=0:
                        cur -= dp[y1][x-K-1]
                    cur += (dp[y1][len(mat[y1])-1] if x+K >= len(mat[y1]) else dp[y1][x+K])
                result[y].append(cur)                
        return result

class Solution:
    def matrixBlockSum(self, mat: List[List[int]], K: int) -> List[List[int]]:
        import numpy as np
        from scipy.signal import convolve2d
        mat = np.array(mat, dtype = int)
        convolution = np.ones((2 * K + 1, 2 * K + 1), dtype = int)
        mat = convolve2d(mat, convolution, 'same')
        return mat

class Solution:
    def matrixBlockSum(self, mat: List[List[int]], K: int) -> List[List[int]]:
        from numpy import array, ones
        from scipy.signal import convolve2d
        
        mat = array(mat, dtype = int)
        convolution = ones((2 * K + 1, 2 * K + 1), dtype = int)
        mat = convolve2d(mat, convolution, 'same')
        
        return mat

class Solution:
    def matrixBlockSum(self, mat: List[List[int]], K: int) -> List[List[int]]:
        
        
        def getSum(i,j):
            ii = max(i-K, 0)
            s = 0
            while ii <= min(i+K, len(mat)-1):
                jj = max(j-K, 0)
                while jj <= min(j+K, len(mat[0])-1):
                    s += mat[ii][jj]
                    jj += 1
                ii += 1
            return s
        
        def editCol(i,j, s):
            if j-K-1 >= 0:
                ii = max(i-K, 0)
                while ii <= min(i+K, len(mat)-1):
                    s -= mat[ii][j-K-1]
                    ii += 1
            if j+K < len(mat[0]):
                ii = max(i-K, 0)
                while ii <= min(i+K, len(mat)-1):
                    s += mat[ii][j+K]
                    ii += 1
            return s
            
        rett = []
        for i in range(len(mat)):
            s = getSum(i,0)
            ret = [s]
            for j in range(1,len(mat[i])):
                s = editCol(i,j, s)
                ret.append(s)
            rett.append(ret)
        return rett

class Solution:
    def matrixBlockSum(self, mat: List[List[int]], K: int) -> List[List[int]]:
        cum = [[0 for i in range(len(mat[0]))] for i in range(len(mat)) ] 
        for i in range(len(mat)):
            for j in range(len(mat[i])):
                if j==0:
                    cum[i][j] = mat[i][j]
                else:
                    cum[i][j] = cum[i][j-1] + mat[i][j]
        
        ans = [[0 for i in range(len(mat[0]))] for i in range(len(mat)) ]
        
        # print(cum)
        
        for i in range(len(mat)):
            for j in range(len(mat[0])):
                summ = 0
                for k in range(max(0,i-K),min(len(mat),i+K+1)):
                    if(j-K-1<0):
                        summ += cum[k][min(j+K,len(cum[i])-1)]
                    else:
                        # print(k, len(cum[k]))
                        summ += cum[k][min(j+K,len(cum[k])-1)] 
                        summ -= cum[k][j-K-1] 
                ans[i][j] = summ
        print(ans)
        return ans