An army of n droids is lined up in one row. Each droid is described by m integers a_1, a_2, ..., a_{m}, where a_{i} is the number of details of the i-th type in this droid's mechanism. R2-D2 wants to destroy the sequence of consecutive droids of maximum length. He has m weapons, the i-th weapon can affect all the droids in the army by destroying one detail of the i-th type (if the droid doesn't have details of this type, nothing happens to it). 

A droid is considered to be destroyed when all of its details are destroyed. R2-D2 can make at most k shots. How many shots from the weapon of what type should R2-D2 make to destroy the sequence of consecutive droids of maximum length?


-----Input-----

The first line contains three integers n, m, k (1 ≤ n ≤ 10^5, 1 ≤ m ≤ 5, 0 ≤ k ≤ 10^9) — the number of droids, the number of detail types and the number of available shots, respectively.

Next n lines follow describing the droids. Each line contains m integers a_1, a_2, ..., a_{m} (0 ≤ a_{i} ≤ 10^8), where a_{i} is the number of details of the i-th type for the respective robot.


-----Output-----

Print m space-separated integers, where the i-th number is the number of shots from the weapon of the i-th type that the robot should make to destroy the subsequence of consecutive droids of the maximum length.

If there are multiple optimal solutions, print any of them. 

It is not necessary to make exactly k shots, the number of shots can be less.


-----Examples-----
Input
5 2 4
4 0
1 2
2 1
0 2
1 3

Output
2 2

Input
3 2 4
1 2
1 3
2 2

Output
1 3



-----Note-----

In the first test the second, third and fourth droids will be destroyed. 

In the second test the first and second droids will be destroyed.

Difficulty: interview

Starter code:

Solutions:
n,m,k = map(int, input().split())
mCnt = 0
ans = [0]*m
start = 0
end = 0
Q = [[] for i in range(m)]

for i in range(n):
    A = list(map(int, input().split()))
    z = 0
    for j in range(m) :
        while Q[j] and Q[j][-1][0] < A[j] :
            Q[j].pop()
        Q[j].append([A[j],i])
        z += Q[j][0][0]
    if z <= k :
        end = i+1
        if mCnt < end - start :
            mCnt = end - start
            for j in range(m) :
                ans[j] = Q[j][0][0]
    else :
        while True :
            z = 0
            for j in range(m) :
                if Q[j] and Q[j][0][1] == start :
                    Q[j].pop(0)
                if Q[j] : z += Q[j][0][0]
            start += 1
            if z<= k : break
        end += 1
            
for i in ans :
    print(i, end = " ")
    













    


n,m,k = map(int, input().split())
mCnt = 0
ans = [0]*m
start = 0
end = 0
Q = [[] for i in range(m)]

for i in range(n):
    A = list(map(int, input().split()))
    z = 0
    for j in range(m) :
        while Q[j] and Q[j][-1][0] < A[j] :
            Q[j].pop()
        Q[j].append([A[j],i])
        z += Q[j][0][0]
    if z <= k :
        end = i+1
        if mCnt < end - start :
            mCnt = end - start
            for j in range(m) :
                ans[j] = Q[j][0][0]
    else :
        while True :
            z = 0
            for j in range(m) :
                if Q[j] and Q[j][0][1] == start :
                    Q[j].pop(0)
                if Q[j] : z += Q[j][0][0]
            start += 1
            if z<= k : break
        end += 1
            
for i in ans :
    print(i, end = " ")

n,m,k=map(int,input().split())
q=0
rez=[0]*int(m)
st=0
end=0
p=[[] for i in range(int(m))]
for i in range(int(n)):
        a=list(map(int,input().split()))
        c=0
        for ii in range(m):
            while p[ii] and p[ii][-1][0]<a[ii]:
                p[ii].pop()
            p[ii].append([a[ii],i])
            c+=p[ii][0][0]
        if c<=k:
            end=i+1
            if q<end-st:
                q=end-st
                for iii in range(m):
                    rez[iii]=p[iii][0][0]
        else:
            while 1==1:
                c=0
                for j in range(m):
                    if p[j] and p[j][0][1]==st:
                        p[j].pop(0)
                    if p[j]:c+=p[j][0][0]
                st+=1
                if c<=k:
                    break
            end+=1
for i in rez:
    print(i,end= " ")

from itertools import tee
from sys import setrecursionlimit
from sys import stdin
setrecursionlimit(1000000007)
_data = iter(stdin.read().split('\n'))
def input():
    return next(_data)

