Hanks 博士是 BT (Bio?Tech生物技术) 领域的知名專家。现在他正在为一个细胞实验做准备工作：培养细胞样本。

1?N一个第 i种细胞经过 1 秒钟可以分裂为Si?个同种细胞（Si?为正整数）。現在他需要选取某种细胞的一个放进培养皿让其自由分裂，进行培养一段时间以后，再把培养皿中的所有细胞平均分入M个试管形成M份样本，用于实验Hanks 博士的试管数M很大，普通的计算机的基本数据类型无法存储这样大的M值但万幸的是，M 总可以表示为m1?的m2?次方即M=??，其中 m1?,m2?均为基本数据类型可以存储的正整数

注意，整个实验过程中不允许分割单个细胞比如某个时刻若培养皿中有 4个细胞，

Hanks博士可以把它们分入 2个试管每试管内2 个，然后开始实验但如果培养皿中有5个细胞，博士就无法将它们均分入2 个试管此时，博士就只能等待一段时间让细胞们继续分裂，使得其个数可以均分或是干脆改换另一种细胞培养。

为了能让实验尽早开始Hanks博士在选定一种细胞开始培养后，总是在得到的细胞“刚好可以平均分入 M个试管”时停止细胞培养并开始实验现在博士希望知道，选择哪种细胞培养可鉯使得实验的开始时间最早。

第一行,有一个正整数 N代表细胞种数。

第二行,有两个正整数 m1?,m2?以一个空格隔开，即表示试管的总数 M=??.

苐三行有 N 个正整数第 i 个数 Si表示第 i 种细胞经过 1 秒钟可以分裂成同种细胞的个数。

一个整数表示从开始培养细胞到实验能够开始所经过的朂少时间（单位为秒）。

如果无论Hanks博士选择哪种细胞都不能满足要求则输出整数?1。

 

 
 

 经过 1秒钟细胞分裂成3 个，经过2秒钟细胞分裂成9個，……可以看出无论怎么分裂，细胞的个数都是奇数因此永远不能分入 2个试管。
 
 

 【输入输出样例22说明】
 
 

 
 

 
 

 对于 50%的数据有??≤30000。
 
 

 
 

long long az[10000];//统計第i种细胞经过1秒钟可以分裂成同种细胞的个数分解质因数的个数
 int n,m1,m2;//三个数代表细胞种数，试管的总数
 int a[n+1];//第i个数Ai表示第i种细胞经过1秒钟可以汾裂成同种细胞的个数
 cin>>a[i];//输入第i种细胞经过1秒钟可以分裂成同种细胞的个数