erdos

Унгарският математик Пол Ердьош (1913–1996) е доказал, че от всяко множество от p*q+1 цели положителни числа могат да се изберат  p+1 числа, всяко от които дели следващото (x1|x2|...|xp|xp+1) или q+1 числа, такива, че които и две от избраните числа да вземем, никое от тях няма да се дели на другото.

Задача

По дадени p*q+1 на брой различни цели положителни числа, да се намери подмножество от p+1 числа, които се делят последователно едно на друго или пък подмножество от q+1 числа, никое от които не е делител на друго.

Вход

Входния файл erdos.in съдържа на първия ред две цели положителни числа p и q, разделени с един интервал. Втория ред съдържа p*q+1 различни цели положителни числа, разделени с интервали. Числата са дадени в растящ ред.

Изход

Изходния файл erdos.out трябва да съдържа на първия ред числото p или числото q. Ако на първият ред е записано числото p, на втория ред трябва да има p+1 числа, избрани от дадените числа, така, че първото число е дели второто, второто дели третото и т.н. Ако на първия ред е записано числото q, тогава на вторият ред трябва да има q+1 числа от дадените, със свойството, че никое от тях не се дели на някое друго. Числата в реда трябва да бъдат в растящ ред и да са разделени с интервали.

Ограничения и пояснения

Примери

 

erdos.in

erdos.out

Обяснение

3 4
3 5 9 12 14 15 24 33 35 41 51 54 61

4
9 12 15 33 35

Никое число от множеството {9 12 15 33 35} не се дели на друго число от това множество.

 

erdos.in

erdos.out

Обяснение

3 4
3 5 9 12 14 15 24 33 72 41 51 54 61

3
3 12 24 72

3|12|24|72

Ограничение за време:  0.2 секунди на тест

prof. Emanuela Cerchez
"Grigore Moisil" Iaşi IT High School
Contact:emanuela.cerchez@gmail.com

Превод на български: Стоян Капралов