class SegTree:
    def __init__(self, n, zero, f):
        while n & (n - 1):
            n -= n & -n
        self.n = 2 * n
        self.zero = zero
        self.f = f
        self.t = [self.zero for _ in range(2 * self.n - 1)]

    def __getitem__(self, k):
        return self.t[k + self.n - 1]

    def __setitem__(self, k, v):
        k += self.n - 1
        self.t[k] = v
        while k > 0:
            k = (k - 1) >> 1
            self.t[k] = self.f(self.t[2 * k + 1], self.t[2 * k + 2])

    def query(self, a, b):
        ans = self.zero
        t1 = [0]
        t2 = [0]
        t3 = [self.n]
        while t1:
            k, l, r = t1.pop(), t2.pop(), t3.pop()
            if b <= l or r <= a:
                continue
            elif a <= l and r <= b:
                ans = self.f(self.t[k], ans)
            else:
                t1.append(2 * k + 1), t2.append(l), t3.append((l + r) >> 1)
                t1.append(2 * k + 2), t2.append((l + r) >> 1), t3.append(r)
        return ans

n, m, k = [int(x) for x in input().split()]
st = tuple(SegTree(n, 0, max) for _ in range(m))
rv = -1
rt = (0,) * m
p = 0
t = [0] * m
for i in range(n):
    a = tuple(int(x) for x in input().split())
    for j in range(m):
        st[j][i] = a[j]
        t[j] = max(t[j], a[j])
    while sum(t) > k:
        p += 1
        for j in range(m):
            t[j] = st[j].query(p, i + 1)
    if rv < (i + 1) - p:
        rv = (i + 1) - p
        rt = tuple(t)
print(*rt)

from heapq import heappush, heappop
from sys import setrecursionlimit
from sys import stdin
from collections import defaultdict
setrecursionlimit(1000000007)
_data = iter(stdin.read().split('\n'))
def input():
    return next(_data)

n, m, k = [int(x) for x in input().split()]
a = tuple(tuple(-int(x) for x in input().split()) for i in range(n))
heaps = tuple([0] for _ in range(m))
removed = tuple(defaultdict(int) for _ in range(m))

rv = -1
rt = (0,) * m
p = 0
for i in range(n):
    ai = a[i]
    for j in range(m):
        heappush(heaps[j], ai[j])
    while -sum(heaps[j][0] for j in range(m)) > k:
        ap = a[p]
        for j in range(m):
            removed[j][ap[j]] += 1
            while heaps[j][0] in removed[j]:
                top = heappop(heaps[j])
                removed[j][top] -= 1
                if removed[j][top] == 0:
                   del removed[j][top]
                assert(heaps[j])
        p += 1
    t = tuple(heaps[j][0] for j in range(m))
    if rv < (i + 1) - p:
        rv = (i + 1) - p
        rt = t
print(*map(lambda x: -x, rt))

from heapq import heappush, heappop
from sys import setrecursionlimit
from sys import stdin
from collections import defaultdict
setrecursionlimit(1000000007)
_data = iter(stdin.read().split('\n'))
def input():
    return next(_data)

n, m, k = [int(x) for x in input().split()]
a = tuple(tuple(-int(x) for x in input().split()) for i in range(n))
heaps = tuple([0] for _ in range(m))
removed = tuple(defaultdict(int) for _ in range(m))

rv = -1
rt = (0,) * m
t = [0] * m
p = 0
for i in range(n):
    ai = a[i]
    for j, v, heap in zip(range(m), ai, heaps):
        heappush(heap, v)
        t[j] = heap[0]
    while -sum(t) > k:
        ap = a[p]
        for j, v, heap, remd in zip(range(m), ap, heaps, removed):
            remd[v] += 1
            while heap[0] in remd:
                top = heappop(heap)
                if remd[top] == 1:
                   del remd[top]
                else:
                    remd[top] -= 1
            t[j] = heap[0]
        p += 1
    if rv < (i + 1) - p:
        rv = (i + 1) - p
        rt = tuple(t)
print(*map(lambda x: -x, rt))

from heapq import heappush, heappop
from sys import setrecursionlimit
from sys import stdin
from collections import defaultdict
setrecursionlimit(1000000007)
_data = iter(stdin.read().split('\n'))
def input():
    return next(_data)

n, m, k = [int(x) for x in input().split()]
a = tuple(tuple(-int(x) for x in input().split()) for i in range(n))
heaps = tuple([0] for _ in range(m))
removed = tuple(defaultdict(int) for _ in range(m))

