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 PYTHON3):

Solution:
import time,math as mt,bisect as bs,sys
from sys import stdin,stdout
from collections import deque
from fractions import Fraction
from collections import Counter
from collections import OrderedDict
from collections import defaultdict
pi=3.14159265358979323846264338327950
def II(): # to take integer input
    return int(stdin.readline())
def IP(): # to take tuple as input
    return map(int,stdin.readline().split())
def L(): # to take list as input
    return list(map(int,stdin.readline().split()))
def P(x): # to print integer,list,string etc..
    return stdout.write(str(x)+"\n")
def PI(x,y): # to print tuple separatedly
    return stdout.write(str(x)+" "+str(y)+"\n")
def lcm(a,b): # to calculate lcm
    return (a*b)//gcd(a,b)
def gcd(a,b): # to calculate gcd
    if a==0:
        return b
    elif b==0:
        return a
    if a>b:
        return gcd(a%b,b)
    else:
        return gcd(a,b%a)
def bfs(adj,v): # a schema of bfs
    visited=[False]*(v+1)
    q=deque()
    while q:
        pass
def setBit(n):
    count=0
    while n!=0:
        n=n&(n-1)
        count+=1
    return count
mx=10**7
spf=[mx]*(mx+1)
def readTree(n,e): # to read tree
    adj=[set() for i in range(n+1)]
    for i in range(e):
        u1,u2=IP()
        adj[u1].add(u2)
    return adj
def sieve():
    li=[True]*(10**3+5)
    li[0],li[1]=False,False
    for i in range(2,len(li),1):
        if li[i]==True:
            for j in range(i*i,len(li),i):
                li[j]=False
    prime,cur=[0]*200,0
    for i in range(10**3+5):
        if li[i]==True:
            prime[cur]=i
            cur+=1
    return prime
def SPF():
    mx=(10**6+1)
    spf[1]=1
    for i in range(2,mx):
        if spf[i]==1e9:
            spf[i]=i
            for j in range(i*i,mx,i):
                if i<spf[j]:
                    spf[j]=i
    return
def prime(n,d):
    prm=set()
    while n!=1:
        prm.add(spf[n])
        n=n//spf[n]
    for ele in prm:
        d[ele]=d.get(ele,0)+1
    return
#####################################################################################
mod=998244353
inf = 10000000000000000
def solve():
    n,m=IP()
    li=[]
    for i in range(n):
        l=L()
        li.append(l)
    ans=[[0 for j in range(m)] for i in range(n)]
    for i in range(n):
        for j in range(m):
            if (i+j)%2:
                ans[i][j] = 720720+li[i][j]**4
            else:
                ans[i][j] = 720720
    for ele in ans:
        print(*ele)
    return

t=1
for i in range(t):
    solve()

    #######
   #
  #
 #######   #     #  # ####   # #     #
       #  # #   #  # #   #  # # #   #
      #  ####  #  # ####   ####  # #
######  #   # #### #    # #   #   #

