It's Diwali time and you are on a tour of Codepur, a city consisting of buildings of equal length and breadth because they were designed by a computer architect with a bit of OCD.
The ruling party of Codepur wants to have a blockbuster Diwali celebration but lack enough funds and decided to open a donation channel called Codepur Cares Fund (CCF). So they decided to run a survey.
Each building eihter has permanent donors, whose impact value is represented as a positive integer, or potential donors, whose impact value is represented by negative integers.
Overwhelmed by the response, and sticking to their resource optimized philosophy, they decided to hire you to determine the contiguous buildings which are allowed to donate to CCF with the following rule:
The contiguous buildings / areas with the maximum sum impact shall be allowed for donating to Codepur Cares Fund (CCF).
Help them out to get a stunning Diwali bonus and rest of your trip sponsered!

-----Input:-----
The first line consists of two tab spaced integers m and n, indicating number of rows and columns respectively in the Codepur's city plan (which is a 2-D Matrix).
The next $m$ lines consist of $n$ tab spaced integers $ti$ indicating rows in the matrix.

-----Output:-----
Print the bulidings (represented by their donors numbers) which are eligible to donate to CCF (i.e, have the largest sum contiguously) as a 2-D matrix with the elements being tab-spaced.

-----Constraints-----
- $0 \leq m,n \leq 10^{15}$
- $-10^{15} \leq ti \leq 10^5$

-----Sample Input:-----
6    5
0    -2    -7    0    -1
9    2    -6    2    0
-4    1    -4    1    0
-1    8    0    -2    1
-10    1    1    -5    6
-15    -1    1    5    -4

-----Sample Output:-----
9    2
-4    1
-1    8

Source: codechef | Difficulty: UNKNOWN_DIFFICULTY


Solutions:
import sys
input = sys.stdin.readline
(inp, ip) = (lambda : int(input()), lambda : [int(w) for w in input().split()])

def kadane(arr, start, finish, n):
	Sum = 0
	maxSum = float('-inf')
	i = None
	finish[0] = -1
	local_start = 0
	for i in range(n):
		Sum += arr[i]
		if Sum < 0:
			Sum = 0
			local_start = i + 1
		elif Sum > maxSum:
			maxSum = Sum
			start[0] = local_start
			finish[0] = i
	if finish[0] != -1:
		return maxSum
	maxSum = arr[0]
	start[0] = finish[0] = 0
	for i in range(1, n):
		if arr[i] > maxSum:
			maxSum = arr[i]
			start[0] = finish[0] = i
	return maxSum

def findMaxSum(M):
	nonlocal ROW, COL
	(maxSum, finalLeft) = (float('-inf'), None)
	(finalRight, finalTop, finalBottom) = (None, None, None)
	(left, right, i) = (None, None, None)
	temp = [None] * ROW
	Sum = 0
	start = [0]
	finish = [0]
	for left in range(COL):
		temp = [0] * ROW
		for right in range(left, COL):
			for i in range(ROW):
				temp[i] += M[i][right]
			Sum = kadane(temp, start, finish, ROW)
			if Sum > maxSum:
				maxSum = Sum
				finalLeft = left
				finalRight = right
				finalTop = start[0]
				finalBottom = finish[0]
	for i in range(finalTop, finalBottom + 1):
		print(*M[i][finalLeft:finalRight + 1])
(ROW, COL) = ip()
M = [ip() for i in range(ROW)]
findMaxSum(M)