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:
import java.io.*;
import java.lang.reflect.Type;
import java.math.BigDecimal;
import java.math.BigInteger;
import java.math.RoundingMode;
import java.text.DecimalFormat;
import java.util.*;
import java.util.concurrent.ArrayBlockingQueue;
import java.util.concurrent.Future;
import java.util.concurrent.FutureTask;
import java.util.concurrent.locks.LockSupport;

public class Main {

    static class Task {

        public static String roundS(double result, int scale) {
            String fmt = String.format("%%.%df", scale);
            return String.format(fmt, result);
//        DecimalFormat df = new DecimalFormat("0.000000");
//        double result = Double.parseDouble(df.format(result));
        }

        int rt(int x) {
            if (x != fa[x]) {
                int to = rt(fa[x]);
                dp[x] ^= dp[fa[x]];
                fa[x] = to;
                return to;
            }
            return x;
        }

        void combine(int x, int y, int val) {
            int rt1 = rt(x);
            int rt2 = rt(y);

            if (rt1 == rt2) return;

            fa[rt1] = rt2;
            dp[rt1] = dp[x] ^ dp[y] ^ val;
            g--;

        }


        int fa[], dp[];
        int g;


        static int MAXN = 10000;
        static Random rd = new Random(348957438574659L);

        static int[] ch[],val,size,rnd,cnt;
        static int len=0,rt=0;

        // return new node, the node below s
        static int rotate(int s,int d){
            // child
            int x=ch[s][d^1];
            // give me grandson
            ch[s][d^1] = ch[x][d];
            // child become father
            ch[x][d]=s;
            // update size, update new son first
            update(s);
            update(x);
            return x;
        }

        static void update(int s){
            size[s] = size[ch[s][0]] + size[ch[s][1]] + cnt[s];
        }

        // 0 for left, 1 for right
        static int cmp(int x,int num) {
            if (val[x] == num) return -1;
            return num < val[x] ? 0 : 1;
        }

        static int insert(int s,int num) {
            if(s==0){
                s=++len;
                val[s]=num;size[s]=1;rnd[s]=rd.nextInt();cnt[s] = 1;
            }else{
                int d=cmp(s,num);
                if(d!=-1) {
                    ch[s][d]=insert(ch[s][d],num);
                    // father's random should be greater
                    if(rnd[s]<rnd[ch[s][d]]) {
                        s=rotate(s,d^1);
                    }else {
                        update(s);
                    }
                }else{
                    ++cnt[s];++size[s];
                }
            }
            return s;
        }

        static int del(int s,int num) {
            int d = cmp(s, num);
            if (d != -1) {
                ch[s][d] = del(ch[s][d], num);
                update(s);
            }else if (ch[s][0] * ch[s][1] == 0) {
                if(--cnt[s]==0){
                    s = ch[s][0] + ch[s][1];
                }
            } else {
                int k = rnd[ch[s][0]] < rnd[ch[s][1]] ? 0 : 1;
                // k points to smaller random value,then bigger one up
                s = rotate(s, k);
                // now the node with value num become the child
                ch[s][k] = del(ch[s][k], num);
                update(s);
            }
            return s;
        }

        static int getKth(int s, int k){
            int lz = size[ch[s][0]];
            if(k>=lz+1&&k<=lz+cnt[s]){
                return val[s];
            }else if(k<=lz){
                return getKth(ch[s][0], k);
            }else{
                return getKth(ch[s][1], k-lz-cnt[s]);
            }
        }
        // value可能不在树中出现，定义为比自己小的数的个数+1
        static int getRank(int s,int value){
            if(s==0)return 1;
            if(value==val[s])return size[ch[s][0]] + 1;
            if(value<val[s])return getRank(ch[s][0],value);
            return getRank(ch[s][1],value)+size[ch[s][0]] + cnt[s];
        }


