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:
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,sse3,sse4,popcnt,abm,mmx")
#pragma comment(linker, "/STACK:64777216")

#define _CRT_SECURE_NO_WARNINGS

#include <iostream>
#include <sstream>
#include <fstream>
#include <iomanip>
#include <cstdio>
#include <cassert>
#include <climits>
#include <functional>
#include <numeric>
#include <algorithm>
#include <cmath>
#include <ctime>

#include <string>
#include <cstring>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <list>
#include <deque>
#include <unordered_set>
#include <unordered_map>
#include <bitset>
#include <array>

using namespace std;

#define forn(i, n) for(int i = 0; i < int(n); i++)
#define forn1(i, n) for(int i = 1; i <= int(n); i++)
#define sz(a) int((a).size())
#define all(a) (a).begin(), (a).end()
#define mp make_pair
#define pb push_back
#define x first
#define y second

typedef long long li;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair <li, li> pt;

const int INF = int(1e9);
const li INF64 = li(1e18);
const ld PI = acosl(ld(-1));
const ld EPS = 1e-9;

template <typename T> inline T sqr(const T& x) {
	return x * x;
}

template <typename T> inline T abs(const T& x) {
	return x > 0 ? x : -x;
}

inline bool inside(int x, int y, int n, int m) {
	return x >= 1 && x <= n && y >= 1 && y <= m;
}

inline int rnd() {
	return abs(rand() ^ (rand() << 15));
}

inline int rnd(int n) {
	assert(n > 0);
	return rnd() % n;
}

inline int rnd(int lf, int rg) {
	return lf + rnd(rg - lf + 1);
}

inline li rndLL() {
	return rnd() * 1LL * rnd() + rnd();
}

const int dx[4] = { -1, 0, +1, 0 };
const int dy[4] = { 0, +1, 0, -1 };

const int dx8[8] = { -1, -1, 0, +1, +1, +1, 0, -1 };
const int dy8[8] = { 0, +1, +1, +1, 0, -1, -1, -1 };

const int N = int(555);

int n, m, a[N][N];
int ans[N][N];

void gen() {
	
}

bool read() {
	if (scanf("%d %d", &n, &m) != 2) return false;
	forn1(i, n) forn1(j, m) assert(scanf("%d", &a[i][j]) == 1);
	return true;
}

int pw4[20];
bool used[int(1e6) + 777];

void solve() {
	for (li x = 1;; x++) {
		li y = x* x * x * x;
		if (y > 1e6) break;
		//cerr << x << ' ' << y << endl;
	}

	/*
	cerr << "LM == " << 2 * 2 * 2 * 2 * 3 * 3 * 5 * 7 * 11 * 13 << endl;
	int a = 720720;
	for (int i = 2; i <= a; i++) {
		while (a % i == 0) {
			cerr << i << ' ';
			a /= i;
		}
	}
	*/

	int good = 720720;
	set<int> ss;
	forn(i, N) forn(j, N) ans[i][j] = good;
	for (int i = 1; i <= 16; i++) {
		pw4[i] = i * i * i * i;
		ss.insert(pw4[i]);
		used[pw4[i]] = true;
	}

	forn1(i, n) {
		int st = 1;
		if (i % 2 == 1) st++;
		for (int j = st; j <= m; j += 2) {
			int x = a[i][j];
			ans[i][j] += pw4[x];
		}
	}

	/*
	forn1(i, n) {
		forn1(j, m) cerr << ans[i][j] << ' '; cerr << endl;
	}
	*/

	forn1(i, n) forn1(j, m) {
		assert(ans[i][j] <= 1000000);
		vector<int> difs;
		if (i - 1 >= 1) difs.push_back(abs(ans[i - 1][j] - ans[i][j]));
		if (i + 1 <= n) difs.push_back(abs(ans[i + 1][j] - ans[i][j]));
		if (j - 1 >= 1) difs.push_back(abs(ans[i][j - 1] - ans[i][j]));
		if (j + 1 <= m) difs.push_back(abs(ans[i][j + 1] - ans[i][j]));

		forn(k, sz(difs)) {
			int val = difs[k];
			assert(used[val]);
		}
	}

	forn1(i, n) {
		forn1(j, m) printf("%d ", ans[i][j]);
		puts("");
	}
	return;
}

ld gett() {
	return ld(clock()) / CLOCKS_PER_SEC;
}

int main() {
#ifdef _DEBUG
	(freopen("input.txt", "rt", stdin));
	(freopen("output.txt", "wt", stdout));
#endif

	cout << setprecision(15) << fixed;
	cerr << setprecision(15) << fixed;

	int T = 1;
	//T = 10000;

	srand(int(time(NULL)));

	//gen();

	//scanf("%d", &T);
	//cin >> T;
	//T = 100;

	forn(i, T) {
#ifdef _DEBUG
		cerr << "TEST == " << i << endl;
#endif
		//cerr << "TEST == " << i << endl;
		assert(read());
		//cout << "Case #" << i + 1 << ": ";
		solve();
#ifdef _DEBUG
		cerr << "curTime == " << clock() << " ms" << endl;
#endif
		//break;
	}

#ifdef _DEBUG
	cerr << "TIME == " << clock() << " ms" << endl;
#endif

	//cerr << "TIME == " << gett() << " s" << endl;
	return 0;
}