CF1485D Multiples and Power Differences

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$.

Idea

$1\le a_{i,j}\le 16$，而 $1\sim 16$ 的最小公倍数只有 $\mathrm{lcm}=720720$，这就给了启发。

在 $i+j$ 为偶数的位置填 $\mathrm{lcm}$，否则填 $\mathrm{lcm}+a_{i,j}^4$，即符合题意。

Code

/******************************************************************
Copyright: 11D_Beyonder All Rights Reserved
Author: 11D_Beyonder
Problem ID: CF1458D
Date: 2021 Mar. 3rd
Description: Number Theory, Construction
*******************************************************************/
#include<iostream>
using namespace std;
int main(){
	int n,m;
	const int lcm=720720;
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			int a;
			cin>>a;
			cout<<(((i+j)&1)?lcm+a*a*a*a:lcm)<<(j==m?'\n':' ');
		}
	}
	return 0;
}