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;
#define debug(...) fprintf(stderr, __VA_ARGS__), fflush(stderr)
typedef long long int ll;
typedef long double ld;
#define trump(v,a) vector<ll> v(a); for(int i =0;i<a; ++i)cin>>v[i];
#define modi(v) for(auto i:v) cout<<i<<" ";

ll p[200005], inv[200005], hell = 998244353 ;
ll exp(ll x, ll y) {
	ll res = 1;
	x %= hell;
	while (y) {
		if (y & 1)
			res = (res * x) % hell;
		y >>= 1;
		x = (x * x) % hell;
	}
	return res;
}
ll bin(ll n, ll r) {
	if (n < r)
		return 0;
	ll res = (p[n] * inv[n - r]) % hell;
	res = (res * inv[r]) % hell;
	return res;
}



bool sortpairs(const pair<int, int> &a, const pair<int, int> &b)
{
	if (a.first == b.first)
		return a.second <  b.second;
	return a.first < b.first;
}
bool isprime(ll a) {
	for (int i = 2; i * i < a + 1; ++i) {
		if (a % i == 0)
			return false;
	}
	return true;
}
// returnd ceil of 2 integers t and a i.e. ceil(t/a)
ll ceil(ll t, ll a) {
	return t / (a ) + 1 * (bool)(t % (a));
}
// this returns the smallest element that is closest to the target in the sorted array i.e 9 in [6,9,11] with target 10
ll snear( ll arr[], ll target, ll end)
{
	int start = 0;

	int ans = -1;
	while (start <= end)
	{
		int mid = (start + end) / 2;

		// Move to the left side if the target is smaller
		if (arr[mid] == target) {
			ans = mid;
			break;
		}
		if (arr[mid] > target)
		{
			end = mid - 1;
		}

		// Move right side
		else
		{
			ans = mid;
			start = mid + 1;
		}
	}
	return ans;
}
// this function returns set of all factors both prime and composite of ll a
// to take intersection with another set follow
//	set_intersection(v1.begin(), v1.end(), v2.begin(), v2.end(), std::back_inserter(v));
// here v1 v2 are sets and v3 is a vector (or any member with a push_back() function)
const vector<ll> allprime(ll a) {
	vector<ll> v;
	for (int i = 1; i * i <= a; ++i)
	{
		/* code */
		if (a % i == 0 ) {
			v.push_back(i);

		}

	}
	return v;

}

//this calculates a**b in O(log(n)) called as binary exponenetiation
ll bina(ll a, ll b) {
	ll res = a;
	ll c = a;
	ll ans = 1;
	while (b) {

		ans = ans % hell;
		if (b & 1) {
			ans *= res;
		}
		res = (res * res) % hell;
		b >>= 1;
	}
	return ans % hell;
}


//returns a boolean vector of primes uptill n inclusive of n in o(n*loglogn)

const vector<bool> seive(ll n) {
	std::vector<bool> v(n + 1, true);
	v[0] = false;
	v[1] = false;
	for (ll i = 2; i * i <= n; ++i)
	{
		/* code */
		if (v[i] ) {
			for (ll j = i * i; j <= n; j += i )
			{
				/* code */
				v[j] = false;
			}
		}
	}
	return v;
}

void solve() {
	ll a = 19, b = 9, c = 0, t = 1, ans = 0, k = 1,  ans2 = 10000000000, c1 = 0, c2 = 0, n = 0, m = 0, x = 22311311;
	cin >> a >> b;
	c = 720720;
	k = ll(pow(c, 0.25));
	t = c;
	std::vector<ll> v(17);
	while (c > 0) {
		c1 = pow(t - c, 0.25);

		if ( c1 * c1 * c1 * c1 == t - c ) {
			for (int i = 1; i <= 16; ++i)
			{
				/* code */
				if (c % i == 0) {
					// cout << i << " " << t - c << endl;
					v[i] = c;
				}
			}
		}
		c--;
	}
	for (int i = 1; i <= a; ++i)
	{
		/* code */
		for (int j = 1; j <= b; ++j)
		{
			/* code */
			cin >> x;
			if ((i + j) % 2 == 0)cout << t << " " ;
			else cout << v[x] << " ";
		}
		cout << endl;
	}

}




int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif
	clock_t z = clock();
	ll qc = 1;
	// cin >> qc;

	// p[0] = inv[0] = 1;
	// for (ll i = 1; i < 200005; i++) {
	// 	p[i] = (i * p[i - 1]) % hell;
	// 	inv[i] = bina(p[i], hell - 2);
	// }

	// seive1(1000000);
	for (ll i = 1; i <= qc; i++)
		solve();
	debug("Total Time: % .4Lf\n", (ld)(clock() - z) / CLOCKS_PER_SEC);
}