Competitions
Ukrainian Olympiad in Informatics, II Stage, II Round
F. Настя та дешифрування
Нещодавно Настя записалась на гурток дешифрування. Швидко зробивши прості завдання, їй було запропоновано складніший шифр. Два масиви цілих додатних чисел довжиною $n$ та $m$ відповідно шифруються табличкою $V$ розміром $n$ на $m$, де $v_{ij}$ позначає $gcd(a_i, b_j)$, тобто найбільший спільний дільник (НСД) чисел $a_i$ и $b_j$.
Настя отримала таблицю $V$ та хоче знайти будь-які два таких початкових масиви, що всі числа у них цілі, додатні, не більші за $10^9$, і при відповідному шифруванні вони дадуть цю табличку. Допоможіть їй це зробити.
\InputFile
Перший рядок містить два цілі числа $n$ та $m$ ($1 \leq n,m \leq 500$) --- розміри першого та другого масиву чисел.
Наступні $n$ рядків містять по $m$ цілих чисел $v_{i1}, v_{i2}, \ldots, v_{im}$ ($1 \leq v_{ij} \leq 10^9$) --- числа таблиці $V$.
\OutputFile
Перший рядок має містити $n$ цілих чисел $a_1, a_2, \ldots, a_n$ ($1 \leq a_i \leq 10^9$) --- числа першого масиву.
Другий рядок має містити $m$ цілих чисел $b_1, b_2, \ldots, b_m$ ($1 \leq b_i \leq 10^9$) --- числа другого масиву.
Якщо існує декілька правильних відповідей, виведіть будь-яку з них.
Якщо рішення не існує, в єдиному рядку виведіть $-1$.
Input example #1
2 3 9 5 9 2 4 4
Output example #1
45 4 18 20 36
Input example #2
2 2 5 6 2 7
Output example #2
-1