F. Nastya and Decryption

Nastya recently joined a decryption club. After breezing through the initial tasks, she was presented with a more challenging cipher. This cipher involves two arrays of positive integers, with lengths $n$ and $m$, respectively. These arrays are encrypted into a table $V$ of size $n\times m$, where each element $v_{ij}$ represents the greatest common divisor (GCD) of the numbers $a_i$ and $b_j$ from the arrays.

Nastya has been given the table $V$ and needs to determine any two original arrays of positive integers, where each number is no greater than $10^9$, that could have been encrypted to produce this table. Your task is to assist her in finding these arrays.

Input

The first line contains two integers $n$ and $m$ ($1\le n,m\le 500$) — the lengths of the two arrays.

The following $n$ lines each contain $m$ integers $v_{i1},v_{i2},\dots ,v_{im}$ ($1\le v_{ij}\le 10^9$) — the elements of the table $V$.

Output

The first line should output $n$ integers $a_1,a_2,\dots ,a_n$ ($1\le a_i\le 10^9$) — the elements of the first array.

The second line should output $m$ integers $b_1,b_2,\dots ,b_m$ ($1\le b_i\le 10^9$) — the elements of the second array.

If there are multiple valid solutions, you may output any of them.

If no solution is possible, output $-1$ on a single line.

Examples