rv = -1
rt = (0,) * m
t = [0] * m
p = 0
for i in range(n):
    ai = a[i]
    for j, v, heap in zip(range(m), ai, heaps):
        heappush(heap, v)
        t[j] = heap[0]
    while -sum(t) > k:
        ap = a[p]
        for j, v, heap, remd in zip(range(m), ap, heaps, removed):
            remd[v] += 1
            while heap[0] in remd:
                top = heappop(heap)
                if remd[top] == 1:
                   del remd[top]
                else:
                    remd[top] -= 1
            t[j] = heap[0]
        p += 1
    if rv < (i + 1) - p:
        rv = (i + 1) - p
        rt = tuple(t)
print(*map(lambda x: -x, rt))

from heapq import heappush, heappop
from sys import setrecursionlimit
from sys import stdin
setrecursionlimit(1000000007)
_data = iter(stdin.read().split('\n'))
def input():
    return next(_data)

n, m, k = [int(x) for x in input().split()]
a = tuple(tuple(-int(x) for x in input().split()) for i in range(n))
heaps1 = tuple([0] for _ in range(m))
heaps2 = tuple([1] for _ in range(m))

rv = -1
rt = (0,) * m
t = [0] * m
p = 0
for i in range(n):
    ai = a[i]
    for j, v, heap1 in zip(range(m), ai, heaps1):
        heappush(heap1, v)
        t[j] = heap1[0]
    while -sum(t) > k:
        ap = a[p]
        for j, v, heap1, heap2 in zip(range(m), ap, heaps1, heaps2):
            heappush(heap2, v)
            while heap1[0] == heap2[0]:
                heappop(heap1)
                heappop(heap2)
            t[j] = heap1[0]
        p += 1
    if rv < (i + 1) - p:
        rv = (i + 1) - p
        rt = tuple(t)
print(*map(lambda x: -x, rt))

from heapq import heappush, heappop
from sys import setrecursionlimit
from sys import stdin
setrecursionlimit(1000000007)
_data = iter(stdin.read().split('\n'))
def input():
    return next(_data)

n, m, k = [int(x) for x in input().split()]
a = tuple(tuple(-int(x) for x in input().split()) for i in range(n))
heaps1 = tuple([0] for _ in range(m))
heaps2 = tuple([1] for _ in range(m))

rv = -1
rt = (0,) * m
t = [0] * m
p = 0
for i in range(n):
    ai = a[i]
    for j, v, heap1 in zip(range(m), ai, heaps1):
        heappush(heap1, v)
        t[j] = heap1[0]
    while -sum(t) > k:
        ap = a[p]
        for j, v, heap1, heap2 in zip(range(m), ap, heaps1, heaps2):
            heappush(heap2, v)
            while heap1[0] == heap2[0]:
                heappop(heap1)
                heappop(heap2)
            t[j] = heap1[0]
        p += 1
    if rv < (i + 1) - p:
        rv = (i + 1) - p
        rt = tuple(t)
print(*map(lambda x: -x, rt))

#!/usr/bin/env python
# coding=utf-8

n, m, k = map(int, input().split())
mCnt = 0;
ans = [0] * m;
start = 0
end = 0
Q = [[] for i in range(m)]
for i in range(n):
    A = list(map(int, input().split()))
    z = 0
    for j in range(m):
        while Q[j] and Q[j][-1][0] < A[j]:
            Q[j].pop()
        Q[j].append([A[j], i])
        z += Q[j][0][0]
    if z <= k:
        end = i + 1
        if mCnt < end - start:
            mCnt = end - start
            for j in range(m):
                ans[j] = Q[j][0][0]
    else:
        while True:
            z = 0
            for j in range(m):
                if Q[j] and Q[j][0][1] == start:
                    Q[j].pop(0)
                if Q[j]: z += Q[j][0][0]
            start += 1
            if z <= k : break;
        end += 1
for i in ans:
    print(i, end = " ")


import sys
from math import *
from bisect import *
from copy import *
MAX = sys.maxsize
MAXN = 10**5+10
logT = [0]*(MAXN)

def arrIN(x = ' '):
    return list(map(int,sys.stdin.readline().strip().split(x)))
