You are wandering in the explorer space of the 2050 Conference.

The explorer space can be viewed as an undirected weighted grid graph with size n× m. The set of vertices is \{(i, j)|1≤ i≤ n, 1≤ j≤ m\}. Two vertices (i_1,j_1) and (i_2, j_2) are connected by an edge if and only if |i_1-i_2|+|j_1-j_2|=1.

At each step, you can walk to any vertex connected by an edge with your current vertex. On each edge, there are some number of exhibits. Since you already know all the exhibits, whenever you go through an edge containing x exhibits, your boredness increases by x.

For each starting vertex (i, j), please answer the following question: What is the minimum possible boredness if you walk from (i, j) and go back to it after exactly k steps?

You can use any edge for multiple times but the boredness on those edges are also counted for multiple times. At each step, you cannot stay on your current vertex. You also cannot change direction while going through an edge. Before going back to your starting vertex (i, j) after k steps, you can visit (i, j) (or not) freely.

Input

The first line contains three integers n, m and k (2≤ n, m≤ 500, 1≤ k≤ 20).

The j-th number (1≤ j ≤ m - 1) in the i-th line of the following n lines is the number of exibits on the edge between vertex (i, j) and vertex (i, j+1). 

The j-th number (1≤ j≤ m) in the i-th line of the following n-1 lines is the number of exibits on the edge between vertex (i, j) and vertex (i+1, j). 

The number of exhibits on each edge is an integer between 1 and 10^6.

Output

Output n lines with m numbers each. The j-th number in the i-th line, answer_{ij}, should be the minimum possible boredness if you walk from (i, j) and go back to it after exactly k steps.

If you cannot go back to vertex (i, j) after exactly k steps, answer_{ij} should be -1. 

Examples

Input


3 3 10
1 1
1 1
1 1
1 1 1
1 1 1


Output


10 10 10
10 10 10
10 10 10


Input


2 2 4
1
3
4 2


Output


4 4
10 6


Input


2 2 3
1
2
3 4


Output


-1 -1
-1 -1

Note

In the first example, the answer is always 10 no matter how you walk.

In the second example, answer_{21} = 10, the path is (2,1) → (1,1) → (1,2) → (2,2) → (2,1), the boredness is 4 + 1 + 2 + 3 = 10.
#Code by Sounak, IIESTS
#------------------------------warmup----------------------------

import os
import sys
import math
from io import BytesIO, IOBase
from fractions import Fraction
import collections
from itertools import permutations
from collections import defaultdict
from collections import deque
import threading

#sys.setrecursionlimit(300000)
#threading.stack_size(10**8)

BUFSIZE = 8192
 
 
class FastIO(IOBase):
    newlines = 0
    
    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None
     
    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()
 
    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()
 
    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)
 
 
class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")
  
sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")

#-------------------------------------------------------------------------
#mod = 9223372036854775807  
class SegmentTree:
    def __init__(self, data, default=0, func=lambda a, b: a+b):
        """initialize the segment tree with data"""
        self._default = default
        self._func = func
        self._len = len(data)
        self._size = _size = 1 << (self._len - 1).bit_length()
 
        self.data = [default] * (2 * _size)
        self.data[_size:_size + self._len] = data
        for i in reversed(range(_size)):
            self.data[i] = func(self.data[i + i], self.data[i + i + 1])
 
    def __delitem__(self, idx):
        self[idx] = self._default
 
    def __getitem__(self, idx):
        return self.data[idx + self._size]
 
    def __setitem__(self, idx, value):
        idx += self._size
        self.data[idx] = value
        idx >>= 1
        while idx:
            self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
            idx >>= 1
 
    def __len__(self):
        return self._len
 
    def query(self, start, stop):
        if start == stop:
            return self.__getitem__(start)
        stop += 1
        start += self._size
        stop += self._size
 
        res = self._default
        while start < stop:
            if start & 1:
                res = self._func(res, self.data[start])
                start += 1
            if stop & 1:
                stop -= 1
                res = self._func(res, self.data[stop])
            start >>= 1
            stop >>= 1
        return res
 
    def __repr__(self):
        return "SegmentTree({0})".format(self.data)
    
class SegmentTree1:
    def __init__(self, data, default=10**6, func=lambda a, b: min(a,b)):
        """initialize the segment tree with data"""
        self._default = default
        self._func = func
        self._len = len(data)
        self._size = _size = 1 << (self._len - 1).bit_length()
 
        self.data = [default] * (2 * _size)
        self.data[_size:_size + self._len] = data
        for i in reversed(range(_size)):
            self.data[i] = func(self.data[i + i], self.data[i + i + 1])
 
    def __delitem__(self, idx):
        self[idx] = self._default
 
    def __getitem__(self, idx):
        return self.data[idx + self._size]
 
    def __setitem__(self, idx, value):
        idx += self._size
        self.data[idx] = value
        idx >>= 1
        while idx:
            self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
            idx >>= 1
 
    def __len__(self):
        return self._len
 
    def query(self, start, stop):
        if start == stop:
            return self.__getitem__(start)
        stop += 1
        start += self._size
        stop += self._size
 
        res = self._default
        while start < stop:
            if start & 1:
                res = self._func(res, self.data[start])
                start += 1
            if stop & 1:
                stop -= 1
                res = self._func(res, self.data[stop])
            start >>= 1
            stop >>= 1
        return res
 
    def __repr__(self):
        return "SegmentTree({0})".format(self.data)
    
