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;
typedef long long ll;
const int mod=998244353;
const int N=200005;
int prime[1100000],primesize;
bool isprime[11000000];
ll f[N],invf[N];
ll inv[N];
void getlist(int listsize){
    memset(isprime,1,sizeof(isprime));
    isprime[1]=false;
    for(int i=2;i<=listsize;i++){
        if(isprime[i])prime[++primesize]=i;
         for(int j=1;j<=primesize&&i*prime[j]<=listsize;j++) {
            isprime[i*prime[j]]=false;
            if(i%prime[j]==0) break;
        }
    }
}
void extend_gcd(ll a, ll b, ll& d, ll& x, ll& y)
{
	if(!b){ d = a; x = 1; y = 0; }
	else { extend_gcd(b, a%b,d, y, x); y -= x*(a/b);}
}
void ni(int n)
{
	inv[0] = inv[1] = 1;
	for(int i = 2; i <= n; i++)
	{
		inv[i] = (mod - (mod/i))*inv[mod%i]%mod;
	}
}
ll fpow(ll a,ll k){
    ll res=1;
    while(k){
        if(k&1) res=(res*a)%mod;
        k>>=1;
        a=a*a%mod;
        //cout<<1<<endl;
    }
    return res;
}
void init(int n){
    f[0]=1;
    for(int i=1;i<=n;++i){
        f[i]=f[i-1]*i%mod;
    }
    invf[n]=fpow(f[n],mod-2);
    for(int i=n-1;i>=0;--i){
        invf[i]=invf[i+1]*(i+1)%mod;
    }
}
ll C(int n,int k){
    if(k<0 || k>n) return 0;
    return f[n]*invf[k]%mod*invf[n-k]%mod;
}
const int d=2*2*2*2*3*3*5*7*11*13;
void solve(){
	ll n,m,a;
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>a;
			if((i+j)&1){
				cout<<d<<" ";
				
			}
			else{
				cout<<d+a*a*a*a<<" ";
			}
		}
		cout<<endl;
	} 
}
int main(){
	ios::sync_with_stdio(false);cin.tie(0);
//	getlist(1e7);
	int t=1;
//	cin>>t;
	while(t--){
		solve();
	}
}