Problem: You are given a matrix a consisting of positive integers. It has n rows and m columns.

Construct a matrix b consisting of positive integers. It should have the same size as a, and the following conditions should be met: 

  * 1 ≤ b_{i,j} ≤ 10^6; 
  * b_{i,j} is a multiple of a_{i,j}; 
  * the absolute value of the difference between numbers in any adjacent pair of cells (two cells that share the same side) in b is equal to k^4 for some integer k ≥ 1 (k is not necessarily the same for all pairs, it is own for each pair). 



We can show that the answer always exists.

Input

The first line contains two integers n and m (2 ≤ n,m ≤ 500).

Each of the following n lines contains m integers. The j-th integer in the i-th line is a_{i,j} (1 ≤ a_{i,j} ≤ 16).

Output

The output should contain n lines each containing m integers. The j-th integer in the i-th line should be b_{i,j}.

Examples

Input


2 2
1 2
2 3


Output


1 2
2 3


Input


2 3
16 16 16
16 16 16


Output


16 32 48
32 48 64


Input


2 2
3 11
12 8


Output


327 583
408 664

Note

In the first example, the matrix a can be used as the matrix b, because the absolute value of the difference between numbers in any adjacent pair of cells is 1 = 1^4.

In the third example: 

  * 327 is a multiple of 3, 583 is a multiple of 11, 408 is a multiple of 12, 664 is a multiple of 8; 
  * |408 - 327| = 3^4, |583 - 327| = 4^4, |664 - 408| = 4^4, |664 - 583| = 3^4. 

Solution (in JAVA):

Solution:
//Avoid division by decimal digits :). Always try to multiply with whole numbers or fractions instead.
//if getting wrong answer then use long/double instead of int/float
//e + e = o; o + o = e; e + o = o;
//see stuff in a jugaad way... if you are being complicated you are doing it wrong baby girl :)
//If a=b+1 and b is even, then a∧b=1
//Be confident in Maths you are not that bad at it.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

    public static void main(String[] args) {
        // write your code here
        FastReader reader = new FastReader();
//        int test = reader.nextInt();
        int m = reader.nextInt();
        int n = reader.nextInt();
        int[][] grid = new int[m][n];
        int s = 720720;
        int[][] ans = new int[m][n];
        for (int i = 0; i < m; i++){
            for (int j = 0; j < n; j++){
                grid[i][j] = reader.nextInt();
                ans[i][j] = 720720;
                if ((i + j) % 2 != 0){ans[i][j] += Math.pow(grid[i][j], 4);}
            }
        }
        for (int i = 0; i < m; i++){
            for (int j = 0; j < n; j++) {
                System.out.print(ans[i][j] + " ");
            }
            System.out.println("");
        }
//        for (int o = 0; o < test; o++){
//            int a = reader.nextInt();
//            int b = reader.nextInt();
//            long ans = 0;
//            for (int i = 1; i*i < a; i++){
//                ans += Math.max(0, Math.min(b, (a/i) - 1) - i);
//            }
//            System.out.println(ans);
//        }
    }
}
class Noddy {
    int att; int h;
    public Noddy(int att, int h){
        this.att = att; this.h = h;
    }
}
class FastReader
{
    BufferedReader br;
    StringTokenizer st;

    public FastReader()
    {
        br = new BufferedReader(new
                InputStreamReader(System.in));
    }

    String next()
    {
        while (st == null || !st.hasMoreElements())
        {
            try
            {
                st = new StringTokenizer(br.readLine());
            }
            catch (IOException e)
            {
                e.printStackTrace();
            }
        }
        return st.nextToken();
    }

    int nextInt()
    {
        return Integer.parseInt(next());
    }

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

    double nextDouble()
    {
        return Double.parseDouble(next());
    }

    String nextLine()
    {
        String str = "";
        try
        {
            str = br.readLine();
        }
        catch (IOException e)
        {
            e.printStackTrace();
        }
        return str;
    }
}

/** Class for buffered reading int and double values */
class Reader {
    static BufferedReader reader;
    static StringTokenizer tokenizer;

    /** call this method to initialize reader for InputStream */
    static void init(InputStream input) {
        reader = new BufferedReader(
                new InputStreamReader(input) );
        tokenizer = new StringTokenizer("");
    }

    /** get next word */
    static String next() throws IOException {
        while ( ! tokenizer.hasMoreTokens() ) {
            //TODO add check for eof if necessary
            tokenizer = new StringTokenizer(
                    reader.readLine() );
        }
        return tokenizer.nextToken();
    }

    static int nextInt() throws IOException {
        return Integer.parseInt( next() );
    }

    static double nextDouble() throws IOException {
        return Double.parseDouble( next() );
    }
}