MOD=10**9+7
class Factorial:
    def __init__(self, MOD):
        self.MOD = MOD
        self.factorials = [1, 1]
        self.invModulos = [0, 1]
        self.invFactorial_ = [1, 1]
 
    def calc(self, n):
        if n <= -1:
            print("Invalid argument to calculate n!")
            print("n must be non-negative value. But the argument was " + str(n))
            exit()
        if n < len(self.factorials):
            return self.factorials[n]
        nextArr = [0] * (n + 1 - len(self.factorials))
        initialI = len(self.factorials)
        prev = self.factorials[-1]
        m = self.MOD
        for i in range(initialI, n + 1):
            prev = nextArr[i - initialI] = prev * i % m
        self.factorials += nextArr
        return self.factorials[n]
 
    def inv(self, n):
        if n <= -1:
            print("Invalid argument to calculate n^(-1)")
            print("n must be non-negative value. But the argument was " + str(n))
            exit()
        p = self.MOD
        pi = n % p
        if pi < len(self.invModulos):
            return self.invModulos[pi]
        nextArr = [0] * (n + 1 - len(self.invModulos))
        initialI = len(self.invModulos)
        for i in range(initialI, min(p, n + 1)):
            next = -self.invModulos[p % i] * (p // i) % p
            self.invModulos.append(next)
        return self.invModulos[pi]
 
    def invFactorial(self, n):
        if n <= -1:
            print("Invalid argument to calculate (n^(-1))!")
            print("n must be non-negative value. But the argument was " + str(n))
            exit()
        if n < len(self.invFactorial_):
            return self.invFactorial_[n]
        self.inv(n)  # To make sure already calculated n^-1
        nextArr = [0] * (n + 1 - len(self.invFactorial_))
        initialI = len(self.invFactorial_)
        prev = self.invFactorial_[-1]
        p = self.MOD
        for i in range(initialI, n + 1):
            prev = nextArr[i - initialI] = (prev * self.invModulos[i % p]) % p
        self.invFactorial_ += nextArr
        return self.invFactorial_[n]
 
 
class Combination:
    def __init__(self, MOD):
        self.MOD = MOD
        self.factorial = Factorial(MOD)
 
    def ncr(self, n, k):
        if k < 0 or n < k:
            return 0
        k = min(k, n - k)
        f = self.factorial
        return f.calc(n) * f.invFactorial(max(n - k, k)) * f.invFactorial(min(k, n - k)) % self.MOD
mod=10**9+7
omod=998244353
#-------------------------------------------------------------------------
prime = [True for i in range(10)] 
pp=[0]*10
def SieveOfEratosthenes(n=10):
    p = 2
    c=0
    while (p * p <= n): 
          
        if (prime[p] == True):
            c+=1
            for i in range(p, n+1, p): 
                pp[i]+=1
                prime[i] = False
        p += 1
#---------------------------------Binary Search------------------------------------------
def binarySearch(arr, n, key):
    left = 0
    right = n-1
    mid = 0
    res=0
    while (left <= right):
        mid = (right + left)//2
        if (arr[mid][0] > key):
            right = mid-1
        else:
            res=mid
            left = mid + 1
    return res
#---------------------------------running code------------------------------------------
n,m,k=map(int,input().split())
r=[]
for i in range (n):
    a=list(map(int,input().split()))
    r.append(a)
c=[]
for i in range (n-1):
    a=list(map(int,input().split()))
    c.append(a)
if k%2:
    a=[-1]*m
    for i in range (n):
        print(*a)
    sys.exit(0)
dp=[[[0 for i in range ((k//2)+1)]for j in range (m)]for p in range (n)]
for x in range (1,(k//2)+1):
    for i in range (n):
        for j in range (m):
            mn=10**8
            if i>0:
                mn=min(mn,c[i-1][j]+dp[i-1][j][x-1])
            if j>0:
                mn=min(mn,r[i][j-1]+dp[i][j-1][x-1])
            if i<n-1:
                mn=min(mn,c[i][j]+dp[i+1][j][x-1])
            if j<m-1:
                mn=min(mn,r[i][j]+dp[i][j+1][x-1])
            dp[i][j][x]=mn
for i in range (n):
    for j in range (m):
        print(2*dp[i][j][k//2],end=' ')
    print()