测试数据来自 system/2965

作业已超过截止时间，您无法递交本题目。

时间限制：1秒　　内存限制：256M

---

【问题描述】

　　设 \(M = m_1 ^ {m_2}\)，\(S= \{ s_1,s_2,…,s_n \}\)。

　　请你编程求一个最小正整数 \(k\)，使得 \(S\) 中至少存在一个 \(s_i\)，满足：\({s_i}^k\ mod\ M = 0\)

【输入格式】

　　第一行是两个正整数 \(m_1，m_2\)，中间用一个空格隔开。
　　第二行的第一个正整数为 \(n\)，接下来的 \(n\) 个正整数表示 \(s_1,s_2,…,s_n\)。

【输出格式】

　　输出一个整数，表示最小的 \(k\)，如果找不到满足条件的 \(k\)，则输出 -1。

【输入输出样例1】

　Input

12 2
2 42 36

　Output

2

【样例1解释】

　　对于 \(s_1=42\)，当 \(k=4\) 时，就能被 \(12^2=144\) 整除，且是满足条件最小 \(k\) 值
　　而对于 \(s_2=36\)，当 \(k=2\) 时，就能被 \(12^2=144\) 整除，且是满足条件最小 \(k\) 值

【输入输出样例2】

　Input

3 2
2 2 5

　Output

-1

【样例2解释】

　　对于 \(s_1=2\)，\(2^1=1,2^2=4,2^3=8,2^4=16,2^5=32…\)，可以看出无论 \(k\) 是多少，都无法被 \(3^2=9\) 整除；
　　同理，对于 \(s_1=5\)，\(5^1=5,5^2=25,5^3=125,5^4=625…\)，也不能找到合适的k值能被 \(3^2=9\) 整除；

【数据限制】

　　对于 \(50\%\) 的数据，有 \({m_1}^{m_2} ≤50000\)。
　　对于所有的数据，有 \(1≤n≤10000， 1≤m_1≤50000， 1≤m_2≤20000， 1≤s_i≤2,000,000,000\)。

【来源】

　　Mr.he