F. Nastya və deşifrə etmə

Nastya son zamanlar deşifrə dərnəyinə qoşulub. O, sadə tapşırıqları asanlıqla həll etdikdən sonra, ona daha çətin bir şifrə təqdim edildi. Bu şifrə iki tam müsbət ədədlər massivindən ibarətdir: biri uzunluğu $n$, digəri isə $m$ olan. Bu massivlər $n\times m$ ölçülü $V$ cədvəli ilə şifrələnir, burada $v_{ij}$ $a_i$ və $b_j$ ədədlərinin ən böyük ortaq böləni (ƏOB) olan $gcd(a_i,b_j)$-i göstərir.

Nastya $V$ cədvəlini əldə edib və bu cədvəli verən uyğun şifrələmə ilə iki başlanğıc massivini tapmaq istəyir. Ona bu işdə kömək edin.

Giriş verilənləri

Birinci sətir iki tam ədəd $n$ və $m$ ($1\le n,m\le 500$) — birinci və ikinci ədədlər massivinin ölçülərini göstərir.

Sonrakı $n$ sətir hər biri $m$ tam ədəd $v_{i1},v_{i2},\dots ,v_{im}$ ($1\le v_{ij}\le 10^9$) — $V$ cədvəlindəki ədədləri ehtiva edir.

Çıxış verilənləri

Birinci sətir $n$ tam ədəd $a_1,a_2,\dots ,a_n$ ($1\le a_i\le 10^9$) — birinci massivdəki ədədləri göstərməlidir.

İkinci sətir $m$ tam ədəd $b_1,b_2,\dots ,b_m$ ($1\le b_i\le 10^9$) — ikinci massivdəki ədədləri göstərməlidir.

Əgər bir neçə düzgün cavab varsa, onlardan hər hansı birini çıxarın.

Əgər həll mövcud deyilsə, yeganə sətirdə $-1$ çıxarın.

Nümunələr