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.
// Don't place your source in a package
import javax.swing.*;
import java.lang.reflect.Array;
import java.text.DecimalFormat;
import java.util.*;
import java.lang.*;
import java.io.*;
import java.math.*;
import java.util.stream.Stream;


// Please name your class Main
public class Main {
    static FastScanner fs=new FastScanner();
    static class FastScanner {
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st=new StringTokenizer("");
        public String next() {
            while (!st.hasMoreElements())
                try {
                    st=new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            return st.nextToken();
        }
        int Int() {
            return Integer.parseInt(next());
        }

        long Long() {
            return Long.parseLong(next());
        }

        String Str(){
            return next();
        }
    }


    public static void main (String[] args) throws java.lang.Exception {
        PrintWriter out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));

        int T=1;
        for(int t=0;t<T;t++){
            int n=Int(),m=Int(),k=Int();
            List<int[]>g[]=new ArrayList[n*m+1];
            for(int i=0;i<g.length;i++){
                g[i]=new ArrayList<>();
            }
            for(int i=0;i<n;i++){
                for(int j=0;j<m-1;j++){
                    int w=Int();
                    int u=i*m+j;
                    int v=i*m+(j+1);
                    g[u].add(new int[]{v,w});
                    g[v].add(new int[]{u,w});
                }
            }

            for(int i=0;i<n-1;i++){
                for(int j=0;j<m;j++){
                    int w=Int();
                    int u=i*m+j;
                    int v=(i+1)*m+j;
                    g[u].add(new int[]{v,w});
                    g[v].add(new int[]{u,w});
                }
            }

            Solution sol=new Solution(out);
            sol.solution(n,m,k,g);
        }
        out.close();

    }


    public static int Int(){
        return fs.Int();
    }
    public static long Long(){
        return fs.Long();
    }
    public static String Str(){
        return fs.Str();
    }

}






class Solution{
    PrintWriter out;
    public Solution(PrintWriter out){
        this.out=out;
    }




    List<int[]>g[];
    int n,m;
    long INF=10000000000000000l;
    int curr=-1,curc=-1;
    long mn=Long.MAX_VALUE;
    long dp[][];
    public void solution(int n,int m,int k,List<int[]>g[]){
        //edge : 4 directions.
        this.n=n;
        this.m=m;
        long res[][]=new long[n][m];
        if(k%2==1){
            for(int i=0;i<n;i++){
                Arrays.fill(res[i],-1);
            }
            print(res);
            return;
        }
        this.g=g;
        dp=new long[n*m+1][k/2+2];
        for(int i=0;i<dp.length;i++){
            Arrays.fill(dp[i],-1);
        }


        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                int id=i*m+j;
                dfs(id,k/2);
            }
        }

        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                int id=i*m+j;
                res[i][j]=dp[id][k/2];
            }
        }
        print(res);
    }

    public long dfs(int id,int cnt){
        if(cnt==0){
            return 0;
        }
        if(dp[id][cnt]!=-1)return dp[id][cnt];

        int r=id/m;
        int c=id%m;
        long res=Long.MAX_VALUE;
        for(int p[]:g[id]){
            int next=p[0],w=p[1];
            res=Math.min(res,w*2+dfs(next,cnt-1));
        }
        dp[id][cnt]=res;
        return res;

    }

    public int dis(int x1,int y1,int x2,int y2){
        return Math.abs(x1-x2)+Math.abs(y1-y2);
    }


    public void print(long A[][]){
        for(int i=0;i<A.length;i++){
            for(int j=0;j<A[0].length;j++){
                out.print(A[i][j]+" ");
            }
            out.println();
        }
    }






}

class Solution1{
    PrintWriter out;
    public Solution1(PrintWriter out){
        this.out=out;
    }

    public void solution(int A[]){

    }

}



/*
                             ;\
                            |' \
         _                  ; : ;
        / `-.              /: : |
       |  ,-.`-.          ,': : |
       \  :  `. `.       ,'-. : |
        \ ;    ;  `-.__,'    `-.|
         \ ;   ;  :::  ,::'`:.  `.
          \ `-. :  `    :.    `.  \
           \   \    ,   ;   ,:    (\
            \   :., :.    ,'o)): ` `-.
           ,/,' ;' ,::"'`.`---'   `.  `-._
         ,/  :  ; '"      `;'          ,--`.
        ;/   :; ;             ,:'     (   ,:)
          ,.,:.    ; ,:.,  ,-._ `.     \""'/
          '::'     `:'`  ,'(  \`._____.-'"'
             ;,   ;  `.  `. `._`-.  \\
             ;:.  ;:       `-._`-.\  \`.
              '`:. :        |' `. `\  ) \
      -hrr-      ` ;:       |    `--\__,'
                   '`      ,'
                        ,-'


                      free bug dog
*/