        static int getPre(int data){
            int ans= -1;
            int p=rt;
            while(p>0){
                if(data>val[p]){
                    if(ans==-1 || val[p]>val[ans])
                        ans=p;
                    p=ch[p][1];
                }
                else p=ch[p][0];
            }
            return ans!=-1?val[ans]:(-2147483647);
        }

        static int getNext(int data){
            int ans= -1;
            int p=rt;
            while(p>0){
                if(data<val[p]){
                    if(ans==-1 || val[p]<val[ans])
                        ans=p;
                    p=ch[p][0];
                }
                else p=ch[p][1];
            }

            return ans!=-1?val[ans]:2147483647;
        }


        static boolean find(int s,int num){
            while(s!=0){
                int d=cmp(s,num);
                if(d==-1) return true;
                else s=ch[s][d];
            }
            return false;
        }
        static int ans = -10000000;
        static boolean findX(int s,int num){
            while(s!=0){
                if(val[s]<=num){
                    ans = num;
                }
                int d=cmp(s,num);
                if(d==-1) return true;
                else {
                    s = ch[s][d];
                }
            }
            return false;
        }

        long gcd(long a,long b){
            if(b==0) return a;
            return gcd(b,a%b);
        }


        public void solve(int testNumber, InputReader in, PrintWriter out) {

//            int t = in.nextInt();
//
//
//            outer:for(int j=0;j<t;++j){
//               int n = in.nextInt();
//               int m = in.nextInt();
//
//               int a[]  = in.nextArray(n);
//               int b[]  = in.nextArray(n);
//               int one = 0;
//                long hi = 0;
//                for(int i=0;i<n;++i){
//                   if(b[i]==1) one++;
//                   hi += a[i];
//               }
//                if(hi<m){
//                    out.println(-1);
//                    continue ;
//                }
//               Long s[]  = new Long[one];
//                Long tw[]  =new Long[n-one];
//
//               int p = one-1;int q = n-one-1;
//
//               for(int i=0;i<n;++i){
//                   if(b[i]==1){
//                       s[p--] = (long)a[i];
//                   }else{
//                       tw[q--] =  (long)a[i];
//                   }
//               }
//               Arrays.sort(s,(x,y)-> Long.compare(y,x));
//               Arrays.sort(tw,(x,y)-> Long.compare(y,x));
//                for(int i=1;i<one;++i) s[i] += s[i-1];
//                for(int i=1;i<n-one;++i) tw[i] += tw[i-1];
//                long lo = 0;
//                while(lo<hi){
//                    long mi =  (lo+hi)/2L;
//                    boolean ok  =false;
//                        for(int i=0;i<=one&&i<=mi;++i){
//                        long ck = mi - i;
//                        //if(ck%2==0){
//                            int num =  (int)(ck/2L);
//                            if(num<=n-one){
//
//                               long tot =  (num-1>=0?tw[num-1]:0) + (i-1>=0?s[i-1]:0) ;
//                               if(tot>=m){
//                                   ok = true;
//                                   break;
//                               }
//
//                            }
//
//                      //  }
//                    }
//                    if(ok){
//                        hi = mi;
//                    }else{
//                        lo = mi+1;
//                    }
//
//                }
//                out.println(lo);





     //       }

                int n = in.nextInt();
                int m = in.nextInt();
                int a[][] = new int[n][m];
                for(int i=0;i<n;++i){
                    for(int j=0;j<m;++j){
                        a[i][j] = in.nextInt();
                    }
                }
                int g = 1;
                for(int j=2;j<=16;++j){
                    g = (int)(j/gcd(g,j)*g);
                }
                int f = g;

            for(int i=0;i<n;++i) {
                for (int j = 0; j < m; ++j) {
                    if(j>=1){
                        out.print(" ");

                    }
                    if((i+j)%2==1){
                        out.print(f);
                    }else{
                        out.print((int)(f+ Math.pow(a[i][j],4)));
                    }
                }
                out.println();
            }




//            while(true) {
//                int n = in.nextInt();
//
//                int m  =in.nextInt();
//
//                fa = new int[n];
//                dp = new int[n];
//                for(int i=0;i<n;++i){
//                    fa[i] = i;
//                }
//                g =  n;
//                int c = 0;
//                int as[] = new int[n];
//                int bs[] = new int[n];
//                char xs[] = new char[n];
//
//                int at = -1;
//                Set<Integer> st = new HashSet<>();
//
//                for (int i = 0; i < n; ++i) {
//                    String line = in.next();
//                    int p = 0;
//                    int a = 0;
//                    while(Character.isDigit(line.charAt(p))){
//                        a =  a*10 + (line.charAt(p)-'0'); p++;
//                    }
//                    char x = line.charAt(p++);
//
//                    int b = 0;
//                    while(p<line.length()){
//                        b =  b*10 + (line.charAt(p)-'0'); p++;
//                    }
//
//                    as[i] = a;
//                    xs[i] = x;
//                    bs[i] = b;
//
//                    if(x=='='){
//                        int r1 = rt(a); int r2 = rt(b);
//                        if(r1==r2){
//                            if(dp[a]!=dp[b]){
//                                c++;
//                                at = i;
//                            }
//                        }else {
//                            combine(a, b, 0);
//                        }
//                    }else if(x=='<'){
//                        int r1 = rt(a); int r2 = rt(b);
//                        if(r1==r2){
//                            if(dp[a]>=dp[b]){
//                                c++;
//                                at = i;
//                            }
//                        }else {
//                            combine(a, b, -1);
//                        }
//                    }else{
//                        int r1 = rt(a); int r2 = rt(b);
//                        if(r1==r2){
//                            if(dp[a]<=dp[b]){
//                                c++;
//                                at = i;
//                            }
//                        }else {
//                            combine(a, b, 1);
//                        }
//                    }
//
//
//                }
//                if(g==1||c>=2){
//                    out.println("Impossible");
//                    continue;
//                }
//
//
//                for(int xuan: st){
//
//
//
//
//                }
//
//
//
//
//
//
//            }






        }


