Нещодавно Настя записалась на гурток дешифрування. Швидко зробивши прості завдання, їй було запропоновано складніший шифр. Два масиви цілих додатних чисел довжиною n та m відповідно шифруються табличкою V розміром n на m, де vij позначає gcd(ai,bj), тобто найбільший спільний дільник (НСД) чисел ai и bj.
Настя отримала таблицю V та хоче знайти будь-які два таких початкових масиви, що всі числа у них цілі, додатні, не більші за 109, і при відповідному шифруванні вони дадуть цю табличку. Допоможіть їй це зробити.
Перший рядок містить два цілі числа n та m (1≤n,m≤500) — розміри першого та другого масиву чисел.
Наступні n рядків містять по m цілих чисел vi1,vi2,…,vim (1≤vij≤109) — числа таблиці V.
Перший рядок має містити n цілих чисел a1,a2,…,an (1≤ai≤109) — числа першого масиву.
Другий рядок має містити m цілих чисел b1,b2,…,bm (1≤bi≤109) — числа другого масиву.
Якщо існує декілька правильних відповідей, виведіть будь-яку з них.
Якщо рішення не існує, в єдиному рядку виведіть −1.