# ``````¶0````1¶1_```````````````````````````````````````
# ```````¶¶¶0_`_¶¶¶0011100¶¶¶¶¶¶¶001_````````````````````
# ````````¶¶¶¶¶00¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶0_````````````````
# `````1_``¶¶00¶0000000000000000000000¶¶¶¶0_`````````````
# `````_¶¶_`0¶000000000000000000000000000¶¶¶¶¶1``````````
# ```````¶¶¶00¶00000000000000000000000000000¶¶¶_`````````
# ````````_¶¶00000000000000000000¶¶00000000000¶¶`````````
# `````_0011¶¶¶¶¶000000000000¶¶00¶¶0¶¶00000000¶¶_````````
# ```````_¶¶¶¶¶¶¶00000000000¶¶¶¶0¶¶¶¶¶00000000¶¶1````````
# ``````````1¶¶¶¶¶000000¶¶0¶¶¶¶¶¶¶¶¶¶¶¶0000000¶¶¶````````
# ```````````¶¶¶0¶000¶00¶0¶¶`_____`__1¶0¶¶00¶00¶¶````````
# ```````````¶¶¶¶¶00¶00¶10¶0``_1111_`_¶¶0000¶0¶¶¶````````
# ``````````1¶¶¶¶¶00¶0¶¶_¶¶1`_¶_1_0_`1¶¶_0¶0¶¶0¶¶````````
# ````````1¶¶¶¶¶¶¶0¶¶0¶0_0¶``100111``_¶1_0¶0¶¶_1¶````````
# ```````1¶¶¶¶00¶¶¶¶¶¶¶010¶``1111111_0¶11¶¶¶¶¶_10````````
# ```````0¶¶¶¶__10¶¶¶¶¶100¶¶¶0111110¶¶¶1__¶¶¶¶`__````````
# ```````¶¶¶¶0`__0¶¶0¶¶_¶¶¶_11````_0¶¶0`_1¶¶¶¶```````````
# ```````¶¶¶00`__0¶¶_00`_0_``````````1_``¶0¶¶_```````````
# ``````1¶1``¶¶``1¶¶_11``````````````````¶`¶¶````````````
# ``````1_``¶0_¶1`0¶_`_``````````_``````1_`¶1````````````
# ``````````_`1¶00¶¶_````_````__`1`````__`_¶`````````````
# ````````````¶1`0¶¶_`````````_11_`````_``_``````````````
# `````````¶¶¶¶000¶¶_1```````_____```_1``````````````````
# `````````¶¶¶¶¶¶¶¶¶¶¶¶0_``````_````_1111__``````````````
# `````````¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶01_`````_11____1111_```````````
# `````````¶¶0¶0¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶1101_______11¶_```````````
# ``````_¶¶¶0000000¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶0¶0¶¶¶1````````````
# `````0¶¶0000000¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶1`````````````
# ````0¶0000000¶¶0_````_011_10¶110¶01_1¶¶¶0````_100¶001_`
# ```1¶0000000¶0_``__`````````_`````````0¶_``_00¶¶010¶001
# ```¶¶00000¶¶1``_01``_11____``1_``_`````¶¶0100¶1```_00¶1
# ``1¶¶00000¶_``_¶_`_101_``_`__````__````_0000001100¶¶¶0`
# ``¶¶¶0000¶1_`_¶``__0_``````_1````_1_````1¶¶¶0¶¶¶¶¶¶0```
# `_¶¶¶¶00¶0___01_10¶_``__````1`````11___`1¶¶¶01_````````
# `1¶¶¶¶¶0¶0`__01¶¶¶0````1_```11``___1_1__11¶000`````````
# `1¶¶¶¶¶¶¶1_1_01__`01```_1```_1__1_11___1_``00¶1````````
# ``¶¶¶¶¶¶¶0`__10__000````1____1____1___1_```10¶0_```````
# ``0¶¶¶¶¶¶¶1___0000000```11___1__`_0111_```000¶01```````
# ```¶¶¶00000¶¶¶¶¶¶¶¶¶01___1___00_1¶¶¶`_``1¶¶10¶¶0```````
# ```1010000¶000¶¶0100_11__1011000¶¶0¶1_10¶¶¶_0¶¶00``````
# 10¶000000000¶0________0¶000000¶¶0000¶¶¶¶000_0¶0¶00`````
# ¶¶¶¶¶¶0000¶¶¶¶_`___`_0¶¶¶¶¶¶¶00000000000000_0¶00¶01````
# ¶¶¶¶¶0¶¶¶¶¶¶¶¶¶_``_1¶¶¶00000000000000000000_0¶000¶01```
# 1__```1¶¶¶¶¶¶¶¶¶00¶¶¶¶00000000000000000000¶_0¶0000¶0_``
# ```````¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶00000000000000000000010¶00000¶¶_`
# ```````0¶¶¶¶¶¶¶¶¶¶¶¶¶¶00000000000000000000¶10¶¶0¶¶¶¶¶0`
# ````````¶¶¶¶¶¶¶¶¶¶0¶¶¶00000000000000000000010¶¶¶0011```
# ````````1¶¶¶¶¶¶¶¶¶¶0¶¶¶0000000000000000000¶100__1_`````
# `````````¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶000000000000000000¶11``_1``````
# `````````1¶¶¶¶¶¶¶¶¶¶¶0¶¶¶00000000000000000¶11___1_`````
# ``````````¶¶¶¶¶¶0¶0¶¶¶¶¶¶¶0000000000000000¶11__``1_````
# ``````````¶¶¶¶¶¶¶0¶¶¶0¶¶¶¶¶000000000000000¶1__````__```
# ``````````¶¶¶¶¶¶¶¶0¶¶¶¶¶¶¶¶¶0000000000000000__`````11``
# `````````_¶¶¶¶¶¶¶¶¶000¶¶¶¶¶¶¶¶000000000000011_``_1¶¶¶0`
# `````````_¶¶¶¶¶¶0¶¶000000¶¶¶¶¶¶¶000000000000100¶¶¶¶0_`_
# `````````1¶¶¶¶¶0¶¶¶000000000¶¶¶¶¶¶000000000¶00¶¶01`````
# `````````¶¶¶¶¶0¶0¶¶¶0000000000000¶0¶00000000011_``````_
# ````````1¶¶0¶¶¶0¶¶¶¶¶¶¶000000000000000000000¶11___11111
# ````````¶¶¶¶0¶¶¶¶¶00¶¶¶¶¶¶000000000000000000¶011111111_
# ```````_¶¶¶¶¶¶¶¶¶0000000¶0¶00000000000000000¶01_1111111
# ```````0¶¶¶¶¶¶¶¶¶000000000000000000000000000¶01___`````
# ```````¶¶¶¶¶¶0¶¶¶000000000000000000000000000¶01___1````
# ``````_¶¶¶¶¶¶¶¶¶00000000000000000000000000000011_111```
# ``````0¶¶0¶¶¶0¶¶0000000000000000000000000000¶01`1_11_``
# ``````¶¶¶¶¶¶0¶¶¶0000000000000000000000000000001`_0_11_`
# ``````¶¶¶¶¶¶¶¶¶00000000000000000000000000000¶01``_0_11`
# ``````¶¶¶¶0¶¶¶¶00000000000000000000000000000001```_1_11