e-olymp
favorite We need a little bit of your help to keep things running, click on this banner to learn more
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$.
Time limit 1 second
Memory limit 256 MiB
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
Author Andrey Abdulaev
Source Ukrainian Olympiad in Informatics 2021, II Stage