        static long mul(long a, long b, long p)
        {
            long res=0,base=a;
            while(b>0)
            {
                if((b&1L)>0)
                    res=(res+base)%p;
                base=(base+base)%p;
                b>>=1;
            }
            return res;
        }

        static long mod_pow(long k,long n,long p){
            long res = 1L;
            long temp = k%p;
            while(n!=0L){
                if((n&1L)==1L){
                    res = mul(res,temp,p);
                }
                temp = mul(temp,temp,p);
                n = n>>1L;
            }
            return res%p;
        }


        public static double roundD(double result, int scale){
            BigDecimal bg = new BigDecimal(result).setScale(scale, RoundingMode.UP);
            return bg.doubleValue();
        }



    }
    private static void solve() {
        InputStream inputStream = System.in;
        //InputStream inputStream  = new FileInputStream(new File("D:\\chrome_download\\travel1.in"));
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        Task task = new Task();
        task.solve(1, in, out);
        out.close();
    }
    public static void main(String[] args) {
       // new Thread(null, () -> solve(), "1", (1 << 10 ) ).start();
        solve();
    }
    static class InputReader {
        public BufferedReader reader;
        public StringTokenizer tokenizer;
        public InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream), 32768);
            tokenizer = null;
        }
        public String nextLine() {
            String line = null;
            try {
                line = reader.readLine();
            } catch (IOException e) {
                throw new RuntimeException(e);
            }
            return line;
        }
        public String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }
        public int nextInt() {
            return Integer.parseInt(next());
        }
        public char nextChar() {
            return next().charAt(0);
        }
        public int[] nextArray(int n) {
            int res[] = new int[n];
            for (int i = 0; i < n; ++i) {
                res[i] = nextInt();
            }
            return res;
        }
        public long nextLong() {
            return Long.parseLong(next());
        }
        public double nextDouble() {
            return Double.parseDouble(next());
        }
    }
}