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

Difficulty: interview

Starter code:

Solutions:
#dt = {} for i in x: dt[i] = dt.get(i,0)+1
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)