F. Настя и дешифрование

Настя недавно начала посещать кружок по дешифрованию. После успешного выполнения простых заданий ей предложили более сложную задачу. Даны два массива целых положительных чисел длиной $n$ и $m$, которые зашифрованы в таблице $V$ размером $n\times m$. В этой таблице элемент $v_{ij}$ равен наибольшему общему делителю (НОД) чисел $a_i$ и $b_j$.

Настя получила таблицу $V$ и хочет найти любые два исходных массива, состоящих из целых положительных чисел, не превышающих $10^9$, которые при шифровании дадут эту таблицу. Помогите ей в этом.

Входные данные

Первая строка содержит два целых числа $n$ и $m$ ($1\le n,m\le 500$) — размеры первого и второго массива.

Следующие $n$ строк содержат по $m$ целых чисел $v_{i1},v_{i2},\dots ,v_{im}$ ($1\le v_{ij}\le 10^9$) — элементы таблицы $V$.

Выходные данные

Первая строка должна содержать $n$ целых чисел $a_1,a_2,\dots ,a_n$ ($1\le a_i\le 10^9$) — элементы первого массива.

Вторая строка должна содержать $m$ целых чисел $b_1,b_2,\dots ,b_m$ ($1\le b_i\le 10^9$) — элементы второго массива.

Если существует несколько правильных решений, выведите любое из них.

Если решения не существует, выведите в единственной строке $-1$.

Примеры