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: MEDIUM
Tags: Matrices

Data structures

Range queries
Skill types: Data structures

Range queries

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]]:
		(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)]
		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]
		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):
				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)
				elif i == 0:
					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:
					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)
		(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)]
				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]
					ans[i][j] += sum
		return ans


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]]:
		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


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)]
		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]]:
		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])):
				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])):
				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


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


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])
					elif 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 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
			for row in mat[x1:x2 + 1]:
				sumi += sum(row[y1:y2 + 1])
			return sumi
		newmat = [[0] * len(row) for row in mat]
		for (ri, row) in enumerate(mat):
			for (ci, i) in enumerate(row):
				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 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])
					elif 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)
				s = 0
				for i2 in range(r_low, min(r_high + 1, m)):
					s += sum(mat[i2][c_low:c_high + 1])
				print((i, j, n, m))
				out[i][j] = s
		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())
		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 = []
		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 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]
		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]]:
		(N, M) = (len(mat), len(mat[0]))
		ans = [[0] * M for i in range(N)]

		def getBlockSum(i, j):
			rows = mat[max(0, i - K):i + K + 1]
			block = list(zip(*rows))[max(0, j - K):j + K + 1]
			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


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)])
				this.append(add)
			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]
		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)
		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])):
				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))
				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)
		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)]
		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]]:
		ans = []
		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])):
				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])
		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
				for k in range(r_min, r_max):
					for l in range(c_min, c_max):
						val += mat[k][l]
				res_list.append(val)
			res_mat.append(res_list)
		return res_mat


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]]:
		(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

		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]]:
		(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, K):
		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]
		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]]:
		if not mat:
			self.cum_matrix = [[]]
		else:
			nrow = len(mat)
			ncol = len(mat[0])
			self.cum_matrix = [[0] * ncol for _ in range(nrow)]
			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


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))])
		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))])
		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))])
		return ans


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]]:
		N = len(mat)
		M = len(mat[0])
		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]
				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


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]
			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)
		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 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]]:
		if not mat or not mat[0]:
			return mat
		answer = [[0 for _ in mat[0]] for _ in mat]
		for i in range(len(mat)):
			for j in range(1, len(mat[0])):
				mat[i][j] += mat[i][j - 1]
		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])
			if i > 0:
				col_start = 0
				col_end = min([mat.shape[1] - 1, K])
				val = answer[i - 1][0]
				if i + K <= mat.shape[0] - 1:
					val += np.sum(mat[row_end, col_start:col_end + 1])
				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:
					if j + K <= mat.shape[1] - 1 and j != 0:
						val += np.sum(mat[row_start:row_end + 1, col_end])
					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)


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)
				lrj = min(width - 1, j + K)
				uli = i - K - 1
				ulj = j - K - 1
				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)
				else:
					hor_s = slice(j - K, j + K + 1)
				if i - K < 0:
					ver_s = slice(0, i + K + 1)
				else:
					ver_s = slice(i - K, i + K + 1)
				arr[i, j] = mat[ver_s, hor_s].sum()
		return arr.tolist()


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):
			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):
				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


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)]
		for i in range(m):
			running_sum = 0
			for j in range(n):
				running_sum += mat[i][j]
				sumMat[i][j] = running_sum
		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)
		return fnlMat

	def sumColWindow(self, verMat, row_i, col_j, window_k):
		col = [verMat[i][col_j] for i in range(len(verMat))]
		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]

	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)
				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
		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)]
		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]))
		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)

		@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
		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


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]]:
		(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]]:
		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):
				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


class Solution:

	def matrixBlockSum(self, mat: List[List[int]], K: int) -> List[List[int]]:
		sum_mtx = [[0 for col in range(len(mat[0]))] for row in range(len(mat))]
		for row in range(len(mat)):
			summ = 0
			for col in range(len(mat[0])):
				summ += mat[row][col]
				sum_mtx[row][col] = summ
				if row > 0:
					sum_mtx[row][col] += sum_mtx[row - 1][col]
		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])):
				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:
					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]]:
		if not mat or not mat[0]:
			return []
		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


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]
		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)
				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]]:
		(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]]:

		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))]
		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:
						summ += cum[k][min(j + K, len(cum[k]) - 1)]
						summ -= cum[k][j - K - 1]
				ans[i][j] = summ
		print(ans)
		return ans