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

Solution:
#include <bits/stdc++.h> 
using namespace std; 
#include <stack>
#define ll long long 
#define ld long double
const ll INF=100000000000000000;
#define vecpair vector<pair <ll,ll> >
#define priqs priority_queue<ll, vector<ll>,  greater<ll> >
#define priqg priority_queue<ll>
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define vel vector<ll>
#define endl "\n"
#define forl for(int i=0;i<n;i++)
const ll MAXN=15000001;
bool prime[15000001];
void SieveOfEratosthenes() 
{ 
    // Create a boolean array "prime[0..n]" and initialize 
    // all entries it as true. A value in prime[i] will 
    // finally be false if i is Not a prime, else true.  
    memset(prime, true, sizeof(prime)); 
  
    for (int p=2; p*p<=15000000; p++) 
    { 
        // If prime[p] is not changed, then it is a prime 
        if (prime[p] == true) 
        { 
            // Update all multiples of p greater than or  
            // equal to the square of it 
            // numbers which are multiple of p and are 
            // less than p^2 are already been marked.  
            for (int i=p*p; i<=15000000; i += p) 
                prime[i] = false; 
        } 
    } 
  
    
} 
ll bs(vel &a,ll i,ll j,ll val){
	int l=i;
	int h=j;
	int m;
	if(a[h]<val) return -1;
	while(l<=h){
		m=(l+h)/2;
		if(a[m]>=val) h=m-1;
		else if(a[m]<val) l=m+1;
		}
		if(a[m]<val) m++;
		return m;
}

ll bins(vel &a,ll n,ll val){
	int l=0;
	int h=n-1;
	int m;
	while(l<=h){
		m=(l+h)/2;
		if(a[m]>val) h=m-1;
		else if(a[m]<val) l=m+1;
		else return 1;
		}
		return 0;
}

ll power(ll x, ll y)  
{  
	ll p=INF;
    ll res = 1;     // Initialize result  
  
    x = x; // Update x if it is more than or  
                // equal to p 
   
    if (x == 0) return 0; // In case x is divisible by p; 
  
    while (y > 0)  
    {  
        // If y is odd, multiply x with result  
        if (y & 1)  
            res = (res*x) ;  
  
        // y must be even now  
        y = y>>1; // y = y/2  
        x = (x*x);  
    }  
    return res;  
}  

ll powermod(ll x, ll y,ll z)  
{  
	ll p=z;
    ll res = 1%z;     // Initialize result  
  
    x = x%z; // Update x if it is more than or  
                // equal to p 
   
    if (x == 0) return 0; // In case x is divisible by p; 
  
    while (y > 0)  
    {  
        // If y is odd, multiply x with result  
        if (y & 1)  
            res = (res*x)%z ;  
  
        // y must be even now  
        y = y>>1; // y = y/2  
        x = (x*x)%z;  
    }  
    return res%z;  
}  

ll mex(vel a,int n){
	sort(a.begin(),a.end());
	int j=a[0];
	if(j!=0) return 0;
	else{
		for(int i=1;i<n;i++){
				if(a[i]!=a[i-1]){
					if(a[i]!=a[i-1]+1){
						return j+1;
						}else j++;
					}
			}
			return j+1;
		}
}

int spf[MAXN]; 
  
// Calculating SPF (Smallest Prime Factor) for every 
// number till MAXN. 
// Time Complexity : O(nloglogn) 
void sieve() 
{ 
    spf[1] = 1; 
    for (int i=2; i<MAXN; i++) 
  
        // marking smallest prime factor for every 
        // number to be itself. 
        spf[i] = i; 
  
    // separately marking spf for every even 
    // number as 2 
    for (int i=4; i<MAXN; i+=2) 
        spf[i] = 2; 
  
    for (int i=3; i*i<MAXN; i++) 
    { 
        // checking if i is prime 
        if (spf[i] == i) 
        { 
            // marking SPF for all numbers divisible by i 
            for (int j=i*i; j<MAXN; j+=i) 
  
                // marking spf[j] if it is not  
                // previously marked 
                if (spf[j]==j) 
                    spf[j] = i; 
        } 
    } 
} 

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

ll lcm(ll a,ll b){
	return (a*b)/gcd(a,b);
	}

void lps(string pat, int M, int* lps) 
{ 
    // length of the previous longest prefix suffix 
    int len = 0; 
  
    lps[0] = 0; // lps[0] is always 0 
  
    // the loop calculates lps[i] for i = 1 to M-1 
    int i = 1; 
    while (i < M) { 
        if (pat[i] == pat[len]) { 
            len++; 
            lps[i] = len; 
            i++; 
        } 
        else // (pat[i] != pat[len]) 
        { 
            // This is tricky. Consider the example. 
            // AAACAAAA and i = 7. The idea is similar 
            // to search step. 
            if (len != 0) { 
                len = lps[len - 1]; 
  
                // Also, note that we do not increment 
                // i here 
            } 
            else // if (len == 0) 
            { 
                lps[i] = 0; 
                i++; 
            } 
        } 
    }
}

ll c(ll m,ll n){
	ll ans=1;
	for(int i=1;i<=n;i++){
		ans=(ans*(m-i+1))/i;
		}
		return ans;
}

ll gcdExtended(ll a, ll b, ll* x, ll* y) 
{ 
    // Base Case 
    if (a == 0)  
    { 
        *x = 0, *y = 1; 
        return b; 
    } 
  
    ll x1, y1; // To store results of recursive call 
    ll gcd = gcdExtended(b % a, a, &x1, &y1); 
  
    // Update x and y using results of recursive 
    // call 
    *x = y1 - (b / a) * x1; 
    *y = x1; 
  
    return gcd; 
}

ll modInverse(ll a, ll m) 
{ 
    ll x, y; 
    ll g = gcdExtended(a, m, &x, &y); 
		
        // m is added to handle negative x 
        ll res = (x % m + m) % m; 
       return res;
    
} 



ll pc(ll n){
	for(int i=2;i*i<=n;i++){
		if(n%i==0) return 0;
		}	
		return 1;
}

ll lexo(string a,string b){
ll n=a.length();
for(int i=0;i<n;i++){
	if(a[i]<b[i]) return 1;
	else if(b[i]<a[i]) return 0;
}
	return 0;
}

ll mod(ll x){
return (x%INF+INF)%INF;
}
ll next(ll i,ll n){
	if(i<n-1) return i+1;
	else return 0;
}

ll nsum(ll n){
	return (n*(n+1))/2;
	}

	
ll chk(ll a,ll b){
if(a==b) return 0;
else return 1;	
}
	
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
ll test=1;
while(test--){
ll a[17]={};
for(int i=1;i<=16;i++){
	ll g=1;
	while(1){
		if((720720-g*g*g*g)%i==0){
			a[i]=720720-g*g*g*g;
			break;
			}
			g++;
		}
	}
ll n,m;
cin>>n>>m;
ll arr[n][m];
for(int i=0;i<n;i++){
	for(int j=0;j<m;j++){
		cin>>arr[i][j];
		}
	}
	ll b[n][m];
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
			if((i+j)%2==0) b[i][j]=720720;
			else b[i][j]=a[arr[i][j]];
			}
		}
		for(int i=0;i<n;i++){
			for(int j=0;j<m;j++){
				cout<<b[i][j]<<" ";
				}
				cout<<endl;
			}
}
}