for i in range(2,MAXN):
    logT[i] = logT[i//2]+1

def buildSparse(a):
    n = len(a)
    k = logT[n]+1
    st = [[-MAX for j in range(k)] for i in range(n)]
    for i in range(n):
        st[i][0] = a[i]
    j = 1
    while (1<<j)<=n:
        i = 0
        while (i+(1<<j)-1)<n:
            st[i][j] = max(st[i][j-1],st[i+(1<<(j-1))][j-1])
            i+=1
        j+=1
    return st

def query(l,r,st):
    if l>r:
        return -MAX
    tot = r-l+1
    k = logT[tot]
    return max(st[l][k],st[l+tot-(1<<k)][k])

n,m,k = arrIN()
temp = [[0] for _ in range(m)]
for _ in range(n):
    x = arrIN()
    for i in range(m):
        temp[i].append(x[i])

st = []
for i in range(m):
    st.append(buildSparse(temp[i]))

lo = 1
hi = n
t = [0]*m
ans = [0]*m
while lo<=hi:
    mid = (lo+hi)//2
    i = 1
    f = 0
    while i+mid-1<=n:
        for j in range(m):
            t[j] = query(i,i+mid-1,st[j])
        res = sum(t)
        if res<=k:
            ans = deepcopy(t)
            f = 1
            break
        i+=1
    if f:
        lo = mid+1
    else:
        hi = mid-1
print(*ans)





import sys
from math import *
from bisect import *
from copy import *
MAX = sys.maxsize
MAXN = 10**5+10
logT = [0]*(MAXN)

def arrIN(x = ' '):
    return list(map(int,sys.stdin.readline().strip().split(x)))
for i in range(2,MAXN):
    logT[i] = logT[i//2]+1

def buildSparse(a):
    n = len(a)
    k = logT[n]+1
    st = [[-MAX for j in range(k)] for i in range(n)]
    for i in range(n):
        st[i][0] = a[i]
    j = 1
    while (1<<j)<=n:
        i = 0
        while (i+(1<<j)-1)<n:
            st[i][j] = max(st[i][j-1],st[i+(1<<(j-1))][j-1])
            i+=1
        j+=1
    return st

def query(l,r,st):
    if l>r:
        return -MAX
    tot = r-l+1
    k = logT[tot]
    return max(st[l][k],st[l+tot-(1<<k)][k])

n,m,k = arrIN()
temp = [[0] for _ in range(m)]
for _ in range(n):
    x = arrIN()
    for i in range(m):
        temp[i].append(x[i])

st = []
for i in range(m):
    st.append(buildSparse(temp[i]))

lo = 1
hi = n
t = [0]*m
ans = [0]*m
while lo<=hi:
    mid = (lo+hi)//2
    i = 1
    f = 0
    while i+mid-1<=n:
        for j in range(m):
            t[j] = query(i,i+mid-1,st[j])
        res = sum(t)
        if res<=k:
            ans = deepcopy(t)
            f = 1
            break
        i+=1
    if f:
        lo = mid+1
    else:
        hi = mid-1
print(*ans)

from bisect import bisect_left as bl
from bisect import bisect_right as br
import heapq
import math
from collections import *
from functools import reduce,cmp_to_key
import sys
input = sys.stdin.readline
 
# M = mod = 998244353
# def factors(n):return sorted(set(reduce(list.__add__, ([i, n//i] for i in range(1, int(n**0.5) + 1) if n % i == 0))))
# def inv_mod(n):return pow(n, mod - 2, mod)
 
def li():return [int(i) for i in input().rstrip('\n').split()]
def st():return input().rstrip('\n')
def val():return int(input().rstrip('\n'))
def li2():return [i for i in input().rstrip('\n').split(' ')]
def li3():return [int(i) for i in input().rstrip('\n')]

def givediff(a,b):
    return sum(max(i,j) for i,j in zip(b,a))

n, m, k = li()
l = []
for i in range(n):l.append(li())





l1 = [deque() for i in range(m)]
for i in range(m):l1[i].append([0,l[0][i]])


i, j = 0, 1
ans = 0
perm = [0]*m if sum(l[0]) > k else l[0][:]

curr = l[0][:]
while j != n:


    for itr in range(m):
        while len(l1[itr]) and l1[itr][-1][-1] <= l[j][itr]:
            l1[itr].pop()
        l1[itr].append([j,l[j][itr]])




    while i < j and givediff(curr,l[j]) > k:
        i += 1
    
        for itr in range(m):
            while l1[itr][0][0] < i:l1[itr].popleft()
            curr[itr] = l1[itr][0][-1]




    for itr in range(m):curr[itr] = l1[itr][0][-1]




    if ans < j - i + 1 and givediff(l[j],curr) <= k:
        ans = j - i + 1
        perm = [max(a,b) for a,b in zip(l[j],curr)]

    j += 1
    # print(l1,'\n\n\n\n',l[j-1],curr,j,i,ans)
# print(ans)
